en mulig definisjon av omtrentlig string matching problemet er følgende: Gitt et mønster streng P = p 1 p 2 . . . p {\displaystyle p=p_{1}p_ {2}…p_{m}}
og en tekststreng T = t 1 t 2 … t n {\displaystyle t=t_{1}t_{2}\prikker t_{n}}
, finn en substring t j ‘, j = t j ‘… t j {\displaystyle t_{j’,j}=t_{j’}\dots t_{j}}
i t, som Av alle delstrenger av t har den minste redigeringsavstanden til mønsteret p.
en brute-force tilnærming ville Være Å Beregne redigeringsavstanden til p for alle delstrenger av t, og velg Deretter Delstrengen med minimumsavstanden. Denne algoritmen vil imidlertid ha kjøretiden O (n3 m).
en bedre løsning, som Ble foreslått Av Selgere, er avhengig av dynamisk programmering. Den bruker en alternativ formulering av problemet: for hver posisjon j I teksten T og hver posisjon i i mønsteret P, beregne den minste redigeringsavstanden mellom de første tegnene i mønsteret, p i {\displaystyle p_{i}}
, og enhver substring t j ‘, j {\displaystyle t_{j’,j}}
av t som ender i posisjon j.
for hver posisjon j I teksten T, og hver posisjon i i mønsteret P, gå gjennom alle delstrenger Av T som slutter i posisjon j, og avgjøre hvilken av dem som har minimalrediger avstand til de første tegnene I mønsteret P. Skriv denne minimale avstanden Som E(i, j). Etter å ha beregnet E (i, j) for alle i og j, kan vi lett finne en løsning på det opprinnelige problemet: Det er substringen Som E(m, j) er minimal (m er lengden På mønsteret P.)
Databehandling E(m, j) ligner veldig på å beregne redigeringsavstanden mellom to strenger. Faktisk kan Vi bruke Levenshtein avstandsberegningsalgoritmen For E (m, j), den eneste forskjellen er at vi må initialisere den første raden med nuller og lagre beregningsbanen, det vil si om Vi brukte E(i − 1, j), E(i,j − 1) eller E(i − 1, j − 1) i databehandling E(i,j).
i matrisen som inneholder e (x, y) verdiene, velger vi deretter minimumsverdien i siste rad, la Den Være E (x2, y2), og følg beregningsbanen bakover, tilbake til radnummer 0. Hvis feltet vi ankom Var E (0, y1), så T … T Er en substring Av T med minimal redigeringsavstand Til mønsteret P.
Databehandling Av e (x, y) – matrisen tar O (mn) tid med den dynamiske programmeringsalgoritmen, mens bakoverarbeidsfasen tar O (n + m) tid.
En annen ny ide er likheten bli med. Når samsvarende database er relatert til en stor skala av data, Kan O (mn) tid med dynamisk programmeringsalgoritme ikke fungere innen en begrenset tid. Så, ideen er, i stedet for å beregne likheten til alle par av strenger, å redusere antall kandidatpar. Mye brukt algoritmer er basert på filter-verifisering, hashing, Lokalitet-sensitive hashing (LSH), Prøver og andre grådige og tilnærming algoritmer. De fleste av dem er utformet for å passe noen rammeverk (For Eksempel Map-Redusere) for å beregne samtidig.