Efficient Algorithm for the Approximate Search Problem in Regular Sets
Stefan Gerdjikov · 2014
за придобиване на образователната и научна степен "доктор" в професионално направление 4.5 "Математика" по научната специалност 01.01.01 "Математическа логика" Научен ръководител доцент д-р Стоян Михов СОФИЯ, септември 2013 Резюме В настоящия труд разглеждаме проблема за ефективно намиране на думите от даден (регулярен) език, които са близки до дадена дума.Близостта в това изследване е ортографска близост, тоест всяко отклонение в последователността или вида на буквите от оригинала се наказва с цена, която е цяло положително число.Конкретните ортографски замени могат да бъдат произволни, стига техният брой да е краен и те, както и техните цени да са предварително зададени.Проблемът е да се намерят всички думи в даден регулярен език, които са близки до дадена дума, V , с цена, ненадхвърляща q|V |, където q ∈ (0; 1) е рационално число, а |V | е дължината на думата V .В настоящия труд е изложено ефективно алгоритмично решение на поставения по-горе проблем.В своята същност то представлява метод от класа разделяй и владей като първоначалната заявка, думата V , се разделя на по-къси поддуми, които от своя страна определят заявки от същия вид.По-късите заявки се оказват по-лесни за разрешаване, а след това могат да се комбинират, така че да дадат решение и на първоначалната задача.С цел осъществяването на тази идея, в настоящата работа е разработен прост алгебричен апарат, който позволява изследването на свойствата на дадено ортографско разстояние и как то се отразява при търсенето на близки до дадена дума думи от даден език.Резултатите от този подход са основата за разработването на скицирания по-горе алгоритъм.Те позволяват оптималното решение на всяка от възникващите подзадачи в случая на краен език.Това означава, че времето за изпълнението на алгоритъма е пропорционално на резултатите, които той трябва да генерира.В общия случай, когато езикът е произволен регулярен, алгоритъмът е почти оптимален.Излишеството се състои в това, че в края на решаването на определена подзадача, думите генерирани в това решение, трябва да бъдат прочетени още веднъж.Ефективността на изложения алгоритъм е обоснована при известни предположения за регулярния език, ортографското разстояние и рационалния параметър q.За получаването на такъв резултат се използва комбинаторновероятностен подход, който използва метода на пораждащите функции.Той дава оценка отгоре за очакваната сложност на получения алгоритъм, която е линейна функция относно дължината на заявката с параметри, зависещи от структурата на езика, ортографското разстояние и параметъра q.Въпреки че при определени ситуации тези параметри може да не са състоятелни, тоест да бъдат +∞, показани са достатъчни условия, които осигуряват съществуването на тези параметри и тяхната крайност.В последната глава на настоящата работа предлагаме нов подход за определяне на близост между думи.Неговата основна идея е да се отчетат типичните операции, определящи разликите между търсената и дадената дума, според структурата на думите в цялост и тяхната контекстна зависимост.Предложена е практическа реализация на такъв метод, която позволява ефективно търсене на най-близката до дадена дума и адекватността на тази реализиция е потвърдена експериментално.реализация са приложени идеи на Aho и Corasick, [7], а също и общ метод, предложен от Hart et al., [24, 25], от който новият подход съумява да се възползва.Резултатите 1-6 са отразени в една самостоятелна и няколко статии в съавторство със Стоян Михов, Петър Митанкин, Klaus Schulz и Владислав Ненчев: 1.Some algebraic properties of alignments of words, S. Gerdjikov, Comptes rendu de l'Academie bulgare des Sciences, 65(10):1311-1319, 2012, Тази статия е самостоятелна.Тя представя основните стъпки, които водят до Резултати 1 и 5. По-точно, тази статия въвежда и описва основните свойства на списъците от разстояния и множества от подравнявания, които са в основата на Твърдения 5.3.6 и 5.3.15.Тя също представя Лема 7.1.6,къято се използва съществено при доказателството Твърдения 7.2.2 и 7.2.7. 2. WallBreaker -overcoming the wall effect in similarity search, S.
