Google Search (CSE, SS)
Mknik.com
haykakan saiyterum voronmamb. Urakh klinem masnaktselu drants shourj
khindirneri qnnarkman@.
GTUG Armenia
Ցավոք, առաջիկա հանդիպմանը` փետրվարի 12-ին, օրակարգում որոնողական համակարգն ընդգրկված չէ: Այդ թեմայի շուրջ կխոսենք հաջորդ հանդիպումների ժամանակ:
Խնդրում ենք միանալ GTUG ՀԱՅԱՍՏԱՆ-ի գուգլյան խմբին, քաննարկումներին մասնակցելու և հանդիպումների մասին տեղյակ լինելու համար:
Շնորհակալություն:
GTUG Հայաստան թիմ,
Վարդան Գրիգորյան
Vardan "Vermillion" Grigoryan
Որոնումը բավական հետաքրքիր և լայն թեմա է, մասնավորապես մեծ
հետաքրքրություն են առաջացնում տողերի(string) մշակումն ու որոնումը, որը
և կիրառվում է որոնողական համակարգերում, որոնցից են Bing-ը և մեր սիրելի
Google Search-ը։
Որոնման համակարգերում որոնվող արտահայտության լեզուն էական չէ, եթե
որոնումը
կազմակերպվում է որպես սիմվոլների հաջորդական համեմատություն։
Բավական է պատկերացնել ԱԲ-ին մոտ որոնման համակարգ, որը կատարում է
համապատասխան
որոնում հիմնվելով այնպիսի նրբությունների վրա, ինչպիսիք են որոնվող
բառերի առավել
իմաստալից կոմբինացիա և այլն։ Նշված տարբերակը բավական կասկածելի
կիրառություն ունի, մասնավորապես՝ բավական մեծ քանակով լեզուների համար
դժվար է նմանատիպ
նրբությունների մշակումը։
Այս մասում կդիտարկենք առաջին դեպքը, այն է լեզվի ոչ էական լինելը։ Սա
բավական
հեշտ, բայց միևնույն ժամանակ բավական զանազան և մաս-առ-մաս նաև բարդ դեպք
է։ Այստեղ գործում են երկու առանցքային բաղկացուցիչներ՝ որոնվող
բառ(արտահայտություն), և որոնման բազմություն՝ այն
տեքստը(արտահայտությունների բազմությունը), որտեղ և անհրաժեշտ է կատարել
նշված որոնումը։
Մինչ ալգորիթմների մանրամասն դիտարկումը, տեսնենք, թե ինչ թեմաներ են
քննարկվելու
"Որոնման մեխանիզմներ"-ի այս և մնացած բաժիններում՝
Որոնման ալգորիթմներ։
- Knuth-Morris-Pratt
- Boyer-Moore
- Karp-Rabin
- Aho–Corasick string matching algorithm
Որոնող մեքենաներ(посиковые машины)
- տեսական ներածություն և հիմնական դրույթներ
- որոնման մեքենաների կառուցվածքը
- որոնման մեքենայի իրականացում
Քննարկումը չի ավարտվի վերը նշված ցուցակում դիտարկված կետերով, կփորձենք
ժամանակ առ ժամանակ դրանք թարմացնել և ավելացնել քննարկմանն ենթակա նոր
կետեր։
Եվ այսպես,
Knuth-Morris-Pratt-ի ալգորիթմ
------------------------------------------------
Սա, այսպես կոչված, "գծային ժամանակով" կատարման ամենահայտնի ալգորիթմն
է, որն
առաջարկվել է Դոնալդ Կնուտի(http://en.wikipedia.org/wiki/Donald_Knuth),
Վոուգան Պրատտի(http://en.wikipedia.org/wiki/Vaughan_Pratt) և նրանցից
անկախ՝ Ջեյմս Մորրիսի(http://en.wikipedia.org/wiki/James_H._Morris)
կողմից։ Չնայած այս ալգորիթմն արդեն հազվադեպ է կիրառվում և շատ հաճախ
զիջում է Բոյեր-Մուրի(և ոչ միայն) ալգորիթմին(կդիտարկվի հաջորդիվ), այն
կորող է հեշտ ընկալվել, իսկ նրա գծային ժամանակը պարզ է հիմնավորվում։
Բացի այս, Կնուտ-Մորրիս-Պրատտի ալգորիթմը ստեղծում է հիմք՝ Ահո-Կորասիկի
հայտնի ալգորիթմի համար։ Վերջինս բավական էֆեկտիվորեն որոնում է տեքստում
նմուշների տրված բազմության բոլոր համընկնումները։
Նախ պատկերացնենք, թե ինչպես է կատարվում հաջորդական որոնումը, այսինքն՝
տեքստում մի որոշ բառի որոնումը։ Ենթադրենք պետք է որոնել "trial" բառը
"try the trial version" տեքստում։
Սկզբում համեմատում ենք "trial" բառի "t" տառը նշված տեքստի առաջին տառի
հետ՝ "t"։ Դրանք նույնն են, հետևաբար անցնում ենք որոնվող բառի հաջորդ
տառին՝ "r" և համեմատում ենք տեքստի հաջորդ տառի հետ, ստանում ենք այսպես
կոչված "true":). Անցնում ենք մեր "trial" բառի երրորդ տառին՝ "i", և
համեմատում այն տեքստի "y" տառի հետ։ Ստանալով համեմատման բացասական
արդյունք, փորձում ենք կրկին, բայց այս անգամ բառի համեմատությունը
կսկսենք ոչ թե տեքստի սկզբից, այլ սկսած մի սիմվոլ դեպի աջ։ Համեմատում
ենք "trial"-ի "t" տառը տեքստի "r" տառի հետ և այսպես շարունակ, մինչև
գտնվի անհրաժեշտ բառը, կամ հասնենք տեքստի վերջ և համոզվենք, որ որոնվող
բառը չի պարունակվում այդ տեքստում։ Դիտարկենք նկարագրած քայլերը
հնարավորինս "վիզուալ"։
1)
try the trial version
trial
2)
try the trial version
trial
3)
try the trial version
trial
...
k+1)
try the trial version
trial
(հազիվ։)
Ինչևէ, սա բավական կոպիտ, ինչու ոչ՝ նաև տգեղ, օրինակ է, սակայն բավական
հեշտ համոզում է Կնուտ-Մորրիս-Պրատտի(այսուհետ՝ K-M-P) ալգորիթմի գեղեցիկ
տրամաբանությունը։
K-M-P ալգորիթմը փորձում է օգտագործել որոշ ինֆորմացիա կապված այն տեքստի
հետ, որտեղ կատարվում է նախատեսված բառի որոնումը։ Ինչ-որ առումով կարելի
է այն համարել "խելացի" ալգորիթմ, որովհետև տեքստի և որոնվող բառի ամեն
մի անհավասարության("չհամընկնելության") դեպքում որոնվող բառը
տեղափոխվում է ամբողջ անցած տարածությունով, քանի-որ մեկ քայլանոց
տեղափոխությունները չեն բերի ամբողջական համընկնելիության։ Ասվածը
հասկանալու համար դիտարկենք հետևյալ օրինակը։
Որոնվող բառ։ "Google".
Որոնման տեքս։ "Good search engine by Google".
Առաջին փուլը բերված է ներքևում՝
1)
Good search engine by Google
Google
Տեքստի և որոնվող բառի առաջին երեք սիմվոլները համընկնում են, K-M-P
ալգորիթմը
համեմատում է տեքստի և բառի համապատասխան սիմվոլները՝ "d" և "g"։
Ալգորիթմին պարզ է դառնում, որ տեքստի բառը մեր ուզած բառը չի կարող
լինել։ Ի տարբերություն հաջորդական որոնման ալգորիթմին, K-M-P-ն չի
փորձում տեղափոխել որոնվող բառը մեկ սիմվոլով, այլ տեղափոխում է այն
մինչև այն դիրքը(որոնման տեսքտում), որտեղ ալգորիթմը դեռ ոչ մի
համեմատություն չի արել։
2)
Good search engine by Google
Google
Կարճ ասած, մենք տնտեսեցինք երկու տեղափոխություն/համեմատություն։ Բայց
այստեղից սկսած մինչև տեքստի "Google" բառը, K-M-P ալգորիթմը ևս ստիպված
է բառը տեղափոխել մեկական սիմվոլներով։ Ամեն դեպքում, K-M-P-ի
արագությունը մնում է գծային՝ O(n), մինչ հաջորդականինը՝ O(n*m), որտեղ m-
ը որոնվող բառի մեծությունն է։
Արդեն իսկ կարելի է ենթադրել, որ K-M-P ալգորիթմը "օգուտ" կտա, եթե
անհաջողությանը նախորդել են մի քանի համընկումներ, միայն այդ դեպքում
կտնտեսվեն որոշ թվով համեմատություններ՝ որոնվող բառի թռիչքի միջոցով։
Նշենք նաև, որ այստեղ էական չէ որոնման տեքստի կամ որոնվող բառի լեզուն,
անկախ այն բանից հայերեն է այն, թե ոչ, դիտարկված ալգորիթմները
համեմատություն են կատարում սիմվոլ առ սիմվոլ։ Ինձ համար, համենայն դեպս,
լեզվի վրա շեշտը դրված որոնումը շատ է հետաքրքրում, հաճույքով կմասնակցեմ
հնարավոր քննարկումներին։
Այսքանով եզրափակենք առաջին մասը, որն անկեղծ ասած փորձնական է։ Եթե
թեման հետաքրքիր է, իսկ խորացումը՝ ցանկալի, ապա կփորձեմ դիտարկել K-M-P-
ն ավելի մանրամասն և կբերեմ ալգորիթմն իրականացնող ծրագրային կոդը։
Ինչպես նաև հաջորդաբար կդիտարկենք մնացած ալգորիթմներն ու մեխանիզմները։
Ավելի շատ ինֆորմացիա- http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm