yksi mahdollinen määritelmä likimääräiselle merkkijonosovitusongelmalle on seuraava: annetaan kuviomerkkijono P = p 1 p 2 . . . p m {\displaystyle p=p_{1}p_{2}…p_{m}}
ja tekstijono T = t 1 t 2 … T n {\displaystyle T=t_{1}t_{2}\dots t_{n}}
, etsi substraatti T j ’, j = t j ’… t j {\displaystyle T_{j’,j}=t_{J’}\Dots T_{J}}
in t, jolla on kaikista T: n substraateista pienin muokkausetäisyys kuvioon P.
brute-force-lähestymistapa olisi laskea muokkausetäisyys arvoon P kaikille t: n substraateille ja valita sitten substraatti, jolla on pienin etäisyys. Tällä algoritmilla olisi kuitenkin käyntiaika O (n3 m).
Sellersin ehdottama parempi ratkaisu nojaa dynaamiseen ohjelmointiin. Se käyttää ongelman vaihtoehtoista muotoilua: jokaista kohtaa J tekstissä t ja jokaista kohtaa I kuviossa P lasketaan pienin muokkausetäisyys kuvion I ensimmäisten merkkien välillä, P i {\displaystyle P_{i}}
, ja minkä tahansa substraatin t j’, j {\displaystyle T_{j’, j}}
T_{J’, J}t,joka päättyy asemaan J.
kunkin kannan J tekstissä t, ja kunkin kannan i kuvion P, käydä läpi kaikki Alustat T päättyen asentoon j, ja määrittää, kumpi niistä on pienin etäisyys I ensimmäiset merkit kuvio P. kirjoita tämä minimaalinen etäisyys e (i, j). Kun laskenta e(i, j) kaikille i ja j, voimme helposti löytää ratkaisun alkuperäiseen ongelmaan: se on substring, jolle E(m, j) on minimaalinen (m on pituus kuvio P.)
Computing E(m, j) on hyvin samanlainen computing edit etäisyys kahden merkkijonoja. Itse asiassa voimme käyttää Levenshtein etäisyys computing algoritmi E(m, j), ainoa ero on, että meidän täytyy alustaa ensimmäisen rivin nollilla, ja tallentaa polku laskenta, eli onko me käytetty e(i − 1,j), e(i,j − 1) tai E(i − 1,j − 1) computing E (i, j).
e(x, y) – arvot sisältävässä rivissä valitaan sitten viimeisellä rivillä minimiarvo, olkoon se e(x2, y2) ja seurataan laskennan polkua taaksepäin, takaisin rivinumeroon 0. Jos kenttä saavuimme oli E (0, y1), sitten T … T on T: n substraatti, jolla on pienin muokkausetäisyys kuvioon P.
E(x, y)-matriisin laskenta vie dynaamisella ohjelmointialgoritmilla O(mn) – aikaa, kun taas taaksepäin työskentely-vaihe vie O(n + m) – aikaa.
toinen tuore ajatus on samankaltaisuusliittymä. Kun tietokannassa on kyse suuresta tietomäärästä, O(mn) – aika dynaamisen ohjelmointialgoritmin kanssa ei voi toimia rajoitetussa ajassa. Niinpä ideana on, sen sijaan, että laskettaisiin kaikkien merkkijonoparien samankaltaisuus, vähentää ehdokasparien määrää. Laajalti käytetyt algoritmit perustuvat suodatinvarmennukseen, tiivistämiseen, Paikallissensitiiviseen tiivistämiseen (LSH), kokeiluihin ja muihin ahneisiin ja likiarviointialgoritmeihin. Useimmat niistä on suunniteltu sopimaan johonkin kehykseen (kuten kartta-vähentää) laskea samanaikaisesti.