Diskussion:Levenshtein-Distanz

aus Wikipedia, der freien Enzyklopädie
Letzter Kommentar: vor 2 Jahren von 46.126.16.87 in Abschnitt Gute Webseite für Levistein-Distanz
Zur Navigation springen Zur Suche springen

Lewenstein oder Levenshtein?

[Quelltext bearbeiten]

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)Beantworten

libwikipedia

[Quelltext bearbeiten]

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)Beantworten

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

[Quelltext bearbeiten]
  • 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 ) wie folgt vorzugehen:

Zunächst noch einmal die ursprüngliche Berechnung rekapituliert: Ich habe das ganze etwas umgeschrieben und eine Gewichtungsfunktion eingeführt, die die “Kosten” einer Transformation beschreibt):

,
wobei in der ursprünglichen Fassung die Kosten mit vorbesetzt sind (aber — und das wird im Artikel auch nicht erwähnt —  durchaus auch variabel, ja sogar jeweils von und abhängig sein können).

Die Matrixwerte ergeben sich damit zu:

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

  • steht in ein ?, wird p = 0, d.h. jeder beliebige Buchstabe darf ohne Kosten durch ein ? substituiert werden.
  • steht in 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.

1 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

[Quelltext bearbeiten]

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)Beantworten
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)Beantworten
Habe nun Hirschberg in das rechte Licht gerückt. --Gms 23:25, 25. Mär. 2010 (CET)Beantworten

Pseudocode Damerau-Levenshtein-Distanz

[Quelltext bearbeiten]

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)Beantworten


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

[Quelltext bearbeiten]

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)Beantworten

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)Beantworten

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)Beantworten

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)Beantworten

Beispiele

[Quelltext bearbeiten]

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)Beantworten

Löschung und Einfügung

[Quelltext bearbeiten]

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

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

[Quelltext bearbeiten]

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)Beantworten

Tippfehler in der Rekursion

[Quelltext bearbeiten]

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)) Beantworten

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

Fehler in der Damerau-Rekurrenzformel

[Quelltext bearbeiten]

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)Beantworten

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

[Quelltext bearbeiten]

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

Anwendung in der Genetik

[Quelltext bearbeiten]

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)Beantworten

Gute Webseite für Levistein-Distanz

[Quelltext bearbeiten]

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) LandevBeantworten