Jedním z možných vymezení přibližné řetězec odpovídající problém je následující: Vzhledem k tomu, vzor, string P = p 1 p 2 . . . p m {\displaystyle P=p_{1}p_{2}…p_{m}}
a textový řetězec T = t 1 t 2 … t n {\displaystyle T=t_{1}a t_{2}\dots t_{n}}
, najít podřetězec T j ‚, j = t j t j {\displaystyle T_{j,j}=t_{j‘}\dots t_{j}}
v T, které, ze všech řetězců z T, má nejmenší upravit vzdálenost vzoru P.
brute-force přístup by byl pro výpočet upravit vzdálenost k P pro všechny podřetězce T, a pak si vybrat podřetězec s minimální vzdálenosti. Tento algoritmus by však měl provozní dobu O (n3 m).
lepší řešení, které navrhli prodejci, se spoléhá na dynamické programování. To používá alternativní formulace problému: pro každou pozici j v textu T a každou pozici i v poli P, výpočet minimální upravit vzdálenost mezi jsem první znaky vzoru, P i {\displaystyle P_{i}}
, a jakékoliv podřetězec T j ‚ , j {\displaystyle T_{j,j}}
T, která končí na pozici j.
Pro každou pozici j v textu T, a každou pozici i v poli P, projít všechny podřetězce T-končí na pozici j, a určit, který z nich má minimaledit vzdálenost na poprvé jsem znaků vzoru P. Psát tato minimální vzdálenost jako E(i, j). Po výpočtu E(i, j) pro všechna i a j, můžeme snadno najít řešení na původní problém: to je podřetězec, pro které E(m, j) je minimální (kde m je délka vzoru P.)
Computing E(m, j) je velmi podobný výpočetní upravit vzdálenosti mezi dvěma řetězci. Ve skutečnosti, můžeme použít Levenshteinova vzdálenost výpočetní algoritmus pro E(m, j), jediný rozdíl je, že musíme inicializovat první řadě s nulami, a uložit cestu výpočtu, to znamená, zda jsme E(i − 1,j), E(i,j − 1) nebo E(i − 1,j − 1) v oblasti výpočetní techniky E(i, j).
V pole obsahující E(x, y) hodnot, jsme pak zvolte minimální hodnotu v posledním řádku, ať je E(x2, y2), a následovat cestu výpočtu, zpět na řádku číslo 0. Pokud pole, na které jsme dorazili, bylo E (0, y1), pak T … T je řetězec, T s minimální upravit vzdálenost vzoru P.
výpočet E(x, y) pole trvá O(mn) čas s dynamické programování algoritmus, zatímco obráceně-pracovní fáze trvá O(n + m) času.
dalším nedávným nápadem je podobnost join. Pokud se odpovídající databáze týká velkého rozsahu dat, o (mn) čas s algoritmem dynamického programování nemůže fungovat v omezeném čase. Myšlenka je tedy namísto výpočtu podobnosti všech párů řetězců snížit počet kandidátských párů. Široce používané algoritmy jsou založeny na ověření filtru, hashování, hashování citlivém na lokalitu (LSH), pokusech a dalších chamtivých a aproximačních algoritmech. Většina z nich jsou navrženy tak, aby se vešly nějaký rámec (například Map-Reduce) pro výpočet souběžně.