o posibilă definiție a problemei aproximative de potrivire a șirului este următoarea: dat un șir de model P = p 1 p 2 . . . p m {\displaystyle P = p_{1}p_{2}…p_{m}}
și un șir de text T = t 1 t 2 … t n {\displaystyle T=t_{1}t_{2}\puncte t_{n}}
, găsiți un subșir T j ‘, j = t j ‘… t j {\displaystyle t_{j’,J}=t_{J’}\dots t_{J}}
în T, care, dintre toate subșirurile lui T, are cea mai mică distanță de editare față de modelul P.
o abordare a forței brute ar fi calcularea distanței de editare la P pentru toate subșirurile lui T, apoi distanța. Cu toate acestea, acest algoritm ar avea timpul de funcționare O(n3 m).
o soluție mai bună, propusă de vânzători, se bazează pe programarea dinamică. Folosește o formulare alternativă a problemei: pentru fiecare poziție j din textul T și fiecare poziție i din modelul P, calculați distanța minimă de editare dintre primele caractere i ale modelului, P I {\displaystyle p_{i}}
și orice subșir T j’, j {\displaystyle t_{j’, j}}
de t care se termină în poziția J.
pentru fiecare poziție j din textul T și fiecare poziție i din modelul P, parcurgeți toate subșirurile T care se termină în poziția j și determinați care dintre ele are Distanța minimaledit până la primele caractere i ale modelului P. scrieți această distanță minimă ca E(i, j). După calculul E (i, j) Pentru toți i și j, putem găsi cu ușurință o soluție la problema inițială: este substringul pentru care E(m, j) este minim (m fiind lungimea modelului P.)
calculul E(M, j) este foarte similar cu calculul distanței de editare dintre două șiruri. De fapt, putem folosi algoritmul de calcul la distanță Levenshtein pentru e(m, j), singura diferență fiind că trebuie să inițializăm primul rând cu zerouri și să salvăm calea de calcul, adică dacă am folosit e(i − 1, j), e(i, j − 1) sau E(i − 1,j − 1) în calculul E(i,j).
în matricea care conține valorile E(x, y), alegem apoi valoarea minimă din ultimul rând, lăsați-o să fie E(x2, y2) și urmați calea de calcul înapoi, înapoi la numărul rândului 0. Dacă câmpul la care am ajuns a fost E(0, y1), atunci T … T este un subșir de T cu distanța minimă de editare față de modelul P.
calculul matricei E(x, y) durează O(mn) timp cu algoritmul de programare dinamică, în timp ce faza de lucru înapoi durează O(n + m) timp.
o altă idee recentă este similaritatea se alăture. Când potrivirea bazei de date se referă la o scară largă de date, timpul O(mn) cu algoritmul de programare dinamică nu poate funcționa într-un timp limitat. Deci, ideea este, în loc să calculăm similitudinea tuturor perechilor de șiruri, să reducem numărul de perechi candidate. Algoritmii utilizați pe scară largă se bazează pe verificarea filtrului, hashing, hashing sensibil la localitate (LSH), încercări și alți algoritmi greedy și aproximation. Cele mai multe dintre ele sunt concepute pentru a se potrivi unele cadru (cum ar fi harta-Reduce) pentru a calcula concomitent.