een mogelijke definitie van de geschatte string matching probleem is de volgende: gegeven een patroon string P = p 1 p 2 . . . p m {\displaystyle P=p_{1}p_{2}…p_{m}}
en een tekst string T = t 1 t 2 … t n {\displaystyle T=t_{1}t_{2}\dots t_{n}}
, het vinden van een substring T j , j = t j ‘ … t j {\displaystyle T_{j,j}=t_{j}\dots t_{j}}
T, die, van alle substrings van T, is de kleinste bewerken afstand tot de patroon P.
Een brute-force aanpak zou zijn om te berekenen wat de edit distance to P voor alle substrings van T, en kies vervolgens de substring met de minimale afstand. Dit algoritme zou echter de looptijd O(n3 m) hebben.
een betere oplossing, die door verkopers werd voorgesteld, is gebaseerd op dynamisch programmeren. Het gebruikt een alternatieve formulering van het probleem: voor elke positie j in de tekst T en elke positie i in het patroon P, bereken de minimale bewerkingsafstand tussen de eerste I-tekens van het patroon, P I {\displaystyle P_{i}}
, en elke substring T j ‘, j {\displaystyle T_{j’,j}}
Van t die eindigt op positie J.
voor elke positie j in de tekst T, en elke positie i in het patroon P, ga door alle substrings van T eindigend op positie j, en bepaal welke van hen heeft de minimale afstand tot de I eerste tekens van het patroon P. schrijf deze minimale afstand als E (i, j). Na het berekenen van E(i, j) Voor alle i en j, kunnen we gemakkelijk een oplossing vinden voor het oorspronkelijke probleem: het is de substring waarvoor E (m, j) minimaal is(M is de lengte van het patroon P.)
Computing E (m, j) is zeer vergelijkbaar met het berekenen van de bewerkingsafstand tussen twee strings. In feite kunnen we het Levenshtein distance computing algoritme gebruiken voor E (m, j), het enige verschil is dat we de eerste rij met nullen moeten initialiseren en het pad van berekening moeten opslaan, dat wil zeggen of we E(i − 1, j), E(i,j − 1) of E(i − 1, j − 1) in de berekening van E(i,j) hebben gebruikt.
in de array die de E(x, y) waarden bevat, kiezen we dan de minimale waarde in de laatste rij, laten we het E(x2, y2) zijn, en volgen we het pad van berekening achterwaarts, terug naar het rijnummer 0. Als het veld waar we aankwamen E was (0, y1), dan T… T is een substring van T met de minimale bewerkingsafstand tot het patroon P.
Het berekenen van de E(x, y) array neemt o(mn) tijd in beslag met het dynamische programmeeralgoritme, terwijl de achterwaarts werkende fase O(n + m) tijd in beslag neemt.
een ander recent idee is de similarity join. Wanneer de matching database betrekking heeft op een grote schaal van gegevens, kan de O(mn) tijd met het dynamische programmeeralgoritme niet werken binnen een beperkte tijd. Dus, het idee is, in plaats van het berekenen van de gelijkenis van alle paren van snaren, om het aantal kandidaat paren te verminderen. Veelgebruikte algoritmen zijn gebaseerd op filterverificatie, hashing, Locality-sensitive hashing (LSH), Try ‘ s en andere hebzuchtige en benaderingsalgoritmen. De meeste van hen zijn ontworpen om een raamwerk (zoals Map-Reduce) te passen om gelijktijdig te berekenen.