en möjlig definition av det ungefärliga strängmatchningsproblemet är följande: givet en mönstersträng P = p 1 p 2 . . . p m {\displaystyle P=p_{1}p_{2}…p_{m}}
och en textsträng T = T 1 t 2 … TN {\displaystyle t=t_{1}t_{2}\dots t_{n}}
, hitta en substring T j ’, j = t j ’… tj {\displaystyle t_{j’,J}=T_{J’}\Dots T_{j}}
i T, som av alla delsträngar av T har det minsta redigeringsavståndet till mönstret P.
ett brute-force-tillvägagångssätt skulle vara att beräkna redigeringsavståndet till P för alla delsträngar av T och sedan välja Delsträngen med det minsta avstånd. Denna algoritm skulle dock ha körtiden O (n3 m).
en bättre lösning, som föreslogs av säljare, bygger på dynamisk programmering. Den använder en Alternativ formulering av problemet: för varje position j i texten T och varje position i i mönstret P, beräkna det minsta redigeringsavståndet mellan de första tecknen i mönstret, P I {\displaystyle P_{i}}
och varje delsträng T j’, j {\displaystyle t_{j’, j}}
av T som slutar vid position J.
för varje position j i texten T och varje position i i mönstret P, gå igenom alla delsträngar av T som slutar vid position j och bestäm vilken av dem som har minimaledit avstånd till de första tecknen i mönstret P. Skriv detta minimala avstånd som E(I, j). Efter beräkning av E(I, j) för alla i och j kan vi enkelt hitta en lösning på det ursprungliga problemet: det är den delsträng för vilken E(m, j) är minimal (m är längden på mönstret P.)
beräkning av E(M, j) är mycket lik beräkning av redigeringsavståndet mellan två strängar. Faktum är att vi kan använda levenshteins avståndsberäkningsalgoritm för E(m, j), den enda skillnaden är att vi måste initiera den första raden med nollor och spara beräkningsvägen, det vill säga om vi använde E(i − 1, j), E(I,j − 1) eller E(i − 1, j − 1) i beräkning E(I,j).
i matrisen som innehåller E(x, y) – värdena väljer vi sedan minimivärdet i sista raden, låt det vara E (x2, y2) och följ beräkningsvägen bakåt, tillbaka till radnumret 0. Om fältet vi anlände till var E (0, y1), då T … T är en delsträng av T med minimalt redigeringsavstånd till mönstret P.
beräkning av E(x, y) array tar O(mn) tid med den dynamiska programmeringsalgoritmen, medan bakåtarbetsfasen tar O(n + m) tid.
en annan ny ide är likheten gå med. När matchande databas avser en stor skala av data, O (mn) tid med den dynamiska programmeringsalgoritmen kan inte fungera inom en begränsad tid. Så tanken är, istället för att beräkna likheten hos alla par strängar, att minska antalet kandidatpar. Ofta använda algoritmer är baserade på filterverifiering, hashing, Lokalitet-känslig hashing (LSH), försök och andra giriga och approximationsalgoritmer. De flesta av dem är utformade för att passa vissa ramar (som Map-Reduce) för att beräkna samtidigt.