N-გრამიანი მსგავსება და დისტანცია

დღეისათვის თითქმის ყველა პროგრამაში, რომელიც რაიმე სახის ტექსტური (და არა მარტო ტექსტური) მონაცემების დამუშავებაზეა დაფუძნებული, აუცილებელია ტექსტში ძებნის შესაძლებლობა. ბევრ პროგრამაში, მით უმეტეს, თუ პროგრამა გათვლილია ადამიანთან ინტერაქციაზე, მათი სპეციფიკიდან გამომდინარე, აუცილებელია მონაცემების მიახლობითი ძებნის არსებობა, რაც ზემოთ ხსენებულ ამოცანას კიდევ უფრო მეტად ართულებს. მონაცემების მიახლოებითი ძებნის ერთ-ერთ მთავარ სირთულეს წარმოადგენს ის, რომ რთულია ალგორითმულად დადგინდეს და შეფასდეს რაიმე კრიტერიუმით ორი მოცემული სიტყვის მსგავსება, რამეთუ მსგავსება დამოკიდებულია კონკრეტული ადამიანის აღქმაზე, რისი ცალმხრივად განმარტება, ალბათ, შეუძლებელიც არის. სიტყვების მსგავსების მთვლელი მრავალი ცნობილი და უკვე აპრობირებული ალგორითმი არსებობს. მათ შორის ყველაზე კარგად ცნობილი ალგორითმები დაფუძნებულია ფრაზების ცვლილების დისტანციასა (Edit Distance) და უდიდესი საერთო ქვე-ფრაზის სიგრძეზე (Longest common subsequence). ნაშრომის მთავარი მიზანი ეფექტური ალგორითმის შემუშავება და პროგრამული უზრუნველყოფაა, ალგორითმის, რომელიც მოცემულ ორ ფრაზას შორის მსგავსებას დათვლის და მსგავსების კოეფიციენტს დაგვიბრუნებს, რაც შეიძლება დიდი სიზუსტით. ნაშრომში წარმოდგენილია N-გრამიანი მსგავსების და დისტანციის ფორმალური და რეკურსიული განმარტებები. ნაჩვენებია, რომ ფრაზების ცვლილების დისტანცია და უდიდესი საერთო ქვე-ფრაზის სიგრძე კონკრეტული შემთხვევებია N-გრამიანი დისტანციისა და მსგავსებისა. ნაშრომში ასევე წარმოდგენილია N-გრამიანი მსგავსებისა და დისტანციის დათვლის ეფექტური ალგორითმები და მათი პროგრამული უზრუნველყოფა. ნაშრომში შემოღბულია ფრაზების მსგავსების ახალ საზომები, რომლებიც N-გრამიან ალგორითმებზე არის დაფუძნებული.

მიმაგრებული ფაილები: