Wasige stringpassing

In rekenaarwetenskap is wasige stringpassing of wasige stringsoektog 'n tegniek om karakterstringe te soek wat 'n patroon min-of-meer pas (eerder as presies). Die probleem van wasige stringpassing word tipies in twee subprobleme verdeel: die vind van benaderde substringpassings in 'n gegewe string, en die vind van woordeboekstringe wat min-of-meer pas by die soekpatroon.

Oorsig

Die nabyheid van 'n passing word gemeet in terme van die aantal primitiewe bewerkings wat nodig is om die string om te skakel in 'n presiese passing. Dié getal word die redigeerafstand genoem tussen die string en die patroon.

invoeging: bok → boek
skrap: boek → bok
vervanging: boek → boet

Hierdie drie bewerkings kan veralgemeen word as vorme van vervanging deur 'n NULL-karakter (hier aangedui met *) waar 'n karakter geskrap of ingevoeg word:

invoeging: bo*k → boek
skrap: boek → bo*k
vervanging: boek → boet

Wasige passing kan ook transposisie hanteer, waarin die posisies van twee letters in die string omgeruil word, as 'n primitiewe bewerking. Die verandering van boet na bote is 'n voorbeeld van transposisie.

Verskillende benaderings tot wasige passing kan verskillende beperkings stel. Sommige gebruik 'n enkele globale ongeweegde koste, dit wil sê, die totale aantal primitiewe bewerkings wat nodig is om die passing in die patroon te verander. By voorbeeld, as die patroon boek is, verskil boet met een vervanging, boeke met een invoeging, bok met een skrapping en plek met twee vervangings. As alle bewerkings tel as 'n enkele eenheidkoste en die drempel is op een gestel, sal boet, boeke en bok pas en plek sal nie.

Ander benaderings spesifiseer die aantal bewerkings van elke soort apart, en ander weer stel 'n totale koste maar laat verskillende gewigte toe om toegeken te word aan verskillende bewerkings. Sommige benaderings laat aparte toekenning toe aan individuele groepe in die patroon wat drempels en gewigte betref.

Probleemformulering en algoritmes

Een moontlike definisie van die probleem van wasige stringpassing is die volgende: Gegewe 'n patroonstring $P=p_{1}p_{2}...p_{m}$ en 'n teksstring $T=t_{1}t_{2}\dots t_{n}$ , vind 'n substring $T_{j',j}=t_{j'}\dots t_{j}$ in T, wat, vir alle substringe van T die kleinste redigeerafstand het tot die patroon P.

'n Brutekragbenadering sal behels om die redigeerafstand na P te bereken vir alle substringe van T en dan die substring te kies met die minimumafstand. Dié algoritme sal egter 'n looptyd hê van O(n³m).

'n Beter oplossing wat deur Sellers voorgestel is, maak staat op dinamiese programmering. Dit gebruik 'n alternatiewe formulering van die probleem: vir elke posisie j in die teks T en elke posisie i in die patroon P, bereken die minimumredigeerafstand tussen die i eerste karakters van die patroon $P_{i}$ en enige substring $T_{j',j}$ van T wat eindig by posisie j.

Vir elke posisie j in die teks T, en elke posisie i in die patroon P, gaan deur alle substringe van T wat eindig by posisie j, en bepaal watter een van hulle het die kleinste redigeerafstand na die i eerste karakters van die patroon P. Skryf dié kleinste afstand as E(i, j). Na die berekening van E(i, j) vir alle i en j kan ons maklik 'n oplossing vir die oorspronklike probleem vind: dit is die substring waarvoor E(m, j) die kleinste is (m is die lengte van die patroon P.)

Die berekening van E(m, j) is baie soortgelyk aan die berekening van die redigeerafstand tussen die twee stringe. Om die waarheid te sê, ons kan die algoritme vir berekening van die Levenshtein-afstand gebruik vir E(m, j), met die enigste verskil dat ons die eerste ry met nulle moet inisialiseer, en die pad van berekening moet stoor, d.w.s. of ons E(i − 1,j), E(i,j − 1) of E(i − 1,j − 1) gebruik het om E(i, j) te bereken.

In die skikking wat die E(x, y)-waardes bevat, kies ons die kleinste waarde in die laaste ry, stel dit as E(x₂, y₂), en volg die pad van berekening agteruit, terug na ry nommer 0. As die veld waar ons aankom E(0, y₁) was, dan is T[y₁ + 1] ... T[y₂] 'n substring van T met die kleinste redigeerafstand na die patroon P.

Die berekening van die E(x, y)-skikking neem O(mn) in tyd met die dinameseprogrammeringalgoritme, terwyl die terugwerkfase O(n + m) in tyd neem.

Aanlyn teenoor vanlyn

Tradisioneel word wasige stringpassing geklassifiseer in twee kategorieë: aanlyn en vanlyn. Met die aanlynalgoritmes kan die patroon verwerk word voordat die soektog gedoen word, maar die teks kan nie. Met ander woorde, aanlyntegnieke soek sonder 'n indeks. Vroeë algoritmes vir aanlyn wasige stringpassing is voorgestel deur Wagner en Fisher en deur Sellers. Altwee algoritmes is gebaseer op dinamiese programmering maar los verskillende probleme op. Sellers se algoritme soek by benadering na 'n substring in 'n teks terwyl die algoritme van Wagner en Fisher die Levenshtein-afstand bereken, en is dus slegs gepas vir "woordeboek" wasige soek.

Aanlyntegnieke is herhaaldelik verbeter. Moontlik die mees bekende verbetering is die Bitap-algoritme (ook bekend as die shift-or- en shift-and-algoritme) wat baie doeltreffend is vir relatief kort patroonstringe. Die Bitap-algoritme is die hart van die soekprogram agrep vir Unix. 'n Oorsig van aanlyn-soekalgoritmes is gedoen deur G. Navarro.

Alhoewel blitsvinnige metodes bestaan, is hul werkverrigting op groot data onaanvaarbaar. Voorafverwerking van die teks of indeksering maak soektogte aansienlik vinniger. Daar is reeds 'n verskeidenheid van indekseringsalgoritmes voorgestel. Dit sluit in suffiksbome, metrieke bome en n-gram-metodes. 'n Gedetailleerde oorsig van indekseringstegnieke wat die vind van arbitrêre substringe in 'n teks toelaat, is gegee deur Navarro et al.. 'n Oorsig van woordeboekmetodes (d.w.s. metodes wat mens toelaat om alle woordeboekinskrywings te vind wat by benadering by 'n soekpatroon pas) is gegee deur Boytsov.

Toepassings

Die algemeenste toepassing van wasige passing tot onlangs was speltoetsing. Met die beskikbaarheid van groot hoeveelhede DNS-data het die passing van nukleotiedkettings 'n belangrike toepassing geword. Wasige passing word ook gebruik in die filtrering van gemorspos. Stringpassing kan nie gebruik word vir meeste binêre data soos beelde en musiek nie. Dié data benodig ander algoritmes soos akoestiese vingerafdrukke.