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

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

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

Преглед

уреди

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

  • додавање: cotcoat
  • брисање: coatcot
  • замена: coatcost

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

  • додавање: co*tcoat
  • брисање: coatco*t
  • замена: coatcost

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

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

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

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

уреди

Једна могућа дефиниција приближног поклапања ниске је следећа: Дата је ниска обрасца:   и ниска текста  , пронаћи подниску   у T, који има најмање едит растојање до обрасца P од свих могућих подниски у T.

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

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

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

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

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

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

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

уреди

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

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

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

Примене

уреди

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

Види још

уреди

Референце

уреди

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

уреди