Strängkorrigering med hjälp av Damerau-Levenshtein-avståndet

där vi för min{} prövar 1≤u1<m och för varje sådan u1, sätter vi v1 till att vara den minsta i>n/2 för vilken \(b_{i} = a_{u_{1}}\phantom {\dot {i}\!}\). För varje u1 undersöker vi alla andra tecken än \(\phantom {\dot {i}\!}a_{u_{1}}\) i alfabetet. För varje sådant tecken c sätts v2 till det största j≤n/2 för vilket bj=c och u2 är det minsta i>u1 för vilket ai=c. Min är alltså (s-1)m termer.

Låt Utop och Ttop vara de slutliga U- och T-matriserna som beräknats av LS_DL med ingångarna B och A och Ubot och Tbot vara dessa matriser när ingångarna är motsatsen till B och A. Från dessa matriser kan vi lätt bestämma de H- och H′-värden som behövs för att utvärdera ekvationerna 3 och 4. Algoritm LSDL_TRACE (Algoritm 4) innehåller pseudokoden för vår linjära rymdberäkning av ett optimalt spår. Den förutsätter att LS_DL har modifierats för att returnera både arrays U och T.

För tidskomplexiteten ser vi att vi på den översta nivån av rekursionen åberopar LS_DL två gånger med strängar A och B av storleken m respektive n/2. Detta tar högst amn tid för en viss konstant a. Den tid som krävs för att beräkna ekv. 3 och 4 är O(sn) och kan absorberas i amn genom att använda en lämpligt stor konstant a. På nästa rekursionsnivå åberopas LS_DL fyra gånger. Summan av längderna av A-strängarna under dessa fyra anrop är högst 2m och B-strängen är högst n/4 lång. Tiden för dessa fyra anrop är alltså högst amn/2. Genom att generalisera till de återstående rekursionsnivåerna ser vi att algoritmen LSDL_TRACE tar amn(1+1/2+1/4+1/8+…)<2amn=O(mn) tid. Det utrymme som behövs är detsamma som för LS_DL (observera att parametrarna för denna algoritm har bytts ut). Av tidsanalysen följer att antalet cache missar är ungefär dubbelt så stort som för LS_DL när den anropas med strängar av storlekarna m och n. Därför är det ungefärliga antalet cache missar för LSDL_TRACE 2mn(1+3/w).

Vi noterar att en viss minskning av den faktiska körtiden kan uppnås genom att växla A och B när A är kortare än B och på så sätt se till att den kortare strängen delas vid varje rekursionsnivå. Detta gör att vi kan få rekursionen avslutad snabbare.

The strip trace algorithm S t r i p_T R A C E

Denna algoritm skiljer sig från LSDL_TRACE genom att den använder en modifierad version av Strip_DL snarare än en modifierad version av LS_DL. Den modifierade versionen av Strip_DL returnerar de matriser strip och V som beräknats av Strip_DL. På motsvarande sätt använder Strip_TRACE Vtop och Vbot i stället för Ttop och Tbot. Den asymptotiska tidskomplexiteten för Strip_TRACE är också O(mn) och tar lika mycket plats som Strip_DL (observera att parametrarna för Strip_DL är ombytta i förhållande till dem för Strip_TRACE). Antalet cache missar är ungefär dubbelt så många som för Strip_DL.

Multikärniga algoritmer

I det här avsnittet beskriver vi våra parallelliseringar av algoritm DL och de fyra enkelkärniga algoritmerna i föregående avsnitt. Dessa parallelliseringar förutsätter att antalet processorer är litet i förhållande till strängarnas längd. Den namnkonvention som vi antar för de parallella versionerna är att lägga till PP_ som prefix till namnet på single-core-algoritmen.

Algoritmen P P_D L

Vår parallella version av algoritmen DL, PP_DL, beräknar elementen i samma ordning som DL. Den börjar dock beräkningen av en rad innan beräkningen av den föregående raden är klar. Varje processor tilldelas en unik rad att beräkna och den beräknar denna rad från vänster till höger. Låt p vara antalet processorer. Processor z tilldelas initialt att utföra beräkningen av den yttre slingan för i=z, 1≤i≤p. Processor z börjar efter en lämplig tidsfördröjning i förhållande till starten av processor z-1 så att de data som den behöver för sin beräkning redan har beräknats av processor z-1. I vår kod är tidsfördröjningen mellan starten av beräkningen av två på varandra följande rader den tid som behövs för att beräkna n/p element. När processorn har slutfört sin beräkning i iteration i går den vidare till iteration i+p i den yttre slingan. Tidskomplexiteten för PP_DL är O(mn/p).

Algoritmen P P P_L S_D L

Men även om den allmänna parallelliseringsstrategin för PP_LS_DL är densamma som den som används i PP_DL, krävs extra omsorg för att säkerställa en beräkning som är identisk med LS_DL. Det är möjligt att resultaten avviker från varandra när två eller flera processorer samtidigt beräknar olika rader av H med hjälp av samma minne. Detta händer till exempel när A=aaabc⋯ och p≥3. Vi börjar med processor i som tilldelats att beräkna rad i i i H, 1≤i≤p. Anta att U=x och T=y initialt (notera att x och y är adresser i minnet). På grund av swap(T],U) i LS_DL börjar processor 1 beräkna rad 1 i H med hjälp av minnet som börjar vid adressen y. Om processor 2 börjar med en lämplig tidsförskjutning som i PP_DL kommer den att beräkna rad 2 i H med hjälp av minnet som börjar vid adressen x. Med ytterligare en fördröjning kommer processor 3 att börja beräkna rad 3 i H med hjälp av minnet som börjar på adressen y. Nu använder både processor 1 och 3 samma minne för att beräkna olika rader i H, vilket innebär att vi riskerar att skriva över H-värden som kan behövas för senare beräkningar. Ett annat exempel är A=ababa⋯ och p≥4. Anta att U=x och T= initialt. Processor 1 börjar beräkna rad 1 med hjälp av minnet y, därefter, med en fördröjning, börjar processor 2 beräkna rad 2 med hjälp av minnet z, därefter börjar processor 3 beräkna rad 3 med hjälp av minnet x. Därefter börjar processor 4 beräkna rad 4 med hjälp av minnet y. Vid denna tidpunkt beräknar processor 1 rad 1 med A=a och processor 4 beräknar rad 4 med A=b och båda processorerna använder samma radminne y.

Låt p1 och p2 vara två processorer som använder samma minne för att beräkna rader r1<r2 i H och att ingen processor använder detta minne för att beräkna en rad mellan r1 och r2. Av det system för bytestilldelning som används i LS_DL följer att p1 beräknar raden \(r_{1} = lastA-1\phantom {\dot {i}\\!}\). H-värdena i denna rad behövs för att beräkna raderna r1+1 till r2 som \(\(\phantom {\dot {i}\\!}r_{1} = lastA r_{1} < i \le r_{2}\). Dessa värden behövs inte för raderna i>r2 eftersom dessa rader \(\phantom {\dot {i}\!}lastA = r_{2} > r_{1} + 1 = lastA\). Låt j1 vara sådan att \(\phantom {\dot {i}\!}b_{j} = a_{r_{2}} = a_{r_{1} + 1}\). För j>j1 gäller då \(\phantom {\dot {i}\!}lastB \ge j_{1}\). För j>j1 behövs alltså inte kolumnerna 1 till j1-2 i rad r1 för att beräkna ett H i rader mellan r1 och r2.

Vår parallella kod använder ett synkroniseringsschema som bygger på observationerna i föregående stycke för att fördröja överskrivningen av värden som behövs för senare beräkningar och säkerställa en korrekt beräkning av DL-avståndet. Vårt synkroniseringsschema använder en annan matris W som är initialiserad till 1. Anta att en processor beräknar rad i i H och att A=a. När denna processor först möter en a i B, till exempel vid position j1, ökar den W. När nästa a möts, till exempel vid j2, ökar den W med 1. När processorn avslutar sin beräkning av rad i ökas de återstående positionerna i W med 1. Den processor som tilldelats uppgiften att beräkna rad q i H kan beräkna U om W=q. Av våra tidigare observationer följer att när W=q kan de gamla värdena i minnespositionerna U skrivas över eftersom de inte behövs för framtida beräkningar.

Denna p-processoralgoritm PP_LS_DL:s tidskomplexitet beror på datamängderna eftersom synkroniseringsfördröjningen är databeroende. Vi förväntar oss dock en körtidsprestanda på ungefär O(mn/p) när tecknen i B är ungefär jämnt fördelade.

Algoritmen P P P_S t r i p_D L

I den parallella versionen PP_Strip_DL av Strip_DL tilldelas processorn i inledningsvis att beräkna strip i, 1≤i≤p. Efter att ha slutfört den för närvarande tilldelade remsan j fortsätter processorn att beräkna remsan j+p. En array-signal används för synkronisering. När en processor beräknar en rad r i sin tilldelade remsa s måste den vänta tills signal=s. signal sätts till s av den processor som arbetar på remsa s-1 när de värden till vänster om remsa s som behövs vid beräkningen av rad r i remsa s har beräknats och det inte finns någon risk för att beräkningarna av rad r i remsa s kommer att överskriva V-värden som behövs av andra processorer. signal fungerar i stor utsträckning som W i PP_LS_DL.

Bemärk att när vi arbetar med p remsor behöver vi p kopior av de matriser U och T som används av Strip_DL.

Tidskomplexiteten för PP_Strip_DL beror på synkroniseringsfördröjningen och förväntas närma sig O(mn/p).

Algoritmen P P P_D L_T R A C E

Denna algoritm använder först PP_DL för att beräkna H. Därefter utför en enskild processor en traceback för att konstruera den optimala trace. För rimliga värden på p domineras körtiden av PP_DL och därför är komplexiteten hos PP_DL_TRACE också O(mn/p).

Algoritmerna P P P_L S D L_T R A C E och P P P_S t r i p_T R A C E

I LSDL_TRACE (Strip_TRACE) delar vi upprepade gånger upp problemet i två och tillämpar antingen LS_DL (Strip_DL) på varje partition. I den parallella versionen PP_LSDL_TRACE (PP_Strip_TRACE) används följande parallelliseringsstrategi:

• Varje delproblem löses med PP_LS_DL (PP_Strip_DL) när antalet oberoende delproblem är litet; alla p processorer tilldelas den parallella lösningen av ett enda delproblem. D.v.s. delproblemen löses i sekvens.

• p delproblem löses parallellt med hjälp av LS_DL (Strip_DL) för att lösa varje delproblem seriellt när antalet oberoende delproblem är stort,

Tidskomplexiteten för PP_LSDL_TRACE och PP_Strip_TRACE är O(mn/p).