Back

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




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

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

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

                                     

1. Преглед

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

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

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

                                     

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

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

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

Боље решење, које је предложио Селерс подниска од T са најмањим едит растојањем до обрасца P.

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

                                     

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

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

                                     

4. Примене

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

                                     

5. Види још

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

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

  • Efficient Similarity Query Processing Project са скорашњим напретком у приближном поклапању ниски заснованом на растојању уређивања.
  • StringMetric project Скала библиотека за метрике ниски и фонетске алгоритме
  • Flamingo Project
  • Natural project Јаваскрипт библиотека за процесирање природних језика која укључује импементације популарних метрика ниски
                                     
  • Лисер нем. Robert Lusser је изабрао овај мотор, због једноставности, ниске цене и јефтине масовне производње. То је било исплативо за дотичну једнократну
  • dinamički konturni tonometar ima konturisani tonometrijski vrh koji služi za poklapanje sa konturom rožnjače. Radijus zakrivljenosti vrha je 10, 5 mm, a kontaktna
  • индикацију и праксу психоаналитичке терапије за полазнике у анализи. Поклапање аналитичара и пацијента може се посматрати као још један фактор који доприноси
  • Овакав маневар обезбеђује практично најповољнију могућност, за брзо поклапање линије нишањења са циљем, за најмањи губитак висине, у стрмом обрушавању

Users also searched:

...