en mulig definition af det omtrentlige strengtilpasningsproblem er følgende: givet en mønsterstreng P = p 1 p 2 . . . p m {\displaystyle P=p_{1}p_{2}…p_{m}}
og en tekststreng T = t 1 t 2 … t n {\displaystyle T=t_{1}T_{2}\dots t_{n}}
, find en substring T j ‘, j = t j ‘… t j {\displaystyle T_{j’,J}=T_{J’}\dots T_{J}}
i T, som af alle substrings af T har den mindste redigeringsafstand til mønsteret P.
en brute-force-tilgang ville være at beregne redigeringsafstanden til P for alle substrings af T, og vælg derefter Substringen med den mindste afstand. Denne algoritme ville dog have driftstiden O(n3 m).
en bedre løsning, som blev foreslået af sælgere, er afhængig af dynamisk programmering. Det bruger en alternativ formulering af problemet: for hver position j i teksten T og hver position i i mønsteret P, beregne den mindste redigeringsafstand mellem de første tegn i mønsteret, P i {\displaystyle p_{i}}
og enhver substring T j’, j {\displaystyle T_{j’, j}}
af T,der slutter ved position J.
for hver position j i teksten T og hver position i i mønsteret P skal du gennemgå alle understrenge af T, der slutter i position j, og bestemme, hvilken af dem der har den minimaledit Afstand til i første tegn i mønsteret P. skriv denne minimale afstand som E(i, j). Efter beregning af E (I, j) for alle i og j, kan vi let finde en løsning på det oprindelige problem: det er den substring, for hvilken E(m, j) er minimal (m er længden af mønsteret P.)
Computing E(m, j) ligner meget at beregne redigeringsafstanden mellem to strenge. Faktisk kan vi bruge Levenshtein-afstandsberegningsalgoritmen til E(m, j), den eneste forskel er, at vi skal initialisere den første række med nuller og gemme beregningsstien, det vil sige, om vi brugte E(i − 1,j), E(I,j − 1) eller E(i − 1,j − 1) i computing E (I, j).
i arrayet, der indeholder værdierne E(H, y), vælger vi derefter den minimale værdi i den sidste række, lad den være E(H2, y2) og følger beregningsstien baglæns, tilbage til række nummer 0. Hvis feltet vi ankom til var E (0, y1), så T … T er en substring af T med den minimale redigeringsafstand til mønsteret P.
beregning af e-arrayet tager O(mn) tid med den dynamiske programmeringsalgoritme, mens den bagudgående arbejdsfase tager o(n + m) tid.
en anden nylig ide er ligheden deltage. Når matchende database vedrører en stor skala af data, kan o (mn) – tiden med den dynamiske programmeringsalgoritme ikke fungere inden for en begrænset tid. Så ideen er, i stedet for at beregne ligheden mellem alle par strenge, at reducere antallet af kandidatpar. Udbredte algoritmer er baseret på filter-verifikation, hashing, Lokalitetsfølsom hashing (LSH), forsøg og andre grådige og tilnærmelsesalgoritmer. De fleste af dem er designet til at passe til nogle rammer (såsom Map-reducer) for at beregne samtidigt.