String correctie met behulp van de Damerau-Levenshtein afstand

Single-core algoritmen

In deze sectie ontwikkelen we vier lineaire-ruimte single-core algoritmen voor string correctie met behulp van de DL afstand. Alle vier werken in O(mn) tijd. De eerste twee (LS_DL en Strip_DL) berekenen alleen de score Hmn van het optimale spoor; ze verschillen in hun cache-efficiëntie. De laatste twee (LSDL_TRACE en Strip_TRACE) berekenen een optimaal spoor.

Het lineaire ruimte-algoritme L S_D L

Laat s de grootte van het alfabet zijn. In plaats van de matrix H die in DL wordt gebruikt, gebruikt algoritme LS_DL een eendimensionale matrix U en een tweedimensionale matrix T. Deze twee matrices hebben een ruimtebeslag van O((s+1)n) = O(n) voor constante s. Als m<n, kan men A en B verwisselen om het benodigde geheugen te verminderen. Als het voor A en B benodigde geheugen wordt opgeteld, is de ruimte-complexiteit O(s min{m,n}+m+n) = O(m+n) als s een constante is.

Zoals in algoritme DL worden de Hij-waarden per rij berekend. De eendimensionale matrix U wordt gebruikt om de door algoritme DL berekende H-waarden op te slaan wanneer rij i wordt berekend. Zij H de laatste rij die berekend is voor teken c. Dan is T rij w-1 van H. Algoritme 2 geeft de pseudocode voor LS_DL. De juistheid ervan volgt uit de juistheid van algoritme DL. Merk op dat swap(T],U) O(1) tijd kost omdat pointers naar 2 een-dimensionale arrays worden verwisseld en niet de inhoud van deze arrays. Het aantal cache-miss voor LS_DL is hetzelfde als dat voor DL wanneer n voldoende groot is, aangezien beide hetzelfde gegevenstoegangspatroon hebben. Voor kleinere gevallen zal LS_DL echter een veel beter cache-gedrag vertonen. Bijvoorbeeld, omdat het veel minder geheugen gebruikt, kunnen we genoeg LLC cache hebben om alle gegevens in LS_DL op te slaan maar niet in DL (O(sn) vs O(mn)).

Het cache-efficiënte lineaire-ruimte-algoritme S t r i p_D L

Wanneer (s+1)n groter is dan de grootte van de LLC cache, kunnen we cache misses ten opzichte van algoritme LS_DL verminderen door Hij te berekenen met stroken van breedte q, voor sommige q kleiner dan n (de laatste strook kan een breedte hebben die kleiner is dan q). Dit wordt getoond in Fig. 3. De stroken worden berekend in de volgorde 0, 1, … met algoritme LS_DL. De ruimte die T en U in LS_DL nodig hebben wordt echter gereduceerd tot (s+1)q omdat de strookbreedte q is in plaats van n. Door q klein genoeg te kiezen, kunnen we ervoor zorgen dat blokken van de T- en U-arrays die door LS_DL worden gebruikt, niet uit de cache worden verwijderd zodra ze zijn binnengehaald. Dus, als elke invoer van T en U 1 woord in beslag neemt, dan hebben we, als de cache grootte lw is, q<lw/(s+1). Merk op dat, naast T en U, de cache partials van A, B en andere arrays moet bevatten die nodig zijn om de gegevens van de ene strook naar de volgende door te geven.

H berekenen met stroken

Om de gegevens van de ene strook naar de volgende door te geven, gebruiken we een extra eendimensionale matrixstrook van grootte m en een tweedimensionale s∗m matrix V. De matrixstrook bevat de waarden van H die berekend zijn voor de meest rechtse kolom in de strook. V geeft de H-waarde in de meest rechtse kolom j van rij i van H die (a) in een strook links van de strook staat die op dat moment wordt berekend en (b) c=B.

De pseudocode voor Strip_DL staat in Algorithm 3. Voor de duidelijkheid worden in deze pseudocode twee strip-arrays (regel 18 en 30) en twee V-arrays (regel 24 en 32) gebruikt. De ene set arrays wordt gebruikt voor het ophalen van gegevens die voor de vorige strook zijn berekend en de andere set voor gegevens die aan de volgende strook moeten worden doorgegeven. In de werkelijke implementatie gebruiken we een enkele strook-array en een enkele V-array voor het overschrijven van waarden die van de vorige strook zijn ontvangen met waarden die aan de volgende strook moeten worden doorgegeven.

De tijd en complexiteit van Strip_DL zijn respectievelijk O(mn) en O((s+1)m+(s+1)q+n) = O(sm+sq+n) = O(sm+n) omdat q een constante is. Wanneer m>n, kunnen we A en B verwisselen om geheugen te sparen en zo wordt de ruimte complexiteit O(s min{m,n}+m+n) = O(m+n) voor constante s.

Wanneer we de cache miss analyseren, merken we op dat q zo gekozen is dat U en T in de cache passen. We nemen de redelijke aanname dat de LRU-vervangingsregel er niet toe leidt dat een blok U of T wordt uitgezet tijdens het uitvoeren van algoritme Strip_DL. Het totale aantal cache misses als gevolg van U en T is dus onafhankelijk van m en n en kan dus in de analyse worden genegeerd. De initialisatie van Strip en V resulteert in respectievelijk m/w en (s+1)m/w leestoegang. Het aantal schrijftoegangen is ongeveer gelijk aan het aantal leestoegangen. De berekening voor elke strook benadert de matrixstrook in oplopende volgorde van index. Dit resulteert in (ongeveer) hetzelfde aantal cache misses als gemaakt tijdens de initialisatie fase. Het totale aantal cache misses als gevolg van de strook is dus ongeveer (2m/w)(n/q+1). Voor V merken we op dat bij het berekenen van de huidige strip, de elementen in een rij van V worden benaderd in niet afnemende volgorde van index (d.w.z. van links naar rechts) en dat we in het cachegeheugen alleen de laatst gelezen waarde voor elk teken van het alfabet hoeven te bewaren (d.w.z. dat er maximaal s waarden moeten worden bewaard). In de veronderstelling dat een V-waarde alleen uit de cache wordt verwijderd als een nieuwe waarde voor hetzelfde teken wordt opgevraagd, is het totale aantal leesmissers van V bij het berekenen van een enkele strook sm/w. Het aantal schrijfmissers is ongeveer hetzelfde. Dus, V draagt bij (2sm/w)(n/q+1). Het totale aantal cache-misses voor algoritme Strip_DL is dus ≈2(s+1)mn/(wq) als m en n groot zijn.

Houd in gedachten dat het aantal cache-misses voor algoritmen DL en LS_DL bij benadering mn(1+3/w) is. Dit is (wq+3q)/(2s+2) maal die voor Strip_DL.

Het lineaire-ruimte-spooralgoritme L S D L_T R A C E

Hoewel de algoritmen LS_DL en Strip_DL de score (kosten) bepalen van een optimaal spoor (en dus van een optimale bewerkingsvolgorde) die A in B transformeert, slaan deze algoritmen niet genoeg informatie op om daadwerkelijk een optimaal spoor te bepalen. Om een optimaal spoor te bepalen met behulp van lineaire ruimte, gebruiken we een verdeel-en-heers strategie, vergelijkbaar met die gebruikt door Hirschberg voor het eenvoudige string editing probleem (d.w.z, transposities zijn niet toegestaan) en Myers en Miller voor het sequentie-uitlijningsprobleem.

We zeggen dat een spoor een middendoorgang heeft als het twee lijnen (u1,v1) en (u2,v2) bevat, u1<u2 zodanig dat v1>n/2 en v2≤n/2 (Fig. 4).

L-spoor splitsingskansen. a Geen middendoorsnijding b Met middendoorsnijding

Laat T een optimaal spoor zijn dat aan de eigenschappen P2-P4 voldoet. Als T geen middendoorgang bevat, dan kunnen de lijnen ervan verdeeld worden in verzamelingen TL en TR zodanig dat TL alle lijnen (u,v)∈T met v≤n/2 bevat en TR de overige lijnen (fig. 4a). Omdat er geen middendoorgang is, hebben alle lijnen in TR een u-waarde groter dan de u-waarde van elke lijn in TL. Uit de eigenschappen P2-P4 volgt dat er een i, 1≤i≤m zo is dat T de unie is van een optimaal spoor voor A en B en dat voor A en B. Zij H de kosten van het eerstgenoemde optimale spoor en H′ die van het laatstgenoemde optimale spoor. We zien dat wanneer T geen middenkruising heeft, de kosten van T

Wanneer T een middenkruising bevat, kunnen de lijnen ervan worden verdeeld in 3 verzamelingen, TL, TM, en TR, zoals in fig. 4b is te zien. Zij (u1,v1) en (u2,v2) de lijnen die het middenkruispunt definiëren. Merk op dat TL alle lijnen van T met v<v2 bevat, TR bevat alle lijnen met v>v1, en TM={(u1,v1),(u2,v2)}. Merk ook op dat alle lijnen in TL een u<u1 hebben en alle in TR hebben u>u2. Uit eigenschap P1 volgt dat TL een optimaal spoor is voor A en B en TR een optimaal spoor is voor A en B. Verder zijn (u1,v1) en (u2,v2) gebalanceerde lijnen, zodat de kosten van TM (u2-u1-1)+1+(v1-v2-1) zijn. Ook A≠Als anders resulteert het vervangen van de middendoorsnijdende lijnen door (u1,v2) en (u2,v1) in een goedkoper spoor. Uit eigenschap P4 weten we dat \(u_{1} = lastAphantom {i}}} en \(v_{2} = lastB\phantom {i}}}). Laat H de kosten zijn van een optimaal spoor voor A en B en laat H′ die zijn voor een optimaal spoor voor A en B. Dus, als T een middenovergang heeft, zijn de kosten

waarbij we voor de min{} proberen 1≤u1<m en voor elk van die u1 stellen we v1 gelijk aan de kleinste i>n/2 waarvoor \(b_{i} = a_{u_{1}}}}\). Voor elke u1 onderzoeken we alle andere tekens dan a_{u_{1}} in het alfabet. Voor elk zo’n teken c wordt v2 ingesteld op de grootste j≤n/2 waarvoor bj=c en u2 is de kleinste i>u1 waarvoor ai=c. De min wordt dus genomen over (s-1)m termen.

Zie Utop en Ttop als de uiteindelijke U- en T-reeksen die door LS_DL met de ingangen B en A zijn berekend, en Ubot en Tbot zijn deze reeksen als de ingangen het omgekeerde zijn van B en A. Uit deze reeksen kunnen we gemakkelijk de H- en H′-waarden bepalen die nodig zijn voor de evaluatie van de vergelijkingen 3 en 4. Algoritme LSDL_TRACE (algoritme 4) bevat de pseudocode voor onze lineaire ruimteberekening van een optimaal spoor. De pseudocode gaat ervan uit dat LS_DL is aangepast om zowel de arrays U als T terug te geven.

Voor de tijdcomplexiteit zien we dat we op het hoogste niveau van de recursie LS_DL tweemaal aanroepen met strings A en B van grootte m en n/2, respectievelijk. Dit kost hooguit amn tijd voor een constante a. De tijd die nodig is om Eqs. 3 en 4 te berekenen is O(sn) en kan worden geabsorbeerd in amn door een voldoende grote constante a te gebruiken. Op het volgende niveau van recursie wordt LS_DL 4 keer aangeroepen. De som van de lengtes van de A strings over deze 4 aanroepingen is hoogstens 2m en de B string heeft lengte hoogstens n/4. De tijd voor deze vier aanroepingen is dus hoogstens amn/2. Als we generaliseren naar de resterende recursieniveaus, zien we dat algoritme LSDL_TRACE amn(1+1/2+1/4+1/8+…)<2amn=O(mn) tijd vergt. De benodigde ruimte is dezelfde als die voor LS_DL (merk op dat de parameters van dit algoritme verwisseld zijn). Uit de tijdsanalyse volgt dat het aantal cache misses ongeveer twee keer zo groot is als voor LS_DL wanneer strings van grootte m en n worden aangeroepen. Het aantal cache misses voor LSDL_TRACE is dus bij benadering 2mn(1+3/w).

We merken op dat de werkelijke doorlooptijd enigszins kan worden gereduceerd door A en B te verwisselen wanneer A korter is dan B en er zo voor te zorgen dat de kortere string op elk niveau van recursie wordt gesplitst. Hierdoor kunnen we de recursie sneller laten eindigen.

Het strip trace algoritme S t r i p_T R A C E

Dit algoritme verschilt van LSDL_TRACE doordat het gebruik maakt van een aangepaste versie van Strip_DL in plaats van een aangepaste versie van LS_DL. De gewijzigde versie van Strip_DL geeft de door Strip_DL berekende matrices strip en V terug. Dienovereenkomstig gebruikt Strip_TRACE Vtop en Vbot in plaats van Ttop en Tbot. De asymptotische tijdcomplexiteit van Strip_TRACE is ook O(mn) en neemt evenveel ruimte in als Strip_DL (merk op dat de parameters voor Strip_DL zijn verwisseld ten opzichte van die voor Strip_TRACE). Het aantal cache misses is ongeveer twee keer zo groot als voor Strip_DL.

Multi-core algoritmen

In deze sectie beschrijven we onze parallellisaties van algoritme DL en de vier single-core algoritmen uit de vorige sectie. Deze parallellisaties gaan ervan uit dat het aantal processoren klein is in verhouding tot de lengte van de string. De naamgevingsconventie die we voor de parallelle versies gebruiken is de toevoeging van PP_ als voorvoegsel aan de naam van het single-core algoritme.

Het algoritme P P_D L

Onze parallelle versie van algoritme DL, PP_DL, berekent de elementen in dezelfde volgorde als DL. Het begint echter met de berekening van een rij voordat de berekening van de voorgaande rij is voltooid. Elke processor krijgt een unieke rij om te berekenen en berekent deze rij van links naar rechts. Stel p is het aantal processoren. Processor z wordt aanvankelijk aangewezen om de buitenste lus te berekenen voor i=z, 1≤i≤p. Processor z begint na een geschikte tijdvertraging ten opzichte van de start van processor z-1, zodat de gegevens die hij nodig heeft voor zijn berekening al door processor z-1 zijn berekend. In onze code is het tijdsverschil tussen het begin van de berekening van twee opeenvolgende rijen de tijd die nodig is om n/p elementen te berekenen. Na voltooiing van de berekening van iteratie i gaat de processor verder met iteratie i+p van de buitenste lus. De tijdcomplexiteit van PP_DL is O(mn/p).

Het algoritme P P_L S_D L

Hoewel de algemene parallellisatiestrategie voor PP_LS_DL dezelfde is als die voor PP_DL, is extra zorg nodig om een berekening te krijgen die identiek is aan die van LS_DL. Divergentie in resultaten is mogelijk wanneer twee of meer processoren gelijktijdig verschillende rijen van H berekenen met gebruikmaking van hetzelfde geheugen. Dit gebeurt bijvoorbeeld als A=aaabc⋯ en p≥3. We beginnen met processor i toegewezen om rij i van H te berekenen, 1≤i≤p. Stel dat U=x en T=y aanvankelijk (merk op dat x en y adressen in het geheugen zijn). Vanwege het swap(T],U) statement in LS_DL begint processor 1 rij 1 van H te berekenen met geheugen beginnend bij het adres y. Als processor 2 begint met een passende tijdvertraging zoals in PP_DL, zal hij rij 2 van H berekenen met geheugen beginnend bij het adres x. Met nog meer vertraging zal processor 3 rij 3 van H gaan berekenen met geheugen beginnend bij het adres y. Nu gebruiken zowel processor 1 als 3 hetzelfde geheugen om verschillende rijen van H te berekenen en lopen we dus het risico dat we H-waarden overschrijven die voor volgende berekeningen nodig kunnen zijn. Een ander voorbeeld: beschouw A=ababa⋯ en p≥4. Stel dat U=x en T= aanvankelijk. Processor 1 begint rij 1 te berekenen met geheugen y, daarna begint, met enige vertraging, processor 2 rij 2 te berekenen met geheugen z, daarna begint processor 3 rij 3 te berekenen met geheugen x. Vervolgens begint processor 4 rij 4 te berekenen met geheugen y. Op dit moment berekent processor 1 rij 1 met A=a en berekent processor 4 rij 4 met A=b en beide processoren gebruiken hetzelfde rijgeheugen y.

Laat p1 en p2 twee processoren zijn die hetzelfde geheugen gebruiken om rijen r1<r2 van H te berekenen en dat geen enkele processor dit geheugen gebruikt om een rij tussen r1 en r2 te berekenen. Uit het in LS_DL gebruikte swapping-toewijzingssysteem volgt dat p1 de rij r1 = lastA-1 berekent. De H waarden in deze rij zijn nodig om de rijen r1+1 tot en met r2 te berekenen als \phantom {i}\!}r_{1} = lastA r_{1} < i \le r_{2}). Deze waarden zijn niet nodig voor de rijen i>r2 omdat voor deze rijen r_{1} = lastA = r_{2} > r_{1} + 1 = laatsteA). Laat j1 zo zijn dat _{j} = a_{r_{2}} = a_{r_{1} + 1}}). Dan geldt voor j>j1, \(\phantom {\dot {i}!}lastB \ge j_{1}}). Vandaar dat voor j>j1 de kolommen 1 tot en met j1-2 van rij r1 niet nodig zijn om een H in rijen tussen r1 en r2 te berekenen.

Onze parallelle code gebruikt een synchronisatieschema dat is gebaseerd op de observaties van de vorige paragraaf om het overschrijven van waarden die nodig zijn voor latere berekeningen te vertragen en een correcte berekening van de DL afstand te verzekeren. Ons synchronisatieschema maakt gebruik van een andere matrix W die geïnitialiseerd is op 1. Stel dat een processor rij i van H berekent en dat A=a. Wanneer deze processor voor het eerst een a in B tegenkomt, bijvoorbeeld op positie j1, verhoogt hij W. Wanneer de volgende a wordt tegengekomen, bijvoorbeeld op j2, verhoogt hij W met 1. Wanneer de processor klaar is met de berekening van rij i, worden de resterende posities van W verhoogd met 1. De processor die rij q van H moet berekenen kan U berekenen alsf W=q. Uit onze eerdere waarnemingen volgt dat als W=q, de oude waarden in geheugenposities U mogen worden overschreven, omdat deze niet nodig zijn voor toekomstige berekeningen.

De tijdcomplexiteit van dit p-processor algoritme PP_LS_DL hangt af van de datasets, omdat de synchronisatievertraging data-afhankelijk is. We verwachten echter een runtimeprestatie van ongeveer O(mn/p) als de tekens in B ruwweg uniform verdeeld zijn.

Het algoritme P P_S t r i p_D L

In de parallelle versie PP_Strip_DL van Strip_DL wordt processor i in eerste instantie toegewezen om strook i, 1≤i≤p te berekenen. Na voltooiing van de haar toegewezen strook j gaat de processor verder met het berekenen van strook j+p. Een array-signaal wordt gebruikt voor synchronisatiedoeleinden. Bij het berekenen van een rij r in de aan hem toegewezen strook s moet een processor wachten tot signaal=s. Signaal wordt op s gezet door de processor die aan strook s-1 werkt als de waarden links van strook s die nodig zijn voor het berekenen van rij r van strook s zijn berekend en er geen risico is dat de berekeningen voor rij r van strook s V-waarden overschrijven die andere processoren nodig hebben. signaal werkt ongeveer zoals W in PP_LS_DL.

Merk op dat wanneer we met p stroken werken, we p kopieën nodig hebben van de arrays U en T die door Strip_DL worden gebruikt.

De tijdcomplexiteit van PP_Strip_DL hangt af van de synchronisatievertraging en zal naar verwachting O(mn/p) benaderen.

Het algoritme P_D L_T R A C E

Dit algoritme gebruikt eerst PP_DL om H te berekenen. Vervolgens voert een enkele processor een traceback uit om het optimale spoor te construeren. Voor redelijke waarden van p wordt de doorlooptijd gedomineerd door PP_DL en dus is de complexiteit van PP_DL_TRACE ook O(mn/p).

De algoritmen P P_L S D L_T R A C E en P P_S t r i p_T R A C E

In LSDL_TRACE (Strip_TRACE) verdelen we het probleem herhaaldelijk in tweeën en passen we ofwel LS_DL (Strip_DL) toe op elke partitie. De parallelle versie PP_LSDL_TRACE (PP_Strip_TRACE) maakt gebruik van de volgende parallellisatie strategie:

• Elk deelprobleem wordt opgelost met PP_LS_DL (PP_Strip_DL) als het aantal onafhankelijke deelproblemen klein is; alle p processoren worden toegewezen aan de parallelle oplossing van één deelprobleem. D.w.z., de subproblemen worden achter elkaar opgelost.

• p subproblemen worden parallel opgelost met behulp van LS_DL (Strip_DL) om elk subprobleem serieel op te lossen wanneer het aantal onafhankelijke subproblemen groot is,

De tijdcomplexiteit van PP_LSDL_TRACE en PP_Strip_TRACE is O(mn/p).