Correzione delle stringhe usando la distanza Damerau-Levenshtein

by: adminPosted on:

Algoritmi single-core

In questa sezione, sviluppiamo quattro algoritmi single-core in spazio lineare per la correzione delle stringhe usando la distanza DL. Tutti e quattro girano in tempo O(mn). I primi due (LS_DL e Strip_DL) calcolano solo il punteggio Hmn della traccia ottimale; differiscono nella loro efficienza della cache. Gli ultimi due (LSDL_TRACE e Strip_TRACE) calcolano una traccia ottimale.

L’algoritmo di spazio lineare L S_D L

Sia s la dimensione dell’alfabeto. Invece di usare l’array H usato in DL, l’algoritmo LS_DL usa un array unidimensionale U e un array bidimensionale T. Questi due array hanno una richiesta di spazio di O((s+1)n) = O(n) per s costante. Quando m<n, si può scambiare A e B per ridurre la memoria richiesta. Aggiungendo la memoria necessaria per A e B, la complessità spaziale è O(s min{m,n}+m+n) = O(m+n) quando s è una costante.

Come nell’algoritmo DL, i valori Hij sono calcolati per righe. L’array unidimensionale U è usato per salvare i valori H calcolati dall’algoritmo DL quando viene calcolata la riga i. Sia H l’ultima riga calcolata per il carattere c. Allora, T è la riga w-1 di H. L’algoritmo 2 fornisce lo pseudocodice per LS_DL. La sua correttezza segue dalla correttezza dell’algoritmo DL. Si noti che swap(T],U) richiede O(1) tempo in quanto vengono scambiati i puntatori a 2 array unidimensionali piuttosto che il contenuto di questi array. Il numero di cache-miss per LS_DL è lo stesso di quello di DL quando n è adeguatamente grande, poiché entrambi hanno lo stesso schema di accesso ai dati. Tuttavia, per istanze più piccole LS_DL mostrerà un comportamento della cache molto migliore. Per esempio, a causa del suo utilizzo di molta meno memoria, potremmo avere abbastanza cache LLC per memorizzare tutti i dati in LS_DL ma non in DL (O(sn) vs O(mn)).

L’algoritmo linear-space efficiente per la cache S t r i p_D L

Quando (s+1)n è più grande della dimensione della cache LLC, possiamo ridurre le missioni nella cache rispetto all’algoritmo LS_DL calcolando Hij per strisce di larghezza q, per qualche q inferiore a n (l’ultima striscia può avere una larghezza inferiore a q). Questo è mostrato in Fig. 3. Le strisce sono calcolate nell’ordine 0, 1,… usando l’algoritmo LS_DL. Tuttavia, lo spazio necessario a T e U in LS_DL è ridotto a (s+1)q poiché la larghezza della striscia è q piuttosto che n. Scegliendo q abbastanza piccolo, possiamo assicurarci che i blocchi degli array T e U usati da LS_DL non vengano sfrattati dalla cache una volta che sono stati portati dentro. Quindi, se ogni voce di T e U prende 1 parola, allora quando la dimensione della cache è lw, abbiamo q<lw/(s+1). Si noti che, oltre a T e U, la cache deve contenere i parziali di A, B e altri array necessari per passare i dati da una striscia alla successiva.

Fig. 3
figura3

Computo di H per strisce

Per passare i dati da una striscia alla successiva, usiamo un ulteriore array unidimensionale di dimensioni m e un array bidimensionale s∗m V. La striscia di array registra i valori di H calcolati per la colonna più a destra nella striscia. V dà il valore di H nella colonna j più a destra della riga i di H che è (a) in una striscia a sinistra di quella che si sta calcolando e (b) c=B.

Lo pseudocodice per Strip_DL è dato nell’algoritmo 3. Per chiarezza, questo pseudocodice usa due array di strip (righe 18 e 30) e due array V (righe 24 e 32). Un set di array è usato per recuperare i dati calcolati per la striscia precedente e l’altro set per i dati che devono essere passati alla striscia successiva. Nell’implementazione attuale, usiamo un singolo array di strisce e un singolo array V che sovrascrive i valori ricevuti dalla striscia precedente con i valori da passare alla striscia successiva.

Il tempo e la complessità di Strip_DL sono, rispettivamente, O(mn) e O((s+1)m+(s+1)q+n) = O(sm+sq+n) = O(sm+n) poiché q è una costante. Quando m>n, possiamo scambiare A e B per conservare la memoria e quindi la complessità dello spazio diventa O(s min{m,n}+m+n) = O(m+n) per s costante.

Quando analizziamo la cache miss, notiamo che q è scelto in modo tale che U e T entrino nella cache. Facciamo l’ipotesi ragionevole che la regola di sostituzione LRU non causi lo sfratto di nessun blocco di U o T durante l’esecuzione dell’algoritmo Strip_DL. Come risultato, il numero totale di cache miss dovute a U e T è indipendente da m e n e quindi può essere ignorato nell’analisi. L’inizializzazione di strip e V risulta in m/w e (s+1)m/w accessi in lettura, rispettivamente. Il numero di accessi in scrittura è approssimativamente uguale al numero di accessi in lettura. Il calcolo per ogni striscia accede alla striscia dell’array in ordine crescente di indice. Questo comporta (approssimativamente) lo stesso numero di accessi alla cache di quelli effettuati durante la fase di inizializzazione. Quindi, il numero totale di missioni di cache dovute alla striscia è approssimativamente (2m/w)(n/q+1). Per V, notiamo che quando si calcola la striscia attuale, gli elementi in qualsiasi riga di V sono acceduti in ordine non decrescente di indice (cioè, da sinistra a destra) e che abbiamo bisogno di conservare, nella cache, solo il valore letto più di recente per ogni carattere dell’alfabeto (cioè, al massimo s valori devono essere conservati). Assumendo che un valore V sia espulso dalla cache solo quando si accede a un nuovo valore per lo stesso carattere, il numero totale di read miss da V durante il calcolo di una singola striscia è sm/w. Il numero di mancate scritture è approssimativamente lo stesso. Quindi, V contribuisce (2sm/w)(n/q+1). Quindi, il numero totale di cache miss per l’algoritmo Strip_DL è ≈2(s+1)mn/(wq) quando m e n sono grandi.

Ricordiamo che il numero approssimativo di cache miss per gli algoritmi DL e LS_DL è mn(1+3/w). Questo è (wq+3q)/(2s+2) volte quello per Strip_DL.

L’algoritmo di traccia nello spazio lineare L S D L_T R A C E

Anche se gli algoritmi LS_DL e Strip_DL determinano il punteggio (costo) di una traccia ottimale (e quindi di una sequenza di modifica ottimale) che trasforma A in B, questi algoritmi non conservano abbastanza informazioni per determinare effettivamente una traccia ottimale. Per determinare una traccia ottimale usando lo spazio lineare, adottiamo una strategia “divide et impera” simile a quella usata da Hirschberg per il semplice problema di editing delle stringhe (cioè, diciamo che una traccia ha un attraversamento centrale se contiene due linee (u1,v1) e (u2,v2), u1<u2 tali che v1>n/2 e v2≤n/2 (Fig. 4).

Fig. 4
figura4

Opportunità di divisione della tracciaDL. a Nessun incrocio centrale b Con incrocio centrale

Sia T una traccia ottimale che soddisfi le proprietà P2-P4. Se T non contiene alcun incrocio centrale, allora le sue linee possono essere partizionate in insiemi TL e TR tali che TL contiene tutte le linee (u,v)∈T con v≤n/2 e TR contiene le linee rimanenti (Fig. 4a). Poiché non c’è un incrocio centrale, tutte le linee in TR hanno un valore u maggiore del valore u di ogni linea in TL. Segue dalle proprietà P2-P4 che c’è un i, 1≤i≤m tale che T è l’unione di una traccia ottimale per A e B e quella per A e B. Sia H il costo della prima traccia ottimale e H′ quello della seconda traccia ottimale. Vediamo che quando T non ha un incrocio centrale, il costo di T è

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

Quando T contiene un incrocio centrale, le sue linee possono essere partizionate in 3 set, TL, TM, e TR, come mostrato in Fig. 4b. Sia (u1,v1) e (u2,v2) le linee che definiscono l’incrocio centrale. Si noti che TL contiene tutte le linee di T con v<v2, TR contiene tutte le linee con v>v1, e TM={(u1,v1),(u2,v2)}. Si noti inoltre che tutte le linee in TL hanno un u<u1 e tutte in TR hanno u>u2. Dalla proprietà P1, segue che TL è una traccia ottimale per A e B e TR è una traccia ottimale per A e B. Inoltre, poiché (u1,v1) e (u2,v2) sono linee equilibrate, il costo di TM è (u2-u1-1)+1+(v1-v2-1). Inoltre, A≠A come altrimenti, sostituendo le linee che attraversano il centro con (u1,v2) e (u2,v1) si ottiene una traccia di costo inferiore. Dalla proprietà P4, sappiamo che \(u_{1} = lastA\fantasma {i}{i}!) e \(v_{2} = lastB\fantasma {i}!). Sia H il costo di una traccia ottimale per A e B e sia H′ quello di una traccia ottimale per A e B. Quindi, quando T ha un attraversamento centrale, il suo costo è

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

dove, per il min{}, proviamo 1≤u1<m e per ogni tale u1, impostiamo v1 come il più piccolo i>n/2 per cui \(b_{i} = a_{u_{1}}\phantom {{i}!}\). Per ogni u1 esaminiamo tutti i caratteri diversi da \(\phantom {\fantasma {i}!}a_{u_{1}}) nell’alfabeto. Per ogni tale carattere c, v2 è impostato al più grande j≤n/2 per il quale bj=c e u2 è il più piccolo i>u1 per il quale ai=c. Quindi, il minimo è preso su (s-1)m termini.

Lasciamo che Utop e Ttop siano le matrici finali U e T calcolate da LS_DL con ingressi B e A e Ubot e Tbot siano queste matrici quando gli ingressi sono l’inverso di B e A. Da queste matrici, possiamo facilmente determinare i valori H e H′ necessari per valutare le Eq. 3 e 4. L’algoritmo LSDL_TRACE (Algoritmo 4) fornisce lo pseudocodice per il nostro calcolo dello spazio lineare di una traccia ottimale. Si assume che LS_DL sia stato modificato per restituire entrambi gli array U e T.

Per la complessità temporale, vediamo che al livello superiore della ricorsione, invochiamo LS_DL due volte con stringhe A e B di dimensione m e n/2, rispettivamente. Questo richiede al massimo amn tempo per qualche costante a. Il tempo richiesto per calcolare le Eq. 3 e 4 è O(sn) e può essere assorbito in amn usando una costante a opportunamente grande. Al livello successivo di ricorsione, LS_DL viene invocato 4 volte. La somma delle lunghezze delle stringhe A in queste 4 invocazioni è al massimo 2m e la stringa B ha lunghezza al massimo n/4. Quindi, il tempo per queste quattro invocazioni è al massimo amn/2. Generalizzando ai restanti livelli di ricorsione, vediamo che l’algoritmo LSDL_TRACE richiede amn(1+1/2+1/4+1/8+…)<2amn=O(mn) tempo. Lo spazio necessario è lo stesso di quello di LS_DL (si noti che i parametri di questo algoritmo sono stati cambiati). Dall’analisi dei tempi, segue che il numero di missioni nella cache è circa il doppio di quello di LS_DL quando viene invocato con stringhe di dimensione m e n. Quindi il numero approssimativo di missioni nella cache per LSDL_TRACE è 2mn(1+3/w).

Si noti che una certa riduzione del tempo di esecuzione effettivo può essere ottenuta scambiando A e B quando A è più corto di B, assicurando così che la stringa più corta sia divisa ad ogni livello di ricorsione. Questo ci permette di ottenere che la ricorsione termini più velocemente.

L’algoritmo strip trace S t r i p_T R A C E

Questo algoritmo differisce da LSDL_TRACE in quanto utilizza una versione modificata di Strip_DL piuttosto che una versione modificata di LS_DL. La versione modificata di Strip_DL restituisce gli array strip e V calcolati da Strip_DL. Corrispondentemente, Strip_TRACE usa Vtop e Vbot al posto di Ttop e Tbot. La complessità temporale asintotica di Strip_TRACE è anch’essa O(mn) e richiede la stessa quantità di spazio di Strip_DL (si noti che i parametri di Strip_DL sono cambiati rispetto a quelli di Strip_TRACE). Il numero di cache mancanti è circa il doppio di quello di Strip_DL.

Algoritmi multi-core

In questa sezione, descriviamo le nostre parallelizzazioni dell’algoritmo DL e dei quattro algoritmi single-core della sezione precedente. Queste parallelizzazioni assumono che il numero di processori sia piccolo rispetto alla lunghezza delle stringhe. La convenzione di denominazione che adottiamo per le versioni parallele è l’aggiunta di PP_ come prefisso al nome dell’algoritmo single-core.

L’algoritmo P P_D L

La nostra versione parallela dell’algoritmo DL, PP_DL, calcola gli elementi nello stesso ordine di DL. Tuttavia, inizia il calcolo di una riga prima che il calcolo della riga precedente sia completato. Ad ogni processore viene assegnata un’unica riga da calcolare e calcola questa riga da sinistra a destra. Sia p il numero di processori. Il processore z è inizialmente assegnato a fare il calcolo del ciclo esterno per i=z, 1≤i≤p. Il processore z inizia dopo un adeguato ritardo rispetto all’inizio del processore z-1 in modo che i dati di cui ha bisogno per il suo calcolo siano già stati calcolati dal processore z-1. Nel nostro codice, l’intervallo di tempo tra l’inizio del calcolo di due righe consecutive è il tempo necessario per calcolare n/p elementi. Al completamento del calcolo dell’iterazione i, il processore procede all’iterazione i+p del ciclo esterno. La complessità temporale di PP_DL è O(mn/p).

L’algoritmo P P_L S_D L

Mentre la strategia generale di parallelizzazione per PP_LS_DL è la stessa di quella usata in PP_DL, è necessaria una cura supplementare per assicurare una computazione identica a quella di LS_DL. La divergenza dei risultati è possibile quando due o più processori calcolano simultaneamente diverse righe di H usando la stessa memoria. Questo accade per esempio quando A=aaabc⋯ e p≥3. Iniziamo con il processore i assegnato a calcolare la riga i di H, 1≤i≤p. Supponiamo che inizialmente U=x e T=y (si noti che x e y sono indirizzi in memoria). A causa dell’istruzione swap(T],U) in LS_DL, il processore 1 inizia a calcolare la riga 1 di H usando la memoria che inizia all’indirizzo y. Se il processore 2 inizia con un adeguato ritardo come in PP_DL, esso calcolerà la riga 2 di H usando la memoria che inizia all’indirizzo x. Con un ulteriore ritardo, il processore 3 inizierà a calcolare la riga 3 di H usando di nuovo la memoria che inizia all’indirizzo y. Ora, entrambi i processori 1 e 3 stanno usando la stessa memoria per calcolare diverse righe di H e quindi corriamo il rischio di sovrascrivere valori H che potrebbero essere necessari per calcoli successivi. Come altro esempio, consideriamo A=ababa⋯ e p≥4. Supponiamo che U=x e T= inizialmente. Il processore 1 inizia a calcolare la riga 1 usando la memoria y, poi, con un ritardo, il processore 2 inizia a calcolare la riga 2 usando la memoria z, poi il processore 3 inizia a calcolare la riga 3 usando la memoria x. Successivamente il processore 4 inizia a calcolare la riga 4 usando la memoria y. In questo momento il processore 1 sta calcolando la riga 1 con A=a e il processore 4 sta calcolando la riga 4 con A=b ed entrambi i processori stanno usando la stessa memoria y.

Lasciate che p1 e p2 siano due processori che stanno usando la stessa memoria per calcolare le righe r1<r2 di H e che nessun processore stia usando questa memoria per calcolare una riga tra r1 e r2. Dallo schema di assegnazione dello swapping usato in LS_DL, segue che p1 sta calcolando la riga \(r_{1} = lastA-1\phantom {{i}\fantasma}). I valori H in questa riga sono necessari per calcolare le righe da r1+1 a r2 come \(\phantom {\fantasma {i}!}r_{1} = lastA r_{1} < i \le r_{2}). Questi valori non sono necessari per le righe i>r2 poiché per queste righe \(\fantasma{i}!} ultimoA = r_{2} > r_{1} + 1 = lastA\). Sia j1 tale che \(\fantasma {i}!}b_{j} = a_{r_{2}} = a_{r_{1} + 1}}). Allora, per j>j1, \fantasma(\punto {i}!}ultimoB \ge j_{1}). Quindi, per j>j1 le colonne da 1 a j1-2 della riga r1 non sono necessarie per calcolare un H nelle righe tra r1 e r2.

Il nostro codice parallelo utilizza uno schema di sincronizzazione che si basa sulle osservazioni del paragrafo precedente per ritardare la sovrascrittura dei valori che sono necessari per calcoli successivi e garantire un calcolo corretto della distanza DL. Il nostro schema di sincronizzazione impiega un altro array W che è inizializzato a 1. Supponiamo che un processore stia calcolando la riga i di H e che A=a. Quando questo processore incontra per la prima volta un a in B, diciamo nella posizione j1, incrementa W. Quando viene incontrato il prossimo a, diciamo in j2, incrementa W di 1. Quando il processore finisce il suo calcolo della riga i, le rimanenti posizioni di W sono incrementate di 1. Il processore assegnato a calcolare la riga q di H può calcolare U iff W=q. Dalle nostre osservazioni precedenti, segue che quando W=q, i vecchi valori nelle posizioni di memoria U possono essere sovrascritti poiché non sono necessari per i calcoli futuri.

La complessità temporale di questo algoritmo p-processore PP_LS_DL dipende dagli insiemi di dati poiché il ritardo di sincronizzazione dipende dai dati. Noi, comunque, ci aspettiamo una performance run-time di circa O(mn/p) quando i caratteri in B sono approssimativamente distribuiti in modo uniforme.

L’algoritmo P P_S t r i p_D L

Nella versione parallela PP_Strip_DL di Strip_DL, il processore i è inizialmente assegnato al calcolo della striscia i, 1≤i≤p. Al completamento della sua striscia j attualmente assegnata, il processore procede a calcolare la striscia j+p. Un segnale di matrice è usato per scopi di sincronizzazione. Quando calcola una riga r nella striscia s che gli è stata assegnata, un processore deve aspettare che signal=s. signal è impostato su s dal processore che lavora sulla striscia s-1 quando i valori a sinistra della striscia s necessari al calcolo della riga r della striscia s sono stati calcolati e non c’è il rischio che i calcoli per la riga r della striscia s sovrascrivano i valori V necessari agli altri processori. signal funziona molto simile a W in PP_LS_DL.

Nota che quando stiamo lavorando su p strisce, abbiamo bisogno di p copie degli array U e T usati da Strip_DL.

La complessità temporale di PP_Strip_DL dipende dal ritardo di sincronizzazione e ci si aspetta che si approssimi a O(mn/p).

L’algoritmo P P_D L_T R A C E

Questo algoritmo usa prima PP_DL per calcolare H. Poi, un singolo processore esegue un traceback per costruire il trace ottimale. Per valori ragionevoli di p, il tempo di esecuzione è dominato da PP_DL e quindi, la complessità di PP_DL_TRACE è anche O(mn/p).

Gli algoritmi P P_L S D L_T R A C E e P P_S t r i p_T R A C E

In LSDL_TRACE (Strip_TRACE), si partiziona ripetutamente il problema in due e si applica LS_DL (Strip_DL) ad ogni partizione. La versione parallela PP_LSDL_TRACE (PP_Strip_TRACE) impiega la seguente strategia di parallelizzazione:

  • Ogni sottoproblema è risolto usando PP_LS_DL (PP_Strip_DL) quando il numero di sottoproblemi indipendenti è piccolo; tutti i processori p sono assegnati alla soluzione parallela di un singolo sottoproblema. Cioè, i sottoproblemi sono risolti in sequenza.

  • p sottoproblemi sono risolti in parallelo usando LS_DL (Strip_DL) per risolvere ogni sottoproblema in serie quando il numero di sottoproblemi indipendenti è grande,

La complessità temporale di PP_LSDL_TRACE e PP_Strip_TRACE è O(mn/p).

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.