a hozzávetőleges karakterlánc-illesztési probléma egyik lehetséges meghatározása a következő: adott minta karakterlánc P = p 1 p 2 . . . p m {\displaystyle P=p_{1}p_{2}…p_{m}}
és egy T = t 1 t 2 … t n {\displaystyle T=t_{1}t_{2}\dots t_{n}}
, keresse meg a T J ‘, j = t j ‘… t J {\displaystyle t_{j’,J}=T_{J’}\Dots T_{J}}
a T-ben, amely a T összes alrésze közül a legkisebb szerkesztési távolsággal rendelkezik a p mintához képest.
a brute-force megközelítés az lenne, ha kiszámolnánk a szerkesztési távolságot p-ig a t összes alrészénél, majd kiválasztanánk a minimális távolság. Ennek az algoritmusnak azonban o(n3 m) futási ideje lenne.
az eladók által javasolt jobb megoldás a dinamikus programozásra támaszkodik. A probléma alternatív megfogalmazását használja: a T szöveg minden egyes J pozíciójához és a P minta minden egyes i pozíciójához számítsa ki a minta i első karakterei közötti minimális szerkesztési távolságot, P i {\displaystyle P_{i}}
és bármely T J’, j {\displaystyle T_{j’, j}}
t,amely a j pozícióban végződik.
A t szöveg minden J pozíciójához és a P minta minden I pozíciójához menjen végig a T összes alrészén, amely a j pozícióban végződik, és határozza meg, hogy melyiküknek van a minimaledit távolsága a P minta i első karakteréhez.írja be ezt a minimális távolságot E(i, j) néven. Az E(i, j) kiszámítása után minden i és j esetében könnyen megoldást találhatunk az eredeti problémára: ez az a részstring, amelyre E(m, j) minimális (m a minta hossza P.)
Az E(m, j) számítás nagyon hasonlít a két karakterlánc közötti szerkesztési távolság kiszámításához. Valójában használhatjuk a Levenshtein távolságszámítási algoritmust az E(m, j) számára, az egyetlen különbség az, hogy az első sort nullákkal kell inicializálnunk, és meg kell mentenünk a számítási utat, vagyis hogy E(i − 1,j), E(i,j − 1) vagy E(i − 1,j − 1) – t használtunk-e az e(i, j) számítástechnikában.
az E(x, y) értékeket tartalmazó tömbben ezután kiválasztjuk az utolsó sor minimális értékét, legyen az E(x2, y2), és kövessük a számítás útját visszafelé, vissza a 0 sorszámra. Ha a mező, amelyre megérkeztünk, E volt(0, y1), akkor T …
Az E(x, y) tömb kiszámítása O(mn) időt vesz igénybe a dinamikus programozási algoritmussal, míg a visszafelé működő fázis O(n + m) időt vesz igénybe.
egy másik friss ötlet a hasonlóság csatlakozzon. Ha az adatbázis egyeztetése nagy mennyiségű adatra vonatkozik, az O (mn) idő a dinamikus programozási algoritmussal nem működhet korlátozott időn belül. Tehát az ötlet az, hogy az összes húrpár hasonlóságának kiszámítása helyett csökkentse a jelölt párok számát. A széles körben használt algoritmusok a szűrő-ellenőrzés, a hash, a lokalitás-érzékeny hash (LSH), a Tries és más mohó és közelítő algoritmusokon alapulnak. Legtöbbjük úgy van kialakítva, hogy illeszkedjen valamilyen keretrendszerhez (például a Map-Reduce-hoz), hogy egyidejűleg kiszámítsa.