Editierdistanz

In der Computerlinguistik und Informatik ist die Editierdistanz ein Maß für die Ähnlichkeit von Zeichenketten (z. B. Wörtern) . Sie quantifiziert, wie unähnlich zwei Zeichenketten sind, indem die minimale Anzahl an Operationen gezählt wird, die nötig sind, um die eine Zeichenkette in die andere zu transformieren. Editierdistanzen finden Anwendung in der Verarbeitung natürlicher Sprache , wo die automatische Rechtschreibkorrektur Korrekturvorschläge für ein falsch geschriebenes Wort ermitteln kann, indem sie Wörter aus einem Wörterbuch auswählt, die eine geringe Editierdistanz zum betreffenden Wort aufweisen. In der Bioinformatik kann sie verwendet werden, um die Ähnlichkeit von DNA- Sequenzen zu quantifizieren, die als Zeichenketten der Buchstaben A, C, G und T betrachtet werden können.

Verschiedene Definitionen der Editierdistanz verwenden unterschiedliche Mengen ähnlicher Operationen. Levenshtein-Distanz- Operationen sind das Entfernen, Einfügen oder Ersetzen eines Zeichens in der Zeichenkette. Da die Levenshtein-Distanz die gebräuchlichste Metrik ist, wird der Begriff Levenshtein-Distanz oft synonym mit Editierdistanz verwendet . ^{[ 1 ]}

Arten der Editierdistanz

Unterschiedliche Editierdistanzen ermöglichen unterschiedliche Arten von Zeichenkettenoperationen. Zum Beispiel:

Algorithmen und die zulässigen Operationen
Algorithmus	Einfügungen	Löschungen	Ersetzungen	Transposition
Levenshtein-Distanz	✓	✓	✓
Längste gemeinsame Teilfolge (LCS)	✓	✓
Hamming-Distanz			✓
Damerau–Levenshtein-Distanz	✓	✓	✓	✓
Jaro-Distanz				✓

Manche Editierdistanzen sind als parametrisierbare Metrik definiert, die anhand eines spezifischen Satzes zulässiger Editieroperationen berechnet wird, wobei jeder Operation Kosten (möglicherweise unendlich) zugewiesen werden. Dies wird durch DNA- Sequenzalignment- Algorithmen wie den Smith-Waterman-Algorithmus weiter verallgemeinert , bei denen die Kosten einer Operation davon abhängen, wo sie angewendet wird.

Formale Definition und Eigenschaften

Gegeben seien zwei Zeichenketten $a$ und $b$ über einem Alphabet $Σ$ (z. B. der Menge der ASCII- Zeichen, der Menge der Bytes [0..255] usw.). Die Editierdistanz d( $a$ , $b$ ) ist die gewichtete Folge von Editieroperationen mit minimalem Gewicht, die $a$ in $b$ transformiert . Eine der einfachsten Mengen von Editieroperationen ist die von Levenshtein im Jahr 1966 definierte: ^{[ 2 ]}

Einfügen eines einzelnen Symbols. Wenn

a

=

u

v

, dann ergibt das Einfügen des Symbols

x

u

x

v

. Dies kann auch als ε→

x

geschrieben werden , wobei ε die leere Zeichenkette bezeichnet.

Das Löschen eines einzelnen Symbols ändert

u

x

v

in

u

v

(

x

→ε).

Die Substitution eines einzelnen Symbols

x

durch ein Symbol

y

≠

x

ändert

u

x

v

zu

u

y

v

(

x

→

y

).

In Levenshteins ursprünglicher Definition hat jede dieser Operationen Einheitskosten (außer der Ersetzung eines Zeichens durch sich selbst, die keine Kosten verursacht), daher entspricht die Levenshtein-Distanz der minimalen Anzahl an Operationen, die erforderlich sind, um $a$ in $b$ zu transformieren . Eine allgemeinere Definition ordnet den Operationen nichtnegative Gewichtsfunktionen $w$ _{ins} ( $x$ ), $w$ _{del} ( $x$ ) und $w$ _{sub} ( $x$ , $y$ ) zu. ^{[ 2 ]}

Es wurden weitere primitive Operationen vorgeschlagen. Die Damerau-Levenshtein-Distanz zählt als eine einzige Korrektur. Ein häufiger Fehler ist die Vertauschung zweier benachbarter Zeichen, formal charakterisiert durch eine Operation, die $u$ $x$ $y$ $v$ in $u$ $y$ $x$ $v$ ändert . ^{[ 3 ]}^{[ 4 ]} Zur Korrektur von OCR- Ausgaben wurden Merge- und Split- Operationen verwendet, die ein einzelnes Zeichen durch ein Zeichenpaar ersetzen oder umgekehrt. ^{[ 4 ]}

Andere Varianten der Editierdistanz ergeben sich durch Einschränkung der Operationen. Die Distanz der längsten gemeinsamen Teilsequenz (LCS-Distanz) ist die Editierdistanz, bei der nur Einfügung und Löschung als Editieroperationen zulässig sind, jeweils mit Kosten von einer Einheit. ^{[ 1 ]}^{: 37} Analog dazu erhält man die Hamming-Distanz , indem man nur Ersetzungen zulässt (ebenfalls mit Kosten von einer Einheit) ; diese muss auf Zeichenketten gleicher Länge beschränkt sein. ^{[ 1 ]} Die Jaro-Winkler-Distanz kann aus einer Editierdistanz abgeleitet werden, bei der nur Transpositionen erlaubt sind.

Beispiel

Der Levenshtein-Abstand zwischen „Kätzchen“ und „sitzend“ beträgt 3. Ein minimales Bearbeitungsskript, das Ersteres in Letzteres umwandelt, lautet:

kitten → sitten (ersetze "s" durch "k")
sitt e n → sitt i n (ersetze „e“ durch „i“)
sittin → sittin g (füge "g" am Ende ein)

Die LCS-Distanz (nur Einfügungen und Löschungen) ergibt eine andere Distanz und ein minimales Bearbeitungsskript:

k itten → itten (streiche „k“ bei 0)
itten → s itten (füge "s" an Position 0 ein)
sitt e n → sittn (streiche „e“ bei 4)
sittn → sitt i n (füge „i“ bei 4 ein)
sittin → sittin g (füge "g" an Position 6 ein)

für Gesamtkosten/Entfernung von 5 Operationen.

Eigenschaften

Die Editierdistanz mit nichtnegativen Kosten erfüllt die Axiome einer Metrik und führt zu einem metrischen Raum von Zeichenketten, wenn die folgenden Bedingungen erfüllt sind: ^{[ 1 ]}^{: 37}

Jeder Bearbeitungsvorgang verursacht positive Kosten;
Zu jeder Operation gibt es eine Umkehroperation mit gleichen Kosten.

Aufgrund dieser Eigenschaften sind die metrischen Axiome wie folgt erfüllt:

d

(

a

,

b

) = 0 genau dann, wenn a=b, da jede Zeichenkette trivial mit genau null Operationen in sich selbst transformiert werden kann.

d

(

a

,

b

) > 0 wenn

a

≠

b

, da dies mindestens eine Operation mit Kosten ungleich Null erfordern würde.

d

(

a

,

b

) =

d

(

b

,

a

) aufgrund der Gleichheit der Kosten jeder Operation und ihrer Umkehrung.

Dreiecksungleichung:

d

(

a

,

c

) ≤

d

(

a

,

b

) +

d

(

b

,

c

). ^{[ 5 ]}

Die Levenshtein-Distanz und die LCS-Distanz mit Einheitskosten erfüllen die oben genannten Bedingungen und somit auch die metrischen Axiome. Varianten der Editierdistanz, die keine eigentlichen Metriken darstellen, wurden ebenfalls in der Literatur betrachtet. ^{[ 1 ]}

Weitere nützliche Eigenschaften von Editierdistanzen mit Einheitskosten sind:

Der LCS-Abstand ist nach oben durch die Summe der Längen zweier Zeichenketten beschränkt. ^{[ 1 ]}^{: 37}
Die LCS-Distanz ist eine obere Schranke für die Levenshtein-Distanz.
Für Zeichenketten gleicher Länge ist die Hamming-Distanz eine obere Schranke für die Levenshtein-Distanz. ^{[ 1 ]}

Ungeachtet der Kosten/Gewichte gilt für alle Editierdistanzen folgende Eigenschaft:

Wenn $a$ und $b$ ein gemeinsames Präfix haben, hat dieses Präfix keinen Einfluss auf die Distanz. Formal ausgedrückt: Wenn $a$ = $uv$ und $b$ = $uw$ , dann ist $d$ ( $a$ , $b$ ) = $d$ ( $v$ , $w$ ). ^{[ 4 ]} Dies ermöglicht eine Beschleunigung vieler Berechnungen mit Editierdistanzen und Editierskripten, da gemeinsame Präfixe und Suffixe in linearer Zeit übersprungen werden können.

Berechnung

Der erste Algorithmus zur Berechnung der minimalen Editierdistanz zwischen zwei Zeichenketten wurde 1964 von Damerau veröffentlicht. ^{[ 6 ]}

Gemeinsamer Algorithmus

Unter Verwendung der ursprünglichen Operationen von Levenshtein ist die (nicht-symmetrische) Editierdistanz von zu gegeben durch , definiert durch die Rekursionsgleichung ^[²^]. $a=a_{1}\ldots a_{m}$ $b=b_{1}\ldots b_{n}$ $d_{mn}$

{\begin{aligned}d_{i0}&=\sum _{k=1}^{i}w_{\mathrm {del} }(a_{k}),&&\quad {\text{for}}\;1\leq i\leq m\\d_{0j}&=\sum _{k=1}^{j}w_{\mathrm {ins} }(b_{k}),&&\quad {\text{for}}\;1\leq j\leq n\\d_{ij}&={\begin{cases}d_{i-1,j-1}&{\text{for}}\;a_{i}=b_{j}\\\min {\begin{cases}d_{i-1,j}+w_{\mathrm {del} }(a_{i})\\d_{i,j-1}+w_{\mathrm {ins} }(b_{j})\\d_{i-1,j-1}+w_{\mathrm {sub} }(a_{i},b_{j})\end{cases}}&{\text{for}}\;a_{i}\neq b_{j}\end{cases}}&&\quad {\text{for}}\;1\leq i\leq m,1\leq j\leq n.\end{aligned}}

Dieser Algorithmus kann verallgemeinert werden, um Transpositionen zu behandeln, indem ein weiterer Term in die Minimierung der rekursiven Klausel hinzugefügt wird. ^{[ 3 ]}

Die direkte, rekursive Auswertung dieser Rekursion benötigt exponentielle Zeit . Daher wird sie üblicherweise mithilfe eines dynamischen Programmierungsalgorithmus berechnet , der gemeinhin Wagner und Fischer zugeschrieben wird ^{[ 7 ]} , obwohl er auf mehrere Weiterentwicklungen zurückgeht ^{[ 2 ]}^{[ 3 ]} . Nach Abschluss des Wagner-Fischer-Algorithmus lässt sich eine minimale Folge von Bearbeitungsoperationen als Rückverfolgung der während des dynamischen Programmierungsalgorithmus verwendeten Operationen ab dem Zeitpunkt ablesen . $d_{mn}$

Dieser Algorithmus hat eine Zeitkomplexität von Θ( $m,$ $n$ ), wobei $m$ und $n$ die Längen der Zeichenketten sind. Die Speicherkomplexität der vollständig erstellten dynamischen Programmiertabelle beträgt ebenfalls Θ( $m,$ $n$ ) . Diese lässt sich auf Θ(min( $m$ , $n$ )) verbessern, da der Algorithmus zu jedem Zeitpunkt nur zwei Zeilen (oder zwei Spalten) im Speicher benötigt. Diese Optimierung verhindert jedoch das Auslesen der minimalen Folge von Bearbeitungsoperationen. ^{[ 3 ]} Eine Lösung mit linearem Speicherbedarf bietet der Algorithmus von Hirschberg . ^{[ 8 ]}^{: 634} Ein allgemeines rekursives Divide-and-Conquer-Framework zur Lösung solcher Rekursionen und zur Extraktion einer optimalen Operationsfolge mit cache-effizientem Speicherbedarf, der linear zur Größe der Eingabe ist, wurde von Chowdhury, Le und Ramachandran vorgestellt. ^{[ 9 ]}

Verbesserte Algorithmen

Aufbauend auf dem oben beschriebenen Wagner-Fisher-Algorithmus beschreibt Ukkonen mehrere Varianten ^{[ 10 ].} Eine davon nimmt zwei Zeichenketten und eine maximale Editierdistanz $s$ entgegen und gibt min( $s$ , $d$ ) zurück . Dies wird erreicht, indem nur ein Teil der dynamischen Programmiertabelle entlang ihrer Diagonalen berechnet und gespeichert wird. Dieser Algorithmus benötigt eine Laufzeit von O( $s$ × min( $m$ , $n$ )) , wobei $m$ und $n$ die Längen der Zeichenketten sind. Die Speicherkomplexität beträgt O( $s²$ ) oder O( $s$ ) , je nachdem ^, ob die Editiersequenz ausgelesen werden muss. ^{[ 3 ]}

Weitere Verbesserungen durch Landau , Myers und Schmidt [1] führen zu einem Algorithmus mit einer Laufzeit von O( $s$ ² + max( $m$ , $n$ )) . ^{[ 11 ]}

Bei einem endlichen Alphabet und Bearbeitungskosten, die Vielfache voneinander sind, ist der schnellste bekannte exakte Algorithmus der von Masek und Paterson ^{[ 12 ]} mit einer Laufzeit im schlechtesten Fall von O(nm/logn).

Anwendungen

Die Editierdistanz findet Anwendung in der Computerbiologie und der Verarbeitung natürlicher Sprache, z. B. bei der Korrektur von Rechtschreibfehlern oder OCR-Fehlern, und beim approximativen String-Matching , wo es darum geht, Übereinstimmungen für kurze Zeichenketten in vielen längeren Texten zu finden, in Situationen, in denen eine geringe Anzahl von Unterschieden zu erwarten ist.

Neben der Berechnung des Abstands zwischen zwei Zeichenketten existieren verschiedene Algorithmen, die auch verwandte Problemtypen lösen.

Der Hirschberg-Algorithmus berechnet die optimale Ausrichtung zweier Zeichenketten, wobei Optimalität als Minimierung der Editierdistanz definiert ist.
Die approximative Zeichenkettenübereinstimmung lässt sich mithilfe der Editierdistanz formulieren. Ukkonens Algorithmus von 1985 nimmt eine Zeichenkette $p$ , das sogenannte Muster, und eine Konstante $k$ entgegen ; er konstruiert dann einen deterministischen endlichen Automaten , der in einer beliebigen Zeichenkette $s$ eine Teilzeichenkette findet, deren Editierdistanz zu $p$ höchstens $k beträgt$ ^{[ 13 ]} (vgl. den Aho-Corasick-Algorithmus , der analog einen Automaten konstruiert, um nach beliebigen Mustern zu suchen, jedoch ohne Editieroperationen zuzulassen). Ein ähnlicher Algorithmus für die approximative Zeichenkettenübereinstimmung ist der Bitap-Algorithmus , der ebenfalls mithilfe der Editierdistanz definiert ist.
Levenshtein-Automaten sind endliche Automaten, die eine Menge von Zeichenketten innerhalb einer begrenzten Editierdistanz zu einer festen Referenzzeichenkette erkennen. ^{[ 4 ]}

Sprachliche Bearbeitungsdistanz

Eine Verallgemeinerung der Editierdistanz zwischen Zeichenketten ist die Spracheditierdistanz zwischen einer Zeichenkette und einer Sprache, üblicherweise einer formalen Sprache . Anstatt die Editierdistanz zwischen zwei Zeichenketten zu betrachten, ist die Spracheditierdistanz die minimale Editierdistanz, die zwischen einer festen Zeichenkette und einer beliebigen Zeichenkette aus einer Menge von Zeichenketten erreicht werden kann. Formaler ausgedrückt: Für jede Sprache L und jede Zeichenkette x über einem Alphabet $Σ$ ist die Spracheditierdistanz d( L , x ) gegeben durch ^{[ 14 ]} , wobei die Editierdistanz der Zeichenkette ist. Wenn die Sprache L kontextfrei ist , existiert ein dynamischer Programmieralgorithmus mit kubischer Laufzeit, der 1972 von Aho und Peterson vorgeschlagen wurde und die Spracheditierdistanz berechnet. ^[¹⁵^] Für weniger ausdrucksstarke Grammatikfamilien, wie z. B. reguläre Grammatiken , existieren schnellere Algorithmen zur Berechnung der Editierdistanz. ^[¹⁶^] $d(L,x)=\min _{y\in L}d(x,y)$ $d(x,y)$

Die Editierdistanz in Sprachen findet vielfältige Anwendung, beispielsweise bei der RNA-Faltung, der Fehlerkorrektur und bei Lösungen für das Problem der optimalen Stapelgenerierung. ^{[ 14 ]}^{[ 17 ]}

Siehe auch

Referenzen

^{Navarro ,}^{Gonzalo (1.}^März 2001). „Eine ^geführte^Tour zur approximativen String-Suche“ ( PDF) . ACM Computing Surveys . 33 (1): 31–88 ^. CiteSeerX 10.1.1.452.6317 . doi : 10.1145/375360.375365 . S2CID 207551224. Abgerufen am ^19. März 2015 .
^ ^a ^b ^c ^d Daniel Jurafsky; James H. Martin. Sprachverarbeitung . Pearson Education International. S. 107–111 .
^ ^a ^b ^c ^d ^e Esko Ukkonen (1983). On approximate string matching . Foundations of Computation Theory. Springer. pp. 487– 495. doi : 10.1007/3-540-12689-9_129 .
^ ^a ^b ^c ^d Schulz, Klaus U.; Mihov, Stoyan (2002). „Schnelle Stringkorrektur mit Levenshtein-Automaten“. International Journal of Document Analysis and Recognition . 5 (1): 67–85 . CiteSeerX 10.1.1.16.652 . doi : 10.1007/s10032-002-0082-8 . S2CID 207046453 .
^ Lei Chen; Raymond Ng (2004). On the marriage of L _p -norms and edit distance (PDF) . Proc. 30th Int'l Conf. on Very Large Databases (VLDB). Vol. 30. doi : 10.1016/b978-012088469-8.50070-x .
^ Kukich, Karen (1992). „Techniken zur automatischen Korrektur von Wörtern in Texten“ (PDF) . ACM Computing Surveys . 24 (4): 377–439 . doi : 10.1145/146370.146380 . S2CID 5431215. Archiviert vom Original (PDF) am 27.09.2016 . Abgerufen am 09.11.2017 .
^ R. Wagner; M. Fischer (1974). „Das String-zu-String-Korrekturproblem“ . J. ACM . 21 : 168–178 . doi : 10.1145/321796.321811 . S2CID 13381535 .
^ Skiena, Steven (2010). The Algorithm Design Manual (2. Aufl.). Springer Science+Business Media . Bibcode : 2008adm..book.....S . ISBN 978-1-849-96720-4Die
^ Chowdhury, Rezaul; Le, Hai-Son; Ramachandran, Vijaya (Juli 2010). „Cache-oblivious dynamic programming for bioinformatics“. IEEE/ACM Transactions on Computational Biology and Bioinformatics . 7 (3): 495–510 . Bibcode : 2010ITCBB...7..495C . doi : 10.1109/TCBB.2008.94 . PMID 20671320. S2CID 2532039 .
^ Ukkonen, Esko (1985). „Algorithmen für approximatives String-Matching“ (PDF) . Information and Control . 64 ( 1–3 ): 100–118 . doi : 10.1016/S0019-9958(85)80046-2 .
^ Landau; Myers ; Schmidt (1998). „Inkrementeller Stringvergleich“. SIAM Journal on Computing . 27 (2): 557–582 . CiteSeerX 10.1.1.38.1766 . doi : 10.1137/S0097539794264810 .
^ Masek, William J.; Paterson, Michael S. (Februar 1980). „Ein schnellerer Algorithmus zur Berechnung von String-Editierdistanzen“ . Journal of Computer and System Sciences . 20 (1): 18–31 . doi : 10.1016/0022-0000(80)90002-1 . hdl : 1721.1/148933 . ISSN 0022-0000 .
^ Esko Ukkonen (1985). „Ungefähre Muster in Strings finden“. J. Algorithmen . 6 : 132–137 . doi : 10.1016/0196-6774(85)90023-9 .
^Bringmann , Karl; Grandoni, Fabrizio; Saha, Barna ; Williams, Virginia Vassilevska (2016). „Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product“ ⁽ PDF ) . 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) . S. 375–384 . arXiv : 1707.05095 . doi : 10.1109/focs.2016.48 . ISBN 978-1-5090-3933-3. S2CID 17064578 .
^ Aho, A.; Peterson, T. (1972-12-01). „Ein Parser mit minimaler Distanz und Fehlerkorrektur für kontextfreie Sprachen“. SIAM Journal on Computing . 1 (4): 305–312 . doi : 10.1137/0201022 . ISSN 0097-5397 .
^ Wagner, Robert A. (1974). „Order-n correction for regular languages“ . Communications of the ACM . 17 (5): 265–268 . doi : 10.1145/360980.360995 . S2CID 11063282 .
^ Saha, B. (1. Oktober 2014). Das Dyck-Sprach-Editdistanzproblem in nahezu linearer Zeit . 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. S. 611–620 . doi : 10.1109/FOCS.2014.71 . ISBN 978-1-4799-6517-5. S2CID 14806359 .

[navarnarutoro-1] {Navarro ,}^{Gonzalo (1.}^März 2001). „Eine ^geführte^Tour zur approximativen String-Suche“ ( PDF) . ACM Computing Surveys . 33 (1): 31–88 ^. CiteSeerX 10.1.1.452.6317 . doi : 10.1145/375360.375365 . S2CID 207551224. Abgerufen am ^19. März 2015 .

[slp-2] Daniel Jurafsky; James H. Martin. Sprachverarbeitung . Pearson Education International. S. 107–111 .

[ukkonen83-3] Esko Ukkonen (1983). On approximate string matching . Foundations of Computation Theory. Springer. pp. 487– 495. doi : 10.1007/3-540-12689-9_129 .

[ssm-4] Schulz, Klaus U.; Mihov, Stoyan (2002). „Schnelle Stringkorrektur mit Levenshtein-Automaten“. International Journal of Document Analysis and Recognition . 5 (1): 67–85 . CiteSeerX 10.1.1.16.652 . doi : 10.1007/s10032-002-0082-8 . S2CID 207046453 .

[5] Lei Chen; Raymond Ng (2004). On the marriage of L _p -norms and edit distance (PDF) . Proc. 30th Int'l Conf. on Very Large Databases (VLDB). Vol. 30. doi : 10.1016/b978-012088469-8.50070-x .

[6] Kukich, Karen (1992). „Techniken zur automatischen Korrektur von Wörtern in Texten“ (PDF) . ACM Computing Surveys . 24 (4): 377–439 . doi : 10.1145/146370.146380 . S2CID 5431215. Archiviert vom Original (PDF) am 27.09.2016 . Abgerufen am 09.11.2017 .

[7] R. Wagner; M. Fischer (1974). „Das String-zu-String-Korrekturproblem“ . J. ACM . 21 : 168–178 . doi : 10.1145/321796.321811 . S2CID 13381535 .

[8] Skiena, Steven (2010). The Algorithm Design Manual (2. Aufl.). Springer Science+Business Media . Bibcode : 2008adm..book.....S . ISBN 978-1-849-96720-4Die

[CLR-08-9] Chowdhury, Rezaul; Le, Hai-Son; Ramachandran, Vijaya (Juli 2010). „Cache-oblivious dynamic programming for bioinformatics“. IEEE/ACM Transactions on Computational Biology and Bioinformatics . 7 (3): 495–510 . Bibcode : 2010ITCBB...7..495C . doi : 10.1109/TCBB.2008.94 . PMID 20671320. S2CID 2532039 .

[10] Ukkonen, Esko (1985). „Algorithmen für approximatives String-Matching“ (PDF) . Information and Control . 64 ( 1–3 ): 100–118 . doi : 10.1016/S0019-9958(85)80046-2 .

[11] Landau; Myers ; Schmidt (1998). „Inkrementeller Stringvergleich“. SIAM Journal on Computing . 27 (2): 557–582 . CiteSeerX 10.1.1.38.1766 . doi : 10.1137/S0097539794264810 .

[12] Masek, William J.; Paterson, Michael S. (Februar 1980). „Ein schnellerer Algorithmus zur Berechnung von String-Editierdistanzen“ . Journal of Computer and System Sciences . 20 (1): 18–31 . doi : 10.1016/0022-0000(80)90002-1 . hdl : 1721.1/148933 . ISSN 0022-0000 .

[13] Esko Ukkonen (1985). „Ungefähre Muster in Strings finden“. J. Algorithmen . 6 : 132–137 . doi : 10.1016/0196-6774(85)90023-9 .

[:0-14] Bringmann , Karl; Grandoni, Fabrizio; Saha, Barna ; Williams, Virginia Vassilevska (2016). „Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product“ ⁽ PDF ) . 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) . S. 375–384 . arXiv : 1707.05095 . doi : 10.1109/focs.2016.48 . ISBN 978-1-5090-3933-3. S2CID 17064578 .

[15] Aho, A.; Peterson, T. (1972-12-01). „Ein Parser mit minimaler Distanz und Fehlerkorrektur für kontextfreie Sprachen“. SIAM Journal on Computing . 1 (4): 305–312 . doi : 10.1137/0201022 . ISSN 0097-5397 .

[16] Wagner, Robert A. (1974). „Order-n correction for regular languages“ . Communications of the ACM . 17 (5): 265–268 . doi : 10.1145/360980.360995 . S2CID 11063282 .

[17] Saha, B. (1. Oktober 2014). Das Dyck-Sprach-Editdistanzproblem in nahezu linearer Zeit . 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. S. 611–620 . doi : 10.1109/FOCS.2014.71 . ISBN 978-1-4799-6517-5. S2CID 14806359 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ].

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[

[

[ 17 ]