Sunday, March 28, 2010

regular expression (re, regex)

Энэ материалыг хийхдээ би үр дүнтэй, өөрөө бие даан цаашид гүнзгийрүүлэх боломжтой болгох үүднээс эхлээд "re"-гийн тухай ерөнхий ойлголт өгөөд дараагаар нь түүнийг хэрхэн линуксчид маань хэрэглэж, үр дүнтэй юмаа хийх тухай үзүүлэх болно. Хэрвээ та режексийг мэдэхгүйгээр шеллийн ард сууж байгаа бол cmd.exe рүү шилжихийг зөвлөе :) .

regular expression-ийг заримдаа холбоод богинохноор нь regex гэж дууддаг. Хоорондоо ямар ч ялгаа байхгүй нэг юмыг л хоёр нэрээр нэрлэдэг.

Тэгэхлээр режекс гэдэг нь ямар нэгэн текстийн хэвийг бичих арга юм. Магадгүй заримдаа python хэл дээр хийсэн эх кодын файл хайхдаа *.py гэдэг хайлт өгдөг. Бид нар энэ хэвийг wildcard гэж нэрлэдэг шүү дээ, "*" тэмдэгний оронд юу ч байж болно гэсэн утгаар. Режекс бол wildcard-аас хол илүү хүчирхэг хэв цутгах арга юм.

Ихэнх режексийг хэрэгжүүлдэг аргууд нь дараах зүйлүүд дээр тулгуурладаг. Тийм болохоор та доорхыг уншиж байхдаа ийм хэлний режекс, тэр хэлний режекс гэж санаа зовох хэрэггүй.

. - "." буюу цэг. Цэгийн оронд ямар ч хамаагүй тэмдэгт байж болно.
^ - '^' буюу малгай. Текстийн эхлэл
$ - '$' буюу доллар. Текстийн төгсгөл
* - "*" буюу од. Одын урд байгаа тэмдэгт 0 буюу түүнээс олон давтагдана. Ө.Х: hello* гэвэл hell, hello, helloo, hellooo,... тэмдэгтүүд нь хэвэнд таарна.
+ - "+" буюу нэмэх. Нэмэх тэмдэгийн урд байгаа тэмдэгт нь 1 буюу түүнээс олон давтагдана. Ө.Х: hello+ гэвэл hello, helloo, hellooo,... тэмдэгтүүд нь хэвэнд таарна.
? - "?" буюу асуулт. Энэ нь өмнөх илэрхийлэл 0 эсвэл 1 удаа давтагдана. Ө.Х: o? гэвэл хоосон эсвэл "о" тэмдэгт нь хэвэнд таарна.
{m,n} - m эсвэл n-ийн оронд ямар нэгэн тоо байрлана. Урдах илэрхийлэл нь m-ээс n удаа давтагдана.
{m} - яг m удаа
{m,} - m буюу түүнээс олон удаа
{,n} - n буюу түүнээс бага удаа
[x-y] - "x" тэмдэгтээс "у" хүртэлх тэмдэгт. "х"-ийн ASCII дугаараас "у"-ийн ASCII дугаар хүртэлх тэмдэгтүүдийг илэрхийлнэ. inclusive буюу х,у 2 тэмдэгт өөрсдөө орно.
[X] - олонлогоор тэмдэгтүүдийг нь заана. X нь abc бол зөвхөн a,b,c тэмдэгт гэнэ. Мөн гүйцээлт олонлогийг [^X] гэж тэмдэглэдэг. Ө.Х a,b,c-гээс бусад тэмдэгтүүдийг оруулна.
(regex) - хоёр нуман хаалт хоёр талд нь тавьж режексийг бүлэглэдэг. Мөн хаалтанд бичсэн илэрхийллийг текстэн дундаас ялгаж авах боломжтой болдог.
re1|re2 - "|" буюу босоо хаалт. хоёр текстийн хэвийн аль нэг нь таарна.

Дээр дурдагдсан тусгай тэмдэгтүүдийг режекст бичихдээ урд нь '\' тавьж утгыг нь арилгадаг. Өөр нэг чухал шинж чанартай: А гэсэн текст нь regex_A хэвэнд таардаг, В гэсэн текст нь regex_В гэсэн хэвэнд таардаг байг. Тэгвэл AB текст нь regex_Aregex_B гэсэн текстийн хэвэнд таарна. Формаль байгаа биз? (tnx for Folks)

ХЭРЭГЛЭЭ.1

Зиак одоо өмнөх харсан жаахан зүйлээрээ юм хийе.

КтМС-ийн оюутны кодны хэвийг бичье:
D\.[A-Z]{2}[0-9]{2}D[0-9]{3} - "D" үсгээр эхлээд ард нь цэг бичээд тэгээд A-Z хүртэлх тэмдэгтээс 2 удаа ороод 0-9 хүртэлх тэмдэгт бас 2 удаа, D үсэг дараагаар нь 0-9 хүртэлх тэмдэгт гурван удаа орно гэдгийг зааж байна.

Зөвхөн КтМС ашигладаг програмын хувьд урд нь "D." текст байх хэрэгтэй юм уу? тэгэхлээр байж ч болно байхгүй ч болно. Хэв маань дараах хэлбэртэй болно:
(D\.)?[A-Z]{2}[0-9]{2}D[0-9]{3}

Оюутнууд нь SW, PT, BA, HW гэсэн кодоор эхлэдэг. Эдгээрийн аль нэг нь таарах хэрэгтэй. Тэгвэл эдгээрийг тааруулъя:
(D\.)?(SW|PT|BA|HW)[0-9]D[0-9]{3}

Одоо 90 оноос хойшхи 2009 он хүртэлх оюутны код гэвэл:
(D\.)?(SW|PT|BA|HW)[09][0-9]{2}D[0-9]{3}

Ганц чухал зүйлээ орхисон байна. Оюутны код маань бүхлээрээ дээрх хэвд таарах ёстой. Хоёр талд нь эхлэл төгсгөлийн тэмдэгт тавья
^(D\.)?(SW|PT|BA|HW)[09][0-9]{2}D[0-9]{3}$

ХЭРЭГЛЭЭ.2

Линуксчид маань grep гэдэг командыг нэлээн хэрэглэдэг байх. Энэ команд нь хэвэнд таарсан файлын мөрийг хэвлэж үзүүлдэг. Энэ хэвийг нь режексээр өгөх боломжтой байдаг учраас хэдүүлээ режекс бичье. Python-чид маань нэг төсөл дээр ажиллаж байг л дээ. Тэгээд бүх зарласан функцүүдээ хармаар байдаг. Азаар grep команд маань файлын системүүдээр рекурсивээр шилжиж явах боломжтой байдаг.

Python хэлний функцийн зарлагааны хэвийг нь бичье:
def .*\(.*\)
Манай гол ажил режексээ биччихлээ. Тэгэхлээр одоо grep командаа одоо байгаа директороос (Ө.Х "." директор) рекурсивээр режексээр хайна гэдгээ хэлж өгөх хэрэгтэй. Үүний тулд дараах горимыг бичиж өгнө "-rE". -r нь рекурсив, -E нь өргөтгөсөн режекс гэдгийг илтгэж байна.
Одоо шелл дээрээсээ дараах командыг ажиллуулъя:

tulga@tulga-laptop:~/Documents/project$ grep -rE "def .*\(.*\)" .
./presenter_server/rpc_server.py: def __init__(self):
./presenter_server/rpc_server.py: def login(self, username, passwd):
./presenter_server/rpc_server.py: def printvalue(self):
./presenter_server/tests.py: def test_basic_addition(self):
./presenter_server/views.py:def hello(request):
./presenter/thread_example.py: def __init__(self):
./presenter/thread_example.py: def A(self):
./presenter/thread_example.py: def B(self):
./presenter/chat.py: def __init__(self):
./presenter/chat.py: def on_login_button_pressed(self, widget, data = None):
./presenter/chat.py: def on_login_window_destroy(self, widget, data = None):
./chat/tests.py: def test_basic_addition(self):
./core/tests.py: def test_basic_addition(self):
./core/views.py:def index(request):

Си хэлний функцүүдийг гаргая гэвэл хэв маань ямар болохыг өөрсдөө бодож олоорой :)

ХЭРЭГЛЭЭ.3

Өгөгдлийн бүтэц гэдэг хичээл дээр математикийн хаалттай илэрхийллийг бодох даалгавар өгч билээ. Тэр үед яаж ийж байгаад л хоёртын модонд оруулаад бодсон юм. Дахиад бичих нь режексийг сурахаас өмнө маш хэцүү санагддаг байлаа.

Хаалттай математикийн илэрхийллийг бодохын тулд режекс ашиглаад дараах байдлаар хийж болно:

1. Хамгийн дотор талын хаалттай илэрхийллийг ол.
2. Хэрвээ олдохгүй бол 7 руу шилж
3. Хамгийн дотор талын хаалттай илэрхийллийн :, * илэрхийллийг олж бод.
4. +, - үйлдлүүдийг бод.
5. Бодсон үр дүнгээ дотор талын хаалттай илэрхийллийн оронд тавь
6. 1 рүү шилж
7. 3, 4-ийг хийж үр дүнг харуул.

Тэгэхлээр би бүтэн ажилладаг програм бичихгүй зөвхөн хамгийн дотор талын хаалттай илэрхийллийг яаж ялгах авах режексийг л үзүүлнэ. Текстэн дундаас тэрхүү илэрхийлэл нь хаалтаар эхлээд түүнээс хойшхи тэмдэгтүүдэд нь нээсэн хаалт биш зөвхөн хаасан хаалт тааралдах хүртэлх тэмдэгтүүд байх ёстой.
Хэв нь: ^.*(\([^(]*\)).*$
Текстийн эхлэлээс төгсгөл хүртэлх тэмдэгтийн хэвийг үзүүлжээ. Эхлэлээсээ дурын тэмдэгтийн дурын давталт яваад "(" тэмдэгт орж ирээд түүнээс хойш "(" биш тэмдэгтүүдийн дурын давталт ")" тэмдэгт орж ирээд дурын тэмдэгтийг давтсаар байгаад дуусгажээ. \(, \) Яг хаалт гэдгийг нь зааж өгч байна харин урдаа "\"-гүй 2 хаалт нь дахин хэлье бүлэглэдэг. Тэгэхээр хэвэнд тааруулсныхаа дараа 1-р бүлэг буюу 1-р групп гээд хандах боломжтой. Энэ үүргийг линуксын sed команд гүйцэтгэж чаддаг.

ХЭРЭГЛЭЭ.4

Python хэл дээр киноны subtitle шүүж боловсруулдаг жижигхэн програм бичье.

Энэ хэл дээр режексийн сан нь re гэсэн нэртэй байдаг. Харин текстийн хэвийг зарим тохиолдолд хөрвүүлэх шаардлагатай байдаг. Тэгж гэмээ нь хурдан ажиллана.
Тэгэхээр хэрвээ subtitle чинь Виндовс үйлдлийн систем дээр бэлтгэгдсэн бол мөрийн төгсгөлд 2 тэмдэгтэй байдаг. Энийг '\r\n' гэж тэмдэглэсэн байдаг. Яагаад ч юм энэ хоёр нь мөрийн төгсгөл, шинэ мөрийн эхлэл гэсэн 2 тэмдэгт юм билээ.

Хоёр удаа шинэ мөрийн авч subtitle-ийн үзэгдэл болгон нь хуваагддаг. Үзэгдэл нь эхний мөрөндөө дугаараа дараагийн мөрөнд хэзээнээс хэдий хүртэл гаргах тэгээд үлдсэн мөрөндөө ямар текст үзүүлэхээ харуулдаг. Жишээ нь иймэрхүү хэлбэртэй байна гэсэн үг:

1
00:00:01,476 --> 00:00:03,915
Subtitles: SION HOME VIDEO
sion_py@yahoo.com

2
00:00:04,175 --> 00:00:06,817
Review and synchronization:
Nightcrawler

3
00:00:30,888 --> 00:00:34,683
TE love you forever

4
00:01:02,085 --> 00:01:05,811
-I do not sing.
-It was good, Henry.

5
00:01:05,911 --> 00:01:08,779
I do not know how you sing.
-Of course not.

1-р алхам.
# subtitle хадгалж байгаа файлаа нээх хэрэгтэй:
sub_file = open("path/to/sub/file")
2-р алхам.
# файлын заагчийг авсан тул файлаа уншаад доторхийг нь хувьсагчдаа хадгалаад авчихъя
subtitle = sub_file.read()
3-р алхам
# одоо режексийн сангаа оруулж ирээд текстийн хэвээ хөрвүүлэх хэрэгтэй.
import re
sub_pattern = re.compile('\n{2}', re.S)
# re.S гэдэг нь шинэ мөр гэдэг \n тэмдэгтийг хүртэл "."-ээр тэмдэглэе гэсэн үг
4-р алхам
# мөрийн төгсгөл гэдэг тэмдэгтийн асуудалд орохгүйн тулд тэрийг хасчихъя
subtitle = subtitle.replace('\r','')
5-р алхам
# режексийн тусламжтайгаар үзэгдлүүдийг хуваагаад авчихъя
sub_list = re.split(sub_pattern, subtitle)
6-р алхам
# бидэнд үзэгдлийн дугаар, эхлэх хугацаа, дуусах хугацаа, ямар текст гаргахыг мэдэх хэрэгтэй, дахиж текстийн хэв хөрвүүлье:
sub_detail_pattern = re.compile('^([0-9]+) \n([0-9]+:[0-9]+:[0-9,]+) --> ([0-9]+:[0-9]+:[0-9,]+) \n(.*)$',re.S)
7-р алхам
# одоо 6 дээр хийсэн хэвээ ашиглан 1-р үзэгдлийн текстийг хэвэнд тааруулъя:
matched_sub = re.match(sub_detail_pattern, sub_list[0])
8-р алхам
# олсон үр дүнгээ мэдэж авах хэрэгтэй, бид нар хаалт ашиглан бүлэглэж авсан тул мэдээллийг авахад ямар ч асуудалгүй. Бүлгийг зүүн талаас нь эхлэн 1-ээс эхэлж дугаарладаг. 0-рт нь таарсан текст өөрөө байрлана.
print "дугаар:", matched_sub.group(1)
print "эхлэх хугацаа:", matched_sub.group(2)
print "дуусах хугацаа:", matched_sub.group(3)
print "текст:", matched_sub.group(4)

ХЭРЭГЛЭЭ.5

Энэ удаад режексийн тусламжтайгаар Python хэл дээр вебсайтнаас линкүүдийг нь шүүж авна.
import urllib2
import re
import sys
# html текстнээс линкийг нь шүүж байна.
def extract_links(page_text):
      return [ hrefs for hrefs in re.findall('href="(.+?)"',page_text) ]

# domain хаягийг нь өгөхөд линкүүдийг нь шүүж гаргана.
def printlinks_of(domain):
      html_fd = urllib2.urlopen(domain)
      html_text = html_fd.read()
      print extract_links(html_text)

if __name__ == "__main__":
      printlinks_of(sys.argv[1])

За тэгээд нөхөд өөрсдөө давталтан дундаа оруулаад subtitle-аа хийнэ биз, зөвхөн режексийн тухай үзүүлэх гэсэн учир бүрэн юм бичсэнгүй. Амжилт хүсье, линукс алхам тутамд чинь режекс хэрэглэнэ шүү!

Wednesday, March 24, 2010

Ном зарна

Надад хэрэглэж дууссан ном байгаа юм. Тэгээд зардаг юмуу гэж бодоод. Тэгэхдээ үнэгүй ч өгч болно. Ийм ийм ном байна:
TCP/IP network - Энэ их сайн ном интернетийг анх зохиолцож байсан хүн бичсэн юм билээ, их зузаан.
Kernel project - Энэ номыг хэсэг орчуулж байсан юм. Бас дажгүй практик талыг нь голлосон.
Classical Object Oriented Development - Бас их сайн ном "системийн шинжилгээ" талыг илүү үзүүлсэн.
Java Design Patterns - Их зузаан жава сурч байгаа нөхдүүдэд хэрэгтэй эд.
Би хүний сурах эрмэлзлэлийг мөнгөөр хэмжмээргүй байна, тэгэхээр чадвар сурах эрмэлзлэлийг нь бодолцоноо. Vortex-ийн эхний 5 үеийг давсан хүнд бүх номоо зүгээр өгнө. Энэний линк нь: http://www.overthewire.org/wargames/vortex/. Харин зарвал тус бүрийг нь 15.000-гаар бүгдийг нь зэрэг л зарна. Эсвэл what.cd сайтын урилга авч чадсан хүнд дуртай 1 номыг нь бэлэглэнэ.

Wednesday, March 3, 2010

DNS ойхгүй байна уу?

DNS буюу Domain Name Resolution-ийн гол үйл ажиллагааг мэддэг боловч яг яаж ажилладгийг мэддэггүй байсан юм, миний мэддэг зүйл бол зүгээр домэйн нэрийг IP хаяг руу буулгадаг л гэж боддог байсан тэгсэн нэлээн гүнзгий эд байна лээ. Тэгээд мэдсэн дээрээ энэ тухай бичихийг зорилоо. Доор бичсэн зүйл бол зөвхөн миний ойлгосон ойлгоц! тийм болохоор буруу байж магадгүй зөв ч байж магадгүй "comment" үлдээгээрэй.

DNS гэдэг нь үндсэндээ өмнө хэлсэн шиг домэйн нэрийг IP хаяг руу хөрвүүлдэг. Харин домэйн нэр нь хүнд цээжлэхэд хялбархан нэг үг ардаа com, org, net, mn, uk, en, cn... гэсэн зориулалтын дагавартай бүгд сайтынхаа утгыг агуулж байдаг. Жишээ нь: www.ehlel.com домэйн 124.158.127.28 ip хаягтай com гэсэн өргөтгөлтэй. Тэгэхээр зүгээр ehlel.com гэдэг рүү орохын тулд ийм тасархай 4-н тоо цээжлэх хэрэггүй болноо гэсэн үг. Зүгээр л DNS серверээс асуух хэрэгтэй.

DNS нь яг утсаар ярихтай ижилхэн. Та над руу залгая гэж бодъё, тэгвэл дэвтрээ гаргаж ирж байгаад л "за нөхөр Тулга чинь ямар дугаартай билээ, аа тийм энд байна 96763961 юм байна" гээд л дугаараа хийгээд залгана, энэ дугаар харах үйлчилгээг л DNS сервер хийж өгдөг. Тэгэхээр нөхөр Ehlel.com рүү залгая дугаар нь хэд билээ? 124.158.127.28 thanks. Шууд ингэж харагдаж болж байгаа бол түүнийг А буюу absolute нэр гэдэг.

Түүнээс гадна домэйн нэрүүд ч бас хочтой байдаг. Манай зарим найз нар намайг Туба гэдэг, тэгэхдээ Туба гэдэг нэр дээр Тулгын л дугаар явж байгаа шүү дээ. Би Google-ийг Gogle гэж дуудах дуртай, ялгаагүй энэ нөгөө хоч нь л байхгүй юу. Үүнийг DNS серверүүд CNAME гэж дууддаг(canonical name). Энэ коммандыг шелл дээрээсээ өгөөд үз дээ:

$dig www.yahoo.com

www.yahoo.com. 59 IN CNAME fp.wg1.b.yahoo.com.
fp.wg1.b.yahoo.com. 3124 IN CNAME any-fp.wa1.b.yahoo.com.
any-fp.wa1.b.yahoo.com. 7 IN A 72.30.2.43
any-fp.wa1.b.yahoo.com. 7 IN A 98.137.149.56

Иймэрхүү хариу ирнэ. Тэгэхээр манай yahoo чинь өөр сонин сонин нэртэй юм байна шд. Энэ лав л араб байхаа :) Арабууд чинь нээх урт нэртэй байдаг шд. Бид нар тэгэхээр yahoo гэдэг хочоор нь холбогдох DNS сервер надад "any-fp.wa1.b.yahoo.com" гэсэн ийм сонин араб нэр өгөхнээ. Утасны дугаар нь 72.30.2.43. Хүүе байз энэ залуу чинь хоёр утас барьдаг юм байна. Нөгөө дугаар нь 98.137.149.56 гэж байна. Аль нэг рүү нь залгана даа. Тэгэхээр би ч бас 2 утас барьдаг алин руу нь ч залгасан тэр утас унтраагүй л бол би аваад л ярина яг л адилхан байгаа биз? Өшөө бүүр адилхан түр хүлээ.

Дээхнэ үед манай гэрийнхэн дундаа 5 оронтой утасны дугаар авч тавьсан гэрийн утастай байлаа. Тэр дугаарын тусламжтайгаар гаднаас хүн залгаад бидний алинтай нь ч ярьж болдог байв. Тэгэхээр нэг утасны дугаар дээр олон хүн байж болно. Үүнтэй адилаар нэг ip хаяг дээр өөр домэйн хаягууд байрлаж болно. Жишээ нь: 124.158.127.28 дугаар луу залгаад Ehlel-тэй яръя гэвэл нэг хүн(Apache server) аваад "Хөөе Ehleeel чамтай яръя гэж байна" гэнэ. Өөрөөр саяны дугаар луу залгаад Citinet-тэй яръя гэвэл бас л адилхан "Хөөе Citi чамтай яръя гэж байна" гээд Сититэй ярилцах болно. Энэхүү хэнтэй яръя гэдэг процесс нь HTTP/1.1-ээс эхлэн ажилладаг болсон гэж уншсан юм байна. Өмнө нь нэг дугаар зөвхөн нэг хүн л байна гэж бодож л дээ. Тэгээд шинэ хувилбар дээрээ өөр хүн рүү залгаж болох юм байна тийм болохоор HTTP протоколынхоо толгой хэсэгт хэнтэй ярихаа бичиж бай гэдэг болсон гэнэ лээ.

Тэгэхээр та DNS-ийг хэрхэн ашиглах талаар ерөнхий ойлголттой болсон байх. Одоо арай гүнзгийрье. Хэн нэгэн рүү залгах болгондоо бүх хүмүүс зөвхөн ганцхан DNS гэдэг супер залуугаас асуугаад байвал залуу хэзээ ч хариулт өгч чадахгүй. denial of service, flooding эд нар тохиолдоод ёстой амжихгүй биз. Тэгэхээр интернетийн ертөнцөд маш олон DNS сервер энэхүү хүнд үүргийг гүйцэтгэж жигд ачаалалтай ажиллаж байдаг. Яаж?
"TEDY" нь урьдчилсан төлбөрт үйлчилгээний хэсэг нь урьдчилсан төлбөрт үйлчилгээгээ л хариуцдаг, дараа төлбөрт нь зөвхөн дараа төлбөртөө хариуцдаг. Үүн шиг интернетэд com гэснийг хариуцсан хэдэн нөхдүүд сууж байдаг(нарийн хэлбэл 13), org гэснийг хариуцсан бас хэд бий. Тэгэхээр та залгах гэж байгаа найзынхаа утасны дугаарыг мэдэхийн тулд эхлээд "Root" гэдэг нөхрөөс асууна, харин Root нь аан та "mn" гэсэн өргөтгөлтэй рүү залгах гэж байгаан байна тэнд сууж байгаа Magicnet-ийн хүмүүсээс асуу гээд явуулна. Тэнд сууж байгаа хүмүүс чинь танд хэрвээ тийм утасны дугаар бүртгэлтэй байвал дугаарыг нь өгөөд байхгүй бол "тийм дугаар алгаа" гэнэ. За ухан ухан ойлгосон зүйлээ бичиж дуусгалаа. Thanks.