Corectarea șirurilor de caractere folosind distanța Damerau-Levenshtein

Oportunități de divizare a urmelor DL. a Fără încrucișare de centru b Cu încrucișare de centru

Să fie T o urmă optimă care satisface proprietățile P2-P4. Dacă T nu conține nicio intersecție de centru, atunci liniile sale pot fi împărțite în seturi TL și TR astfel încât TL să conțină toate liniile (u,v)∈T cu v≤n/2, iar TR să conțină restul liniilor (Fig. 4a). Deoarece nu există o intersecție centrală, toate liniile din TR au o valoare u mai mare decât valoarea u a fiecărei linii din TL. Din proprietățile P2-P4 rezultă că există un i, 1≤i≤m astfel încât T este uniunea unui traseu optim pentru A și B și a celui pentru A și B. Fie H costul primului traseu optim și H′ cel al celui de-al doilea traseu optim. Vedem că atunci când T nu are nici o intersecție centrală, costul lui T este

$$ costNoCC(T) = \min_{1 \le i \le m}\{ H + H’\} $$

(3)

Când T conține o intersecție centrală, liniile sale pot fi împărțite în 3 seturi, TL, TM și TR, așa cum se arată în Fig. 4b. Fie că (u1,v1) și (u2,v2) sunt liniile care definesc intersecția centrală. Rețineți că TL conține toate liniile din T cu v<v2, TR conține toate liniile cu v>v1, iar TM={(u1,v1),(u2,v2)}. De asemenea, rețineți că toate liniile din TL au u<u1 și toate cele din TR au u>u2. Din proprietatea P1, rezultă că TL este un traseu optim pentru A și B, iar TR este un traseu optim pentru A și B. Mai mult, deoarece (u1,v1) și (u2,v2) sunt linii echilibrate, costul TM este (u2-u1-1)+1+(v1-v2-1). De asemenea, A≠A ca și în caz contrar, înlocuirea liniilor de încrucișare a centrului cu (u1,v2) și (u2,v1) duce la un traseu cu un cost mai mic. Din proprietatea P4, știm că \(u_{1} = lastA\phantom {\dot {i}\\!}\) și \(v_{2} = lastB\phantom {\dot {i}\\!}\). Fie H costul unei urme optime pentru A și B și fie H′ costul unei urme optime pentru A și B. Deci, când T are o intersecție de centru, costul său este

$$ {\begin{aligned} costCC(T) \,=\,& \min\{H + H’ \\\ &+ (u_{2}-u_{1}-1) + 1 + (v_{1}-v_{2}-1)\} \end{aligned}} $$

(4)

unde, pentru min{}, încercăm 1≤u1<m și pentru fiecare astfel de u1, stabilim că v1 este cel mai mic i>n/2 pentru care \(b_{i} = a_{u_{1}}\phantom {\dot {i}\!}\). Pentru fiecare u1 examinăm toate caracterele din alfabet, altele decât \(\(\phantom {\dot {i}\\!}a_{u_{1}}\). Pentru fiecare astfel de caracter c, v2 este setat la cel mai mare j≤n/2 pentru care bj=c și u2 este cel mai mic i>u1 pentru care ai=c. Deci, min este luat peste (s-1)m termeni.

Să fie Utop și Ttop matricele finale U și T calculate de LS_DL cu intrările B și A și Ubot și Tbot aceste matrice atunci când intrările sunt inversul lui B și A. Din aceste matrice, putem determina cu ușurință valorile H și H′ necesare pentru a evalua ecuațiile 3 și 4. Algoritmul LSDL_TRACE (Algoritmul 4) oferă pseudocodul pentru calculul nostru în spațiu liniar al unei urme optime. Acesta presupune că LS_DL a fost modificat pentru a returna atât tablourile U, cât și T.

Pentru complexitatea în timp, vedem că la nivelul superior al recursiunii, invocăm LS_DL de două ori cu șirurile A și B de dimensiuni m și, respectiv, n/2, respectiv. Acest lucru durează cel mult amn timp pentru o anumită constantă a. Timpul necesar pentru a calcula ecuațiile 3 și 4 este O(sn) și poate fi absorbit în amn prin utilizarea unei constante a suficient de mari. La următorul nivel de recursivitate, LS_DL este invocat de 4 ori. Suma lungimilor șirurilor A pe parcursul acestor 4 apeluri este de cel mult 2m, iar șirul B are o lungime de cel mult n/4. Prin urmare, timpul pentru aceste patru apeluri este de cel mult amn/2. Generalizând la celelalte niveluri de recursivitate, vedem că algoritmul LSDL_TRACE durează amn(1+1/2+1/4+1/8+…)<2amn=O(mn) timp. Spațiul necesar este același cu cel pentru LS_DL (rețineți că parametrii acestui algoritm au fost schimbați). Din analiza timpului, rezultă că numărul de ratări ale memoriei cache este aproximativ dublu față de cel pentru LS_DL atunci când este invocat cu șiruri de dimensiuni m și n. Prin urmare, numărul aproximativ de ratări ale memoriei cache pentru LSDL_TRACE este 2mn(1+3/w).

Reținem că se poate obține o anumită reducere a timpului real de execuție prin comutarea lui A și B atunci când A este mai scurt decât B, asigurându-se astfel că șirul mai scurt este divizat la fiecare nivel de recursivitate. Acest lucru ne permite să obținem o terminare mai rapidă a recursivității.

Algoritmul strip trace S t r i p_T R A C E

Acest algoritm diferă de LSDL_TRACE prin faptul că utilizează o versiune modificată a Strip_DL mai degrabă decât o versiune modificată a LS_DL. Versiunea modificată a Strip_DL returnează array-urile strip și V calculate de Strip_DL. În mod corespunzător, Strip_TRACE utilizează Vtop și Vbot în loc de Ttop și Tbot. Complexitatea asimptotică în timp a Strip_TRACE este, de asemenea, O(mn) și ocupă același spațiu ca și Strip_DL (rețineți că parametrii pentru Strip_DL sunt schimbați în raport cu cei pentru Strip_TRACE). Numărul de ratări ale cache-ului este aproximativ dublu față de cel pentru Strip_DL.

Algoritmi multi-core

În această secțiune, descriem paralelizările noastre ale algoritmului DL și ale celor patru algoritmi single-core din secțiunea anterioară. Aceste paralelizări presupun că numărul de procesoare este mic în raport cu lungimea șirului. Convenția de denumire pe care o adoptăm pentru versiunile paralele constă în adăugarea PP_ ca prefix la numele algoritmului cu un singur nucleu.

Algoritmul P P P_D L

Versiunea noastră paralelă a algoritmului DL, PP_DL, calculează elementele în aceeași ordine ca și DL. Cu toate acestea, începe calculul unui rând înainte ca calculul rândului precedent să fie finalizat. Fiecărui procesor i se atribuie un singur rând de calculat și calculează acest rând de la stânga la dreapta. Fie p numărul de procesoare. Procesorului z i se atribuie inițial sarcina de a efectua calculul buclei exterioare pentru i=z, 1≤i≤p. Procesorul z începe după un decalaj de timp adecvat în raport cu începerea procesorului z-1, astfel încât datele de care are nevoie pentru calculul său să fi fost deja calculate de procesorul z-1. În codul nostru, decalajul de timp dintre începutul calculării a două rânduri consecutive este timpul necesar pentru calcularea a n/p elemente. După terminarea calculului din iterația i, procesorul trece la iterația i+p a buclei exterioare. Complexitatea în timp a PP_DL este O(mn/p).

Algoritmul P P P_L S_D L

În timp ce strategia generală de paralelizare pentru PP_LS_DL este aceeași cu cea utilizată în PP_DL, este necesară o atenție suplimentară pentru a asigura un calcul identic cu cel din LS_DL. Divergențele în rezultate sunt posibile atunci când două sau mai multe procesoare calculează simultan rânduri diferite din H folosind aceeași memorie. Acest lucru se întâmplă, de exemplu, atunci când A=aaabc⋯ și p≥3. Începem cu procesorul i desemnat să calculeze rândul i din H, 1≤i≤p. Să presupunem că U=x și T=y inițial (rețineți că x și y sunt adrese din memorie). Datorită instrucțiunii swap(T],U) din LS_DL, procesorul 1 începe să calculeze rândul 1 din H folosind memoria care începe la adresa y. Dacă procesorul 2 începe cu un decalaj de timp adecvat, ca în PP_DL, acesta va calcula rândul 2 din H folosind memoria care începe la adresa x. Cu un alt decalaj, procesorul 3 va începe să calculeze rândul 3 din H, utilizând din nou memoria care începe la adresa y. Acum, atât procesorul 1, cât și procesorul 3 utilizează aceeași memorie pentru a calcula diferite rânduri din H și, prin urmare, există riscul de a suprascrie valorile H care pot fi necesare pentru calculele ulterioare. Ca un alt exemplu, considerăm A=ababa⋯ și p≥4. Să presupunem că U=x și T= inițial. Procesorul 1 începe să calculeze rândul 1 utilizând memoria y, apoi, cu un decalaj, procesorul 2 începe să calculeze rândul 2 utilizând memoria z, apoi procesorul 3 începe să calculeze rândul 3 utilizând memoria x. În continuare, procesorul 4 începe să calculeze rândul 4 utilizând memoria y. În acest moment, procesorul 1 calculează rândul 1 cu A=a și procesorul 4 calculează rândul 4 cu A=b și ambele procesoare folosesc aceeași memorie y.

Să fie p1 și p2 două procesoare care folosesc aceeași memorie pentru a calcula rândurile r1<r2 din H și că niciun procesor nu folosește această memorie pentru a calcula un rând între r1 și r2. Din schema de alocare a permutării utilizată în LS_DL, rezultă că p1 calculează rândul \(r_{1} = lastA-1\phantom {\dot {i}\\!}\). Valorile H din acest rând sunt necesare pentru a calcula rândurile r1+1 până la r2 ca \(\phantom {\dot {i}\!}r_{1} = lastA r_{1} < i \le r_{2}\). Aceste valori nu sunt necesare pentru rândurile i>r2, deoarece pentru aceste rânduri \(\phantom {\dot {i}\!}lastA = r_{2} > r_{1} + 1 = lastA\). Fie j1 astfel încât \(\(\phantom {\dot {i}\\!}b_{j} = a_{r_{2}} = a_{r_{1} + 1}\). Atunci, pentru j>j1, \(\phantom {\dot {i}\\!}lastB \ge j_{1}\). Prin urmare, pentru j>j1 coloanele 1 până la j1-2 din rândul r1 nu sunt necesare pentru a calcula un H în rândurile dintre r1 și r2.

Codul nostru paralel utilizează o schemă de sincronizare care se bazează pe observațiile din paragraful anterior pentru a întârzia suprascrierea valorilor care sunt necesare pentru calculele ulterioare și pentru a asigura un calcul corect al distanței DL. Schema noastră de sincronizare utilizează o altă matrice W care este inițializată la 1. Să presupunem că un procesor calculează rândul i din H și că A=a. Atunci când acest procesor întâlneș te pentru prima dată un a în B, de exemplu în poziția j1, acesta măreș te W. Atunci când se întâlneș te următorul a, de exemplu în j2, acesta măreș te W cu 1. Atunci când procesorul îș i termină calculul rândului i, celelalte poziții din W sunt mărite cu 1. Procesorul desemnat să calculeze rândul q din H poate calcula U dacă W=q. Din observațiile noastre anterioare rezultă că, atunci când W=q, vechile valori din pozițiile de memorie U pot fi suprascrise, deoarece acestea nu sunt necesare pentru calculele viitoare.

Complexitatea în timp a acestui algoritm p-procesor PP_LS_DL depinde de seturile de date, deoarece întârzierea de sincronizare este dependentă de date. Cu toate acestea, ne așteptăm la o performanță în timp de execuție de aproximativ O(mn/p) atunci când caracterele din B sunt distribuite aproximativ uniform.

Algoritmul P P P_S t r i p_D L

În versiunea paralelă PP_Strip_DL a Strip_DL, procesorului i i i se atribuie inițial să calculeze banda i, 1≤i≤p. După terminarea benzii j care i-a fost atribuită în acel moment, procesorul trece la calcularea benzii j+p. În scopul sincronizării, se utilizează un semnal de matrice. Atunci când calculează un rând r din banda s care i-a fost atribuită, un procesor trebuie să aștepte până când semnal=s. semnalul este setat la s de către procesorul care lucrează pe banda s-1 atunci când valorile din stânga benzii s necesare pentru calculul rândului r din banda s au fost calculate și nu există riscul ca calculele pentru rândul r din banda s să suprascrie valorile V necesare altor procesoare. semnalul funcționează foarte asemănător cu W în PP_LS_DL.

Rețineți că atunci când lucrăm pe p benzi, avem nevoie de p copii ale matricelor U și T utilizate de Strip_DL.

Complexitatea în timp a PP_Strip_DL depinde de întârzierea de sincronizare și se așteaptă să se apropie de O(mn/p).

Algoritmul P P P_D L_T R A C E

Acest algoritm utilizează mai întâi PP_DL pentru a calcula H. Apoi, un singur procesor efectuează un traseu de urmărire pentru a construi traseul optim. Pentru valori rezonabile ale lui p, timpul de execuție este dominat de PP_DL și astfel, complexitatea lui PP_DL_TRACE este, de asemenea, O(mn/p).

Algoritmii P P P_L S D L_T R A C E și P P P_S t r i p_T R A C E

În LSDL_TRACE (Strip_TRACE), partiționăm în mod repetat problema în două și aplicăm fie LS_DL (Strip_DL) la fiecare partiție. Versiunea paralelă PP_LSDL_TRACE (PP_Strip_TRACE) utilizează următoarea strategie de paralelizare:

• Care subproblemă este rezolvată folosind PP_LS_DL (PP_Strip_DL) atunci când numărul de subprobleme independente este mic; toate cele p procesoare sunt alocate soluției paralele a unei singure subprobleme. Adică, subproblemele sunt rezolvate în secvență.

• p subprobleme sunt rezolvate în paralel folosind LS_DL (Strip_DL) pentru a rezolva fiecare subproblemă în serie atunci când numărul de subprobleme independente este mare,

Complexitatea în timp a PP_LSDL_TRACE și PP_Strip_TRACE este O(mn/p).