Приближно поклапање ниске

Расплинута Викимедија претрага за "angry emoticon": "Да ли сте мислили: andré emotions"

У рачунарству, приближно поклапање ниске (често неформално названо расплинуто поклапање ниске) је техника проналажења ниски које приближно одговарају обрасцу (уместо тачно). Проблем приближног поклапања ниске се углавном дели на два потпроблема: проналажење поклапања приближне подниске унутар дате ниске и проналажење ниски у речнику који одговарају обрасцу приближно.

Преглед

Прецизност поклапања се одређује на основу броја примитивних операција потребних за претварање ниске у тачно поклапање. Овај број се назива едит растојање између ниске и обрасца. Уобичајене примитивне операције су:

• додавање: cot → coat
• брисање: coat → cot
• замена: coat → cost

Ове три операције могу бити уопштене као форма замене додавањем NULL карактера (овде приказаног симболом *) где год је карактер обрисан или убачен:

• додавање: co*t → coat
• брисање: coat → co*t
• замена: coat → cost

Некада се у приближном поклапању транспозиција, у којој се позиције два слова у ниски замене, третира као примитивна операција. Промена cost у cots је пример транспозиције.

Различита приближна поклапања намећу различита ограничења. Нека поклапања користе једну општу безтежинску цену, тј. она представља укупан број примитивних операција потребних да за претварање поклапања у образац. На пример, ако је образац coil, foil се добија једном заменом, coils једним додавањем, oil једним брисањем, а foal са две замене. Ако се све операције рачунају као једна јединица цене и ограничење је постављено на један, foil, coils, и oil се рачунају као поклапања, док foal не.

Друга поклапања одређују број операција сваког типа посебно, док нека постављају укупну цену али дозвољавају различите вредности да буду додељене различитим операцијама. Нека поклапања дозвољавају одвојене доделе ограничења и вредности различитим групама у обрасцу.

Проблем формулације и алгоритми

Једна могућа дефиниција приближног поклапања ниске је следећа: Дата је ниска обрасца: $P=p_{1}p_{2}...p_{m}$ и ниска текста $T=t_{1}t_{2}\dots t_{n}$, пронаћи подниску $T_{j',j}=t_{j'}\dots t_{j}$ у T, који има најмање едит растојање до обрасца P од свих могућих подниски у T.

Приступ грубом силом (brute-force приступ) би био да се израчуна едит растојање до P за све подниске у T, и онда одабрати подниску са најмањим растојањем. Међутим, временска сложеност овог алгоритма би била O(n³ m).

Боље решење, које је предложио Селерс, ослања се на динамичко програмирање. Овде се проблем другачије формулише: за сваку позицију j у тексту T и сваку позицију i у обрасцу P, израчунати најмање едит растојање између првих i карактера обрасца $P_{i}$, и било које подниске $T_{j',j}$ из T који се завршава на позицији j.

За сваку позицију j у тексту T, и сваку позицију i у обрасцу P, проћи кроз све подниске у T завршно са позицијом j, и одредити која од њих има најмање едит растојање до првих i карактера обрасца P. Записати најмање растојање као E(i, j). Након израчунавања E(i, j) за све i и j, можемо лако наћи решење почетног проблема: то је подниска за коју је E(m, j) најмање (где је m дужина обрасца P).

Израчунавање E(m, j) је веома слично израчунавању едит растојања између две ниске. У ствари, можемо искористити алгоритам за израчунавање Левенштајновог растојања за израчунавање E(m, j), једина разлика је да морамо прва два реда иницијализовати нулама, и чувати пут израчунавања, што је, зависно да ли користимо E(i − 1,j), E(i,j − 1) или E(i − 1,j − 1) у израчунавању E(i, j).

У низу који садржи вредности E(x, y) одаберемо најмању вредност у последњем реду, нека је то E(x₂, y₂), и пратимо пут израчунавања уназад, све до нултог реда. Ако је поље до ког смо стигли E(0, y₁), онда је T[y₁ + 1] ... T[y₂] подниска од T са најмањим едит растојањем до обрасца P.

За израчунавање низа E(x, y) је потребно O(mn) времена користећи алгоритам који примењује динамичко програмирање, док за део тражења пута уназад треба O(n + m) времена.

Онлајн насупрот офлајн

Традиционално, алгоритми за приближно поклапање ниске се класификују у две категорије: онлајн и офлајн. Са онлајн алгоритмима образац се може обрадити пре претраге, али текст не може. Другим речима, онлајн технике раде претрагу без индекса. Рани алгоритми за онлајн приближно поклапање су предложени од стране Вагнера и Фишера и Селерса. Оба алгоритма су заснована на динамичком програмирању али решавају различите проблеме. Селерсов алгоритам претражује приближно за подниску у тексту, док алгоритам Вагнера и Фишера израчунава Левенштајново растојање и одговара једино за расплинуту претрагу речника.

Онлајн технике претраге су унапређиване у више наврата. Можда је најпознатије унапређење битап алготирам (такође познат као шифт-или и шифт-и алгоритам) који је веома ефикасан за релативно кратке ниске образаца. Битап алгоритам представља језгро Јуникс програмског алата за претрагу агреп. Преглед алгоритама за онлајн претрагу је урађен од стране Г. Навара.

Иако постоје веома брзе онлајн технике, њихов учинак на великим количинама података је неприхватљив. Претпроцесирање текста или индексирање чини претрагу драстично бржом. Данас постоји велики број алгоритама за индексирање. Међу њима су суфиксна стабла, метричка стабла и н-грам методе. Детаљан преглед техника индексирања које омогућавају проналажење произвољне подниске у тексту је дао Наваро et al.. Рачунарски преглед речничких метода (нпр. метода које омогућавају проналажење сви речи из речника које приближно одговарају обрасцу претраге) је дао Бојцов .

Примене

Најчешћа примена приближних поклапања до скора је била у провери писања. Са доступношћу великих количина ДНК података, веома важна примена је постала и проверавање поклапања секвенци нуклеотида. Приближно поклапање се такође користи у филтрирању непожељне имејл поште. Поклапање ниски се не може користити за већину бинарних података, као што су слике и музика. Они захтевају другачије алгоритме, као што је акустични отисак.

Види још

• Растојање уређивања
• Нидлмен-Ваншов алгоритам
• Смит-Ватерманов алгоритам
• Џаро–Винклерово растојање
• Левенштајново растојање
• Концептуална претрага
• Регуларни изрази за нерасплинуто (тачно) поклапање
• Метафон
• Саундекс
• Агреп
• Детекција плагијата

Референце

• ^ Baeza-Yates, R.; Navarro, G. (1996). „A faster algorithm for approximate string matching”. Ур.: Dan Hirchsberg; Gene Myers. Combinatorial Pattern Matching (CPM'96), LNCS 1075. Irvine, CA. стр. 1—23. 
• ^ Baeza-Yates R, Navarro G. „Fast Approximate String Matching in a Dictionary” (PDF). Proc. SPIRE'98. IEEE CS Press. стр. 14—22. 
• ^ Boytsov, Leonid (2011). „Indexing methods for approximate dictionary searching: Comparative analysis”. Jea Acm. 16 (1): 1—91. doi:10.1145/1963190.1963191. 
• ^ Cormen, Thomas; Leiserson, Rivest (2001). Introduction to Algorithms (2nd изд.). MIT Press. стр. 364–7. ISBN 978-0-262-03293-3. 
• ^ Galil, Zvi; Apostolico, Alberto (1997). Pattern matching algorithms. Oxford [Oxfordshire]: Oxford University Press. ISBN 978-0-19-511367-9. 
• ^ Gusfield, Dan (1997). Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge, UK: Cambridge University Press. ISBN 978-0-521-58519-4. 
• ^ G, Myers (1999). „A fast bit-vector algorithm for approximate string matching based on dynamic programming”. Journal of the ACM. 46 (3): 395—415. doi:10.1145/316542.316550. 
• ^ Navarro, Gonzalo (2001). „A guided tour to approximate string matching”. ACM Computing Surveys. 33 (1). doi:10.1145/375360.375365. CiteSeerX: 10.1.1.96.7225. 
• ^ Navarro, Gonzalo; Ricardo Baeza-Yates; E. Sutinen; J. Tarhio (2001). „Indexing Methods for Approximate String Matching” (PDF). IEEE Data Engineering Bulletin. 24 (4): 19—27. 
• ^ Sellers, Peter H. (1980). „The Theory and Computation of Evolutionary Distances: Pattern Recognition”. Journal of Algorithms. 1 (4): 359—73. doi:10.1016/0196-6774(80)90016-4. 
• ^ Skiena, Steve (1998). Algorithm Design Manual (1st изд.). Springer. ISBN 978-0-387-94860-7. 
• ^ E, Ukkonen (1985). „Algorithms for approximate string matching”. Information and Control. 64: 100—18. doi:10.1016/S0019-9958(85)80046-2. 
• ^ Wagner R, Fischer M (1974). „The string-to-string correction problem”. Journal of the ACM. 21: 168—73. doi:10.1145/321796.321811. 
• ^ J. Zobel, P. Dart. Finding approximate matches in large lexicons. Software-Practice & Experience 25(3). стр. 331–345, 1995.

Спољашње везе

• Flamingo Project
• Efficient Similarity Query Processing Project са скорашњим напретком у приближном поклапању ниски заснованом на растојању уређивања.
• StringMetric project Скала библиотека за метрике ниски и фонетске алгоритме
• Natural project Јаваскрипт библиотека за процесирање природних језика која укључује импементације популарних метрика ниски