Diskussion:Levenshtein-Distanz

Lewenstein oder Levenshtein?

Lewenstein oder Levenshtein? --213.68.63.68 11:39, 12. Jan 2005 (CET)

Danke für den Hinweis, muss Levenshtein heißen. Ich änder das gleich mal. Und den Namen vom NamensVater auch gleich, der sit auch falsch. --ElRaki ?! 15:53, 12. Jan 2005 (CET)

Habs nach Lewenstein-Distanz verschoben, wegen Diskussion:Wladimir Iossifowitsch Lewenstein. Diskussionen zum Namen am besten dort. Stern !? 02:07, 2. Mär 2005 (CET)

Levensteins Arbeiten wurden aber zuerst auf Russisch und Englisch veröffentlicht. Bei uns wurde der Begriff unter dem Namen "Levenshtein distance" aus dem Englischen übernommen. Daher ist hier - ausnahmsweise - die engl. Schreibweise durchaus vertretbar. --RokerHRO 10:19, 24. Nov. 2006 (CET)

libwikipedia

Ich habe jetzt mal den LD in C implementiert, zum einen als einfache Library Funktion zum anderen aber auch mit einem Riesigen Überbau, der das Verhalten der Funktion an der Konsole visualisiert. Downloadbar via CVS:

cvs -d :pserver:anonymous@bothie.sharedaemon.org:/home/public/bodo/cvs login
Password: (keines gesetzt)
cvs -d :pserver:anonymous@bothie.sharedaemon.org:/home/public/bodo/cvs co libwikipedia

dieser cvs server scheint leider nicht mehr verfügbar zu sein. David 14.08.08

Wie am Namen des Repos zu erkennen, soll dies nicht bei diesem einen Algorithmus bleiben, sondern eine ganze Sammlung werden, um genau zu sein, eine Sammlung aller Algorithmen, die in der Wikipedia erwähnt werden. Was haltet Ihr von dieser Idee? --Bodo Thiesen 11:03, 3. Mai 2005 (CEST)

Ich finde sie prinzipiell gut, sofern das Projekt wirklich auch weitergepflegt wird und du als einziger Maintainer nach ein paar Monaten die Lust daran verlierst und das Projekt dann verwaist. Vielleicht wäre es sinnvoller, du würdest deinen Code bei Wikisource einstellen, denn dafür ist Wikisource ja da. Du kannst dann ja gerne in regelmäßigen Abständen die dir genehmen Code-Stücke usw. aus Wikisource nehmen und zu einer fertigen "libwiki"-Bibliothek "bündeln" und die dann verbreiten. Was hältst du davon? --RokerHRO 08:18, 10 November 2005 (CET)

Optimierte Algorithmen, Erweiterung auf Wildcards

• Eine Optimierung der Berechnung der LD findet sich auch in

J. L. Spouge, Fast optimal alignment, Computer Applications in the Biosciences, Vol. 7, S. 1-7 (1991) ISSN 1367-4803

• In der c't 3/94, S. 230 ist ein Artikel von Jörg Michael, in dem er eine Erweiterung der LD auf Wildcards vorschlägt. Grundstrategie ist, in der Berechnung von d[i,j] (bzw. mathematisch $D_{i,j}$) wie folgt vorzugehen:

Zunächst noch einmal die ursprüngliche Berechnung rekapituliert: Ich habe das ganze etwas umgeschrieben und eine Gewichtungsfunktion $w(a_{i},b_{j})$ eingeführt, die die “Kosten” einer Transformation beschreibt):

$w:(a_{i},b_{j})\to \mathbb {R} :{\begin{cases}w(a_{i},b_{j})=0,&{\rm {f{\ddot {u}}r}}\quad a_{i}=b_{j}\ {\rm {(Alignment)}}\\w(a_{i},b_{j})=p,&{\rm {f{\ddot {u}}r}}\quad a_{i}\to b_{j}\ {\rm {(Substitution)}}\\w(-,b_{j})=q,&{\rm {f{\ddot {u}}r}}\quad -\to b_{j}\ {\rm {(Einf{\ddot {u}}gung)}}\\w(a_{i},-)=r,&{\rm {f{\ddot {u}}r}}\quad a_{i}\to -\ {\rm {(L{\ddot {o}}schung)}}\end{cases}}$,

wobei in der ursprünglichen Fassung die Kosten mit $p=q=r=1$ vorbesetzt sind (aber — und das wird im Artikel auch nicht erwähnt —  durchaus auch variabel, ja sogar jeweils von $a_{i}$ und $b_{j}$ abhängig sein können).

Die Matrixwerte ergeben sich damit zu:

$D_{i,j}=min{\begin{cases}D_{i-1,j-1}&+w(a_{i},b_{j})\ {\rm {(Alignment\ oder\ Substitution)}}\\D_{i-1,j}&+w(-,b_{j})\ {\rm {(Einf{\ddot {u}}gung)}}\\D_{i,j-1}&+w(a_{i},-)\ {\rm {(L{\ddot {o}}schung)}}\end{cases}}$

Die Funktion w wird nun auf die Benutzung der Wildcards ? und * erweitert, wobei eine Wildcard nur im zweiten Muster b vorkommen darf.¹ Hierdurch ändern sich nur die Kosten wie folgt:

• steht in $b_{j}$ ein ?, wird p = 0, d.h. jeder beliebige Buchstabe darf ohne Kosten durch ein ? substituiert werden.
• steht in $b_{j}$ ein *, werden p, q und r alle zu Null. Das heißt im Detail:
  • p = 0: Jedes Zeichen kann kostenfrei in ein * überführt werden.
  • q = 0: * kann auch für eine leere Sequenz stehen.
  • r = 0: Ein * paßt auf beliebig viele andere Zeichen.

Anmerkung:

¹ Hierzu ein Zitat aus dem c't-Artikel:

[…] Asymmetrie, die der erweiterten Levenshtein-Funktion innewohnt, weil sie Wildcards nur im Muster auswertet. Würde man Wildcards auch im Wort auswerten, hätten die Strings “An*der*Tiefenriede*129” und “Andreasplatz*9” die Distanz Null - ein sicherlich unerwünschtes Resultat.

-- Berndti 16:09, 16. Okt 2005 (CEST)

Levenshtein-Verbesserungen

Es gibt eine ganze Reihe von Verbesserungen des originalen Levenshtein, die weniger Speicher benötigen und/oder geringere Laufzeit aufweisen (Hirschberg, Ukkonen).

Gute Idee, habe einen Verweis auf den Hirschberg Algorithmus hinzugefügt. Ukkonen dient laut der englischen Wikipedia dem Erstellen von Suffix trees, also der exakten Textsuche, nicht dem Errechnen der Levenshtein Distanz. --Sulai 18:47, 24. Jul. 2007 (CEST)

Der Verweis auf Hirschberg ist irreführend, denn der Algorithmus mit linearem Speicherbedarf ist nicht kompliziert; siehe ebendiesen Verweis.

Der Hirschberg-Algorithmus macht nur Sinn, wenn man auch das zugehörige Alignment der beiden zu vergleichenden String bestimmen will. Nur die Levenshtein-Distanz mit linearem Platzbedarf zu berechnen ist trivial und wird nur anfangs im Hirschberg-Artikel nochmal erläutert. Der Verweis ist damit in der Tat irreführend.

Ich stimme dem zu. Ich würde von daher den Verweis auf den Hirschberg-Algorithmus verschieben zum Abschnitt "Verwandte Verfahren" und stattdessen einen Algorithmus einfügen (in Pseudocode, gleicher Stil), der die Levenhstein-Distanz mit linearem Platzbedarf berechnet.--Fas2 15:19, 18. Apr. 2008 (CEST)

Habe nun Hirschberg in das rechte Licht gerückt. --Gms 23:25, 25. Mär. 2010 (CET)

Pseudocode Damerau-Levenshtein-Distanz

In dem angegebenen Pseudocode zur DLD scheinen mir die folgenden IF-Bedingungen

if (str1[i - 1] == str2[j - 1])

...

if ((i > 1) && (j > 1) && (str1[i - 1] == str2[j - 2]) && (str1[i - 2] == str2[j - 1])){

falsch zu sein, sie erzeugt zumindest fehlerhafte Distanzwerte. Eine Änderung in

if (str1[i] == str2[j])

...

if ((i > 1) && (j > 1) && (str1[i] == str2[j - 1]) && (str1[i - 1] == str2[j])){

führt zu den richtigen Ergebnissen.

MKersting

Könntest du hierzu mal ein konkretes Beispiel bringen, bei dem die Distanzen abweichen? --Speifensender 10:09, 13. Jun. 2007 (CEST)

mich wundert, dass im Pseudocode die Zeile mit dieser langen if-Abfrage fehlt. In beiden Code-Beispielen ist sie drin. David 14.08.08

Algorithmen

Bei diesem enzyklopädischen und daher doch eher theoretischen Artikel wäre es sinnvoller, Algorithmen anzugeben und nicht komplette Programme. Erstens ist ein Algorithmus deutlich einfacher zu verstehen und zweitens auch universeller. Das angegebene Programm ist nicht einmal kommentiert. Man muß mühsam aus dem Programmcode (Kenntnis der Programmiersprache vorausgesetzt) das Verfahren zur manuellen Anwendung in der Tabelle extrahieren. --81.173.156.88 01:25, 24. Jul. 2007 (CEST)

Ich habe die zugrundeliegende Rekursionsgleichung eingefügt. Ich hoffe, sie ist dem allgemeinen Verständnis des Algorithmus und auch der Tabelle dienlich. --Sulai 19:25, 24. Jul. 2007 (CEST)

Was ebenfalls in der Algorithmendisziplin wichtig ist und hier m.E. fehlt, sind die Kosten des Algorithmus (Laufzeit) und eine kleine Differenzierung zu anderen phonetischen Algos im Bezug auf eben diese Kosten sowie auf die Komplexität und die Ergebnisqualität (hier abhängig von der Länge der zu vergleichenden Terme). --Sszhd 14:26, 3. Feb. 2010 (CET)

Habe nun Abschnitt zur Komplexität als Teil einer umfangreichen Überarbeitung hinzugefügt.

Sehe das auch problematisch, dass bisher komplette Programme im Artikel standen. Habe das C# Programm durch übersichtliche Rekursionsgleichungen ersetzt. Den anderen Pseudo-Code habe ich auch rausgenommen, weil das nur eine 1 zu 1 Übersetzung der Matrix-Rekurrenz war.

In der Einleitung habe ich die Synomisierung zu dem Begriff 'Edit-Distanz' rausgenommen, weil zur Berechnung der Edit-Distanz andere Kosten verwendet werden können.

--Gms 23:34, 25. Mär. 2010 (CET)

Beispiele

Das Beispiel Tier/Tor mit der Levenshtein-Distanz von 2 ist schonmal ganz hübsch. Allerdings wäre es hilfreich, wenn weiter unten im Text noch ein, zwei, drei Beispiele wären, vielleicht auch mit einem etwas längeren Wort. -- Gohnarch^░░░░ 16:08, 22. Feb. 2009 (CET)

Löschung und Einfügung

Habe eben die vermeintliche Korrektur rückgängig gemacht. Begründung: Seien $u,v$ zwei Sequenzen und $D(|u|,|v|)$ ihre Levenshtein-Distanz. In jeder Zelle $D(i,j)$ steht nun die optimale Distanz der Präfixe $u_{0,i}$ und $v_{0,j}$. Bei einer Löschung bzw. Einfügung wird nun nur ein weiteres Zeichen von $u$ bzw. $v$ verbraucht. D.h. wenn ich ein optimales Alignment $D(i,j)$ habe, und ich erweitere es um eine Löschung bzw. Einfügung dann muss ich das Resultat in $D(i+1,j)$ bzw. $D(i,j+1)$ notieren. Also lassen sich die Kosten für eine Löschung bzw. Einfügung in $i,j$ rekurrent durch $D(i-1,j)+1$ bzw. $D(i,j-1)+1$ berechnen.

HTH. --Gms 13:45, 8. Sep. 2009 (CEST)

Weblinks

Habe diesen Link nun zum 2. Mal rausgenommen. Problematisch sehe ich bei der Seite die penetrante Werbung a la: 'Nachdem Kenntnisstand der Autoren gelang es bisher nur der Firma [..] den Levensthein Algorithmus in höchster Geschwindigkeit zu implementieren.' Die Beschreibung ist zwar auf Deutsch, bringt aber keinen Mehrwert gegenüber dem WP-Artikel. Im Gegenteil, manche Statements dort sind falsch. Die anderen Links sind zwar auf Englisch, aber auch mit 0 Englisch-Kenntnissen kann man von den dortigen Backtracing-Visualisierung profitieren. --Gms 21:17, 6. Apr. 2010 (CEST)

Tippfehler in der Rekursion

Die Rekursion enthält einen Tippfehler:

Es muss heißen "u_i = v_j", nicht "u_i = v + j"! (nicht signierter Beitrag von 93.193.94.150 (Diskussion | Beiträge) 10:33, 14. Apr. 2010 (CEST))

Habe ich korrigiert. Danke für den Hinweis. Ansonsten für die Zukunft: Sei mutig usw. ;) --Gms 22:30, 21. Apr. 2010 (CEST)

Fehler in der Damerau-Rekurrenzformel

Das obere D_ij = min(...) müsste für i=1 oder j=1 greifen, das zweite D_ij = min(...) bei 2<=i<=m, 2<=j<=n. Das kann man leicht nachvollziehen, indem man ein Beispiel (z.B. u=AB, v=BA) rechnet. -- Fnatter 22:25, 5. Feb. 2012 (CET) darf ich das einfach ändern? -- Fnatter 19:14, 6. Feb. 2012 (CET)

"sie ist nicht größer als die Hamming-Distanz plus dem Längenunterschied der Zeichenketten"

Die Hamming-Distanz ist für unterschiedlich lange Zeichenketten gar nicht definiert, oder doch? --134.2.189.37 11:36, 24. Sep. 2014 (CEST)

Anwendung in der Genetik

Ich denke es sollte erwähnt werden, dass das Verfahren auch in der Genetik eine Rolle spielt, wo die genetische Distanz zweier Alelle berechnet wird ([1]), sowie bei der Erkennung möglicher Duplikate ([2]). Vielleicht am besten mit einem kurzen eigenen Abschnitt "Praktische Anwendungen"?--Nico b. (Diskussion) 14:14, 18. Nov. 2018 (CET)

Gute Webseite für Levistein-Distanz

Webseite um mit Levistein aber auch Jaro Winkler etc zu spielen: https://asecuritysite.com/forensics/simstring

46.126.16.87 11:39, 3. Sep. 2022 (CEST) Landev