String-Korrektur unter Verwendung der Damerau-Levenshtein-Distanz

Ein-Kern-Algorithmen

In diesem Abschnitt entwickeln wir vier Ein-Kern-Algorithmen für die String-Korrektur unter Verwendung der DL-Distanz. Alle vier laufen in O(mn) Zeit. Die ersten beiden (LS_DL und Strip_DL) berechnen nur den Wert Hmn der optimalen Spur; sie unterscheiden sich durch ihre Cache-Effizienz. Die letzten beiden (LSDL_TRACE und Strip_TRACE) berechnen eine optimale Spur.

Der lineare Raumalgorithmus L S_D L

Lassen Sie s die Größe des Alphabets sein. Anstelle des in DL verwendeten Arrays H verwendet der Algorithmus LS_DL ein eindimensionales Array U und ein zweidimensionales Array T. Diese beiden Arrays haben einen Platzbedarf von O((s+1)n) = O(n) für konstantes s. Wenn m<n, kann man A und B vertauschen, um den benötigten Speicher zu reduzieren. Addiert man den für A und B benötigten Speicher, so beträgt die Raumkomplexität O(s min{m,n}+m+n) = O(m+n), wenn s eine Konstante ist.

Wie in Algorithmus DL werden die Hij-Werte zeilenweise berechnet. Das eindimensionale Array U wird verwendet, um die von Algorithmus DL berechneten H-Werte zu speichern, wenn die Zeile i berechnet wird. H sei die letzte für das Zeichen c berechnete Zeile. T sei dann die Zeile w-1 von H. Algorithmus 2 enthält den Pseudocode für LS_DL. Seine Korrektheit ergibt sich aus der Korrektheit des Algorithmus DL. Man beachte, dass swap(T],U) O(1) Zeit benötigt, da Zeiger auf 2 eindimensionale Arrays getauscht werden und nicht der Inhalt dieser Arrays. Die Anzahl der Cache-Fehler für LS_DL ist die gleiche wie für DL, wenn n entsprechend groß ist, da beide das gleiche Datenzugriffsmuster haben. Bei kleineren Instanzen weist LS_DL jedoch ein wesentlich besseres Cache-Verhalten auf. Zum Beispiel können wir aufgrund des geringeren Speicherbedarfs genügend LLC-Cache haben, um alle Daten in LS_DL zu speichern, aber nicht in DL (O(sn) gegenüber O(mn)).

Der cache-effiziente Linear-Space-Algorithmus S t r i p_D L

Wenn (s+1)n größer ist als die Größe des LLC-Caches, können wir die Cache-Misses im Vergleich zum Algorithmus LS_DL reduzieren, indem wir Hij durch Streifen der Breite q berechnen, wobei q kleiner als n ist (der letzte Streifen kann eine Breite kleiner als q haben). Dies ist in Abb. 3 dargestellt. Die Streifen werden mit dem Algorithmus LS_DL in der Reihenfolge 0, 1,… berechnet. Der von T und U in LS_DL benötigte Speicherplatz reduziert sich jedoch auf (s+1)q, da die Streifenbreite q statt n beträgt. Indem wir q klein genug wählen, können wir sicherstellen, dass Blöcke der von LS_DL verwendeten Arrays T und U nicht aus dem Cache entfernt werden, sobald sie eingebracht wurden. Wenn also jeder Eintrag von T und U 1 Wort einnimmt, dann haben wir bei einer Cache-Größe von lw q<lw/(s+1). Man beachte, dass der Cache zusätzlich zu T und U Teilmengen von A, B und anderen Arrays enthalten muss, die für die Weitergabe der Daten von einem Streifen zum nächsten benötigt werden.

Berechnung von H durch Streifen

Um die Daten von einem Streifen zum nächsten zu übertragen, verwenden wir einen zusätzlichen eindimensionalen Array-Streifen der Größe m und ein zweidimensionales s∗m-Array V. Das Array Strip speichert die Werte von H, die für die Spalte ganz rechts im Strip berechnet wurden. V gibt den H-Wert in der ganz rechten Spalte j der Zeile i von H an, die (a) in einem Streifen links von dem gerade berechneten liegt und (b) c=B.

Der Pseudocode für Strip_DL ist in Algorithmus 3 angegeben. Der Übersichtlichkeit halber verwendet dieser Pseudocode zwei Strip-Arrays (Zeilen 18 und 30) und zwei V-Arrays (Zeilen 24 und 32). Ein Satz von Arrays wird verwendet, um Daten zu holen, die für den vorherigen Strip berechnet wurden, und der andere Satz für Daten, die an den nächsten Strip weitergegeben werden sollen. In der eigentlichen Implementierung verwenden wir ein einziges Strip-Array und ein einziges V-Array, das die vom vorherigen Strip erhaltenen Werte mit den Werten überschreibt, die an den nächsten Strip übergeben werden sollen.

Die Zeit und die Komplexität von Strip_DL sind O(mn) bzw. O((s+1)m+(s+1)q+n) = O(sm+sq+n) = O(sm+n), da q eine Konstante ist. Wenn m>n, können wir A und B vertauschen, um Speicher zu sparen, und so wird die Raumkomplexität zu O(s min{m,n}+m+n) = O(m+n) für konstantes s.

Wenn wir den Cache-Miss analysieren, stellen wir fest, dass q so gewählt ist, dass U und T in den Cache passen. Wir gehen davon aus, dass die LRU-Ersetzungsregel nicht dazu führt, dass ein Block von U oder T während der Ausführung des Algorithmus Strip_DL verdrängt wird. Infolgedessen ist die Gesamtzahl der Cache-Misses aufgrund von U und T unabhängig von m und n und kann daher bei der Analyse ignoriert werden. Die Initialisierung von Strip und V führt zu m/w bzw. (s+1)m/w Lesezugriffen. Die Anzahl der Schreibzugriffe ist ungefähr gleich groß wie die Anzahl der Lesezugriffe. Die Berechnung für jeden Strip greift auf den Array-Strip in aufsteigender Reihenfolge des Index zu. Dies führt zu (annähernd) der gleichen Anzahl von Cache-Zugriffen wie in der Initialisierungsphase. Daher beträgt die Gesamtzahl der Cache-Misses aufgrund von Strips ungefähr (2m/w)(n/q+1). Für V ist zu beachten, dass bei der Berechnung des aktuellen Streifens auf die Elemente in jeder Zeile von V in nicht abnehmender Reihenfolge des Index zugegriffen wird (d. h. von links nach rechts) und dass für jedes Zeichen des Alphabets nur der zuletzt gelesene Wert im Cache gespeichert werden muss (d. h., es müssen höchstens s Werte gespeichert werden). Unter der Annahme, dass ein Wert von V nur dann aus dem Cache entfernt wird, wenn auf einen neuen Wert für dasselbe Zeichen zugegriffen wird, beträgt die Gesamtzahl der Lesefehler von V beim Berechnen eines einzelnen Streifens sm/w. Die Anzahl der Schreibversuche ist ungefähr gleich. V trägt also (2sm/w)(n/q+1) bei. Daher ist die Gesamtzahl der Cache-Misses für den Algorithmus Strip_DL ≈2(s+1)mn/(wq), wenn m und n groß sind.

Erinnern Sie sich, dass die ungefähre Anzahl der Cache-Misses für die Algorithmen DL und LS_DL mn(1+3/w) ist. Das ist (wq+3q)/(2s+2) mal so viel wie bei Strip_DL.

Der Linear-Space-Trace-Algorithmus L S D L_T R A C E

Obwohl die Algorithmen LS_DL und Strip_DL den Score (die Kosten) eines optimalen Traces (und damit einer optimalen Editiersequenz) bestimmen, der A in B transformiert, speichern diese Algorithmen nicht genug Informationen, um tatsächlich einen optimalen Trace zu bestimmen. Um eine optimale Spur im linearen Raum zu bestimmen, verwenden wir eine Strategie des Teilens und Eroberns, ähnlich der von Hirschberg für das einfache String-Editierproblem (d.h., Transpositionen sind nicht erlaubt) und Myers und Miller für das Sequenz-Alignment-Problem.

Wir sagen, dass eine Spur eine zentrale Kreuzung hat, wenn sie zwei Linien (u1,v1) und (u2,v2) enthält, u1<u2, so dass v1>n/2 und v2≤n/2 (Abb. 4).

Gelegenheiten zur Aufteilung derDL-Spur. a Keine Mittelkreuzung b Mit Mittelkreuzung

Lassen Sie T eine optimale Spur sein, die die Eigenschaften P2-P4 erfüllt. Wenn T keine Mittelkreuzung enthält, dann können seine Linien in die Mengen TL und TR aufgeteilt werden, so dass TL alle Linien (u,v)∈T mit v≤n/2 enthält und TR die restlichen Linien (Abb. 4a). Da es keine Mittelkreuzung gibt, haben alle Linien in TR einen u-Wert, der größer ist als der u-Wert jeder Linie in TL. Aus den Eigenschaften P2-P4 folgt, dass es ein i, 1≤i≤m gibt, so dass T die Vereinigung einer optimalen Spur für A und B und der für A und B ist. Sei H die Kosten der ersten optimalen Spur und H′ die der zweiten optimalen Spur. Wir sehen, dass, wenn T keine Mittelkreuzung hat, die Kosten von T

Wenn T eine Mittelkreuzung enthält, können seine Linien in drei Mengen, TL, TM und TR, unterteilt werden, wie in Abb. 4b gezeigt. (u1,v1) und (u2,v2) seien die Linien, die die Mittelkreuzung definieren. Man beachte, dass TL alle Linien von T mit v<v2 enthält, TR alle Linien mit v>v1, und TM={(u1,v1),(u2,v2)}. Man beachte auch, dass alle Zeilen in TL ein u<u1 und alle in TR ein u>u2 haben. Aus Eigenschaft P1 folgt, dass TL eine optimale Strecke für A und B und TR eine optimale Strecke für A und B ist. Da (u1,v1) und (u2,v2) ausgeglichene Linien sind, sind die Kosten von TM (u2-u1-1)+1+(v1-v2-1). Auch A≠A wie sonst führt das Ersetzen der sich kreuzenden Linien durch (u1,v2) und (u2,v1) zu einer Spur mit geringeren Kosten. Aus Eigenschaft P4 wissen wir, dass \(u_{1} = lastA\phantom {\dot {i}\!}\) und \(v_{2} = lastB\phantom {\dot {i}\!}\). Sei H die Kosten einer optimalen Spur für A und B und sei H′ die Kosten einer optimalen Spur für A und B. Wenn T also eine Mittelkreuzung hat, sind seine Kosten

wobei wir für die min{} 1≤u1<m versuchen und für jedes solche u1 v1 als das kleinste i>n/2 setzen, für das \(b_{i} = a_{u_{1}}\phantom {\dot {i}\!}\). Für jedes u1 untersuchen wir alle Zeichen außer \(\phantom {\dot {i}\!}a_{u_{1}}\) im Alphabet. Für jedes solche Zeichen c wird v2 auf das größte j≤n/2 gesetzt, für das bj=c ist, und u2 ist das kleinste i>u1, für das ai=c ist. Das Minimum wird also über (s-1)m Terme gebildet.

Lassen Sie Utop und Ttop die endgültigen U- und T-Arrays sein, die von LS_DL mit den Eingaben B und A berechnet werden, und Ubot und Tbot sind diese Arrays, wenn die Eingaben die Umkehrung von B und A sind. Aus diesen Arrays können wir leicht die H- und H′-Werte bestimmen, die zur Auswertung der Gleichungen 3 und 4 benötigt werden. Der Algorithmus LSDL_TRACE (Algorithmus 4) liefert den Pseudocode für unsere lineare Raumberechnung einer optimalen Spur. Er setzt voraus, dass LS_DL so modifiziert wurde, dass es die beiden Arrays U und T zurückgibt.

Für die Zeitkomplexität sehen wir, dass wir auf der obersten Ebene der Rekursion LS_DL zweimal mit den Strings A und B der Größe m bzw. n/2 aufrufen. Dies dauert höchstens amn Zeit für eine Konstante a. Die für die Berechnung der Gleichungen 3 und 4 benötigte Zeit ist O(sn) und kann in amn aufgehen, wenn man eine entsprechend große Konstante a verwendet. Auf der nächsten Ebene der Rekursion wird LS_DL viermal aufgerufen. Die Summe der Längen der A-Zeichenketten über diese 4 Aufrufe hinweg ist höchstens 2m und die B-Zeichenkette hat eine Länge von höchstens n/4. Die Zeit für diese vier Aufrufe ist also höchstens amn/2. Verallgemeinert man auf die übrigen Rekursionsebenen, so sieht man, dass der Algorithmus LSDL_TRACE amn(1+1/2+1/4+1/8+…)<2amn=O(mn) Zeit benötigt. Der Platzbedarf ist derselbe wie bei LS_DL (beachten Sie, dass die Parameter für diesen Algorithmus vertauscht wurden). Aus der Zeitanalyse folgt, dass die Anzahl der Cache-Misses ungefähr doppelt so hoch ist wie bei LS_DL, wenn der Algorithmus mit Strings der Größe m und n aufgerufen wird. Daher beträgt die ungefähre Anzahl der Cache-Misses für LSDL_TRACE 2mn(1+3/w).

Wir stellen fest, dass eine gewisse Reduzierung der tatsächlichen Laufzeit erreicht werden kann, indem A und B vertauscht werden, wenn A kürzer als B ist, wodurch sichergestellt wird, dass der kürzere String auf jeder Rekursionsebene aufgeteilt wird. Dadurch können wir die Rekursion schneller beenden.

Der Strip-Trace-Algorithmus S t r i p_T R A C E

Dieser Algorithmus unterscheidet sich von LSDL_TRACE dadurch, dass er eine modifizierte Version von Strip_DL und nicht eine modifizierte Version von LS_DL verwendet. Die modifizierte Version von Strip_DL gibt die von Strip_DL berechneten Arrays strip und V zurück. Dementsprechend verwendet Strip_TRACE Vtop und Vbot anstelle von Ttop und Tbot. Die asymptotische Zeitkomplexität von Strip_TRACE ist ebenfalls O(mn) und benötigt den gleichen Speicherplatz wie Strip_DL (beachten Sie, dass die Parameter für Strip_DL im Vergleich zu denen für Strip_TRACE vertauscht sind). Die Anzahl der Cache-Misses ist etwa doppelt so hoch wie bei Strip_DL.

Multi-Core-Algorithmen

In diesem Abschnitt beschreiben wir unsere Parallelisierungen des Algorithmus DL und der vier Single-Core-Algorithmen des vorherigen Abschnitts. Bei diesen Parallelisierungen wird davon ausgegangen, dass die Anzahl der Prozessoren im Verhältnis zur Stringlänge gering ist. Die Namenskonvention, die wir für die parallelen Versionen verwenden, ist das Hinzufügen von PP_ als Präfix zum Namen des Single-Core-Algorithmus.

Der Algorithmus P P_D L

Unsere parallele Version des Algorithmus DL, PP_DL, berechnet die Elemente in der gleichen Reihenfolge wie DL. Er beginnt jedoch mit der Berechnung einer Zeile, bevor die Berechnung der vorangegangenen Zeile abgeschlossen ist. Jedem Prozessor wird eine eindeutige Zeile zur Berechnung zugewiesen, die er von links nach rechts berechnet. Sei p die Anzahl der Prozessoren. Prozessor z wird zunächst mit der Berechnung der äußeren Schleife beauftragt, und zwar für i=z, 1≤i≤p. Prozessor z beginnt mit einer geeigneten Zeitverzögerung gegenüber dem Start von Prozessor z-1, so dass die Daten, die er für seine Berechnung benötigt, bereits von Prozessor z-1 berechnet wurden. In unserem Code entspricht die Zeitspanne zwischen dem Beginn der Berechnung zweier aufeinanderfolgender Zeilen der Zeit, die für die Berechnung von n/p Elementen benötigt wird. Nach Abschluss seiner Berechnung in Iteration i geht der Prozessor zu Iteration i+p der äußeren Schleife über. Die Zeitkomplexität von PP_DL ist O(mn/p).

Der Algorithmus P P_L S_D L

Während die allgemeine Parallelisierungsstrategie für PP_LS_DL dieselbe ist wie die in PP_DL verwendete, ist besondere Sorgfalt erforderlich, um eine Berechnung zu gewährleisten, die mit der von LS_DL identisch ist. Divergenzen in den Ergebnissen sind möglich, wenn zwei oder mehr Prozessoren gleichzeitig verschiedene Zeilen von H berechnen und dabei denselben Speicher verwenden. Dies ist zum Beispiel der Fall, wenn A=aaabc⋯ und p≥3. Wir beginnen mit Prozessor i, der mit der Berechnung der Zeile i von H beauftragt ist, 1≤i≤p. Nehmen wir an, dass U=x und T=y zu Beginn sind (x und y sind Adressen im Speicher). Aufgrund der Anweisung swap(T],U) in LS_DL beginnt Prozessor 1 mit der Berechnung der Zeile 1 von H, wobei er den Speicher ab der Adresse y verwendet. Wenn Prozessor 2 mit einer angemessenen Verzögerung wie in PP_DL beginnt, berechnet er Zeile 2 von H, wobei er den Speicher ab der Adresse x verwendet. Mit einer weiteren Verzögerung beginnt Prozessor 3 mit der Berechnung von Zeile 3 von H, wobei er wiederum Speicher verwendet, der an der Adresse y beginnt. Nun verwenden sowohl Prozessor 1 als auch Prozessor 3 denselben Speicher für die Berechnung verschiedener Zeilen von H, so dass die Gefahr besteht, dass H-Werte überschrieben werden, die für spätere Berechnungen benötigt werden. Als weiteres Beispiel betrachten wir A=ababa⋯ und p≥4. Nehmen wir an, dass U=x und T= anfänglich. Prozessor 1 beginnt mit der Berechnung der Zeile 1 unter Verwendung des Speichers y, dann beginnt mit Verzögerung Prozessor 2 mit der Berechnung der Zeile 2 unter Verwendung des Speichers z, dann beginnt Prozessor 3 mit der Berechnung der Zeile 3 unter Verwendung des Speichers x. Danach beginnt Prozessor 4 mit der Berechnung der Zeile 4 unter Verwendung des Speichers y. Zu diesem Zeitpunkt berechnet Prozessor 1 die Zeile 1 mit A=a und Prozessor 4 die Zeile 4 mit A=b, und beide Prozessoren verwenden denselben Zeilenspeicher y.

Bei p1 und p2 handelt es sich um zwei Prozessoren, die denselben Speicher zur Berechnung der Zeilen r1<r2 von H verwenden, und kein Prozessor verwendet diesen Speicher zur Berechnung einer Zeile zwischen r1 und r2. Aus dem in LS_DL verwendeten Zuweisungsschema ergibt sich, dass p1 die Zeile \(r_{1} = lastA-1\phantom {\dot {i}\!}) berechnet. Die H-Werte in dieser Zeile werden benötigt, um die Zeilen r1+1 bis r2 als \(\phantom {\dot {i}\!}r_{1} = lastA r_{1} < i \le r_{2}\). Diese Werte werden für die Zeilen i>r2 nicht benötigt, da für diese Zeilen \(\phantom {\dot {i}\!}lastA = r_{2} > r_{1} + 1 = lastA\). Sei j1 so, dass \(\phantom {\dot {i}\!}b_{j} = a_{r_{2}} = a_{r_{1} + 1}\). Dann gilt für j>j1, \(\phantom {\dot {i}\!}lastB \ge j_{1}\). Daher werden für j>j1 die Spalten 1 bis j1-2 der Zeile r1 nicht benötigt, um ein H in den Zeilen zwischen r1 und r2 zu berechnen.

Unser paralleler Code verwendet ein Synchronisationsschema, das auf den Beobachtungen des vorangegangenen Absatzes beruht, um das Überschreiben von Werten zu verzögern, die für spätere Berechnungen benötigt werden, und um eine korrekte Berechnung des DL-Abstands sicherzustellen. Unser Synchronisationsschema verwendet ein weiteres Array W, das mit 1 initialisiert wird. Nehmen wir an, dass ein Prozessor die Zeile i von H berechnet und dass A=a ist. Wenn dieser Prozessor zum ersten Mal auf ein a in B stößt, z. B. an der Position j1, erhöht er W. Wenn er auf das nächste a stößt, z. B. an j2, erhöht er W um 1. Wenn der Prozessor seine Berechnung der Zeile i beendet, werden die verbleibenden Positionen von W um 1 erhöht. Der Prozessor, der mit der Berechnung der Zeile q von H beauftragt ist, kann U berechnen, wenn W=q. Aus unseren früheren Beobachtungen folgt, dass bei W=q die alten Werte in den Speicherpositionen U überschrieben werden können, da sie für künftige Berechnungen nicht benötigt werden.

Die Zeitkomplexität dieses p-Prozessor-Algorithmus PP_LS_DL hängt von den Datensätzen ab, da die Synchronisationsverzögerung datenabhängig ist. Wir erwarten jedoch eine Laufzeitleistung von etwa O(mn/p), wenn die Zeichen in B ungefähr gleichmäßig verteilt sind.

Der Algorithmus P P_S t r i p_D L

In der parallelen Version PP_Strip_DL von Strip_DL wird Prozessor i zunächst mit der Berechnung von Streifen i, 1≤i≤p beauftragt. Nach Beendigung des ihm zugewiesenen Streifens j geht der Prozessor zur Berechnung von Streifen j+p über. Für die Synchronisierung wird ein Array-Signal verwendet. Bei der Berechnung einer Zeile r in dem ihm zugewiesenen Streifen s muss ein Prozessor warten, bis signal=s. signal wird von dem Prozessor, der an dem Streifen s-1 arbeitet, auf s gesetzt, wenn die Werte links von dem Streifen s, die für die Berechnung der Zeile r des Streifens s benötigt werden, berechnet wurden und keine Gefahr besteht, dass die Berechnungen für die Zeile r des Streifens s die von anderen Prozessoren benötigten V-Werte überschreiben. signal funktioniert ähnlich wie W in PP_LS_DL.

Wenn wir mit p Streifen arbeiten, benötigen wir p Kopien der von Strip_DL verwendeten Arrays U und T.

Die Zeitkomplexität von PP_Strip_DL hängt von der Synchronisationsverzögerung ab und dürfte ungefähr O(mn/p) betragen.

Der Algorithmus P P_D L_T R A C E

Dieser Algorithmus verwendet zunächst PP_DL zur Berechnung von H. Dann führt ein einzelner Prozessor einen Traceback durch, um die optimale Spur zu konstruieren. Für vernünftige Werte von p wird die Laufzeit von PP_DL dominiert, so dass die Komplexität von PP_DL_TRACE ebenfalls O(mn/p) ist.

Die Algorithmen P P_L S D L_T R A C E und P P_S t r i p_T R A C E

In LSDL_TRACE (Strip_TRACE) wird das Problem wiederholt in zwei Partitionen aufgeteilt und entweder LS_DL (Strip_DL) auf jede Partition angewendet. Bei der parallelen Version PP_LSDL_TRACE (PP_Strip_TRACE) wird die folgende Parallelisierungsstrategie verwendet:

• Jedes Teilproblem wird mit PP_LS_DL (PP_Strip_DL) gelöst, wenn die Zahl der unabhängigen Teilprobleme klein ist; alle p Prozessoren werden der parallelen Lösung eines einzigen Teilproblems zugewiesen. D.h. die Teilprobleme werden nacheinander gelöst.

• p Teilprobleme werden parallel mit LS_DL (Strip_DL) gelöst, um jedes Teilproblem seriell zu lösen, wenn die Anzahl der unabhängigen Teilprobleme groß ist,

Die Zeitkomplexität von PP_LSDL_TRACE und PP_Strip_TRACE ist O(mn/p).