Diskussion:Levenshtein-Distanz

aus Wikipedia, der freien Enzyklopädie

Inhaltsverzeichnis

1 Lewenstein oder Levenshtein?
2 libwikipedia
3 Optimierte Algorithmen, Erweiterung auf Wildcards
- 3.1 Anmerkung:
4 Levenshtein-Verbesserungen
5 Pseudocode Damerau-Levenshtein-Distanz
6 Algorithmen

[Bearbeiten] 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)

[Bearbeiten] 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

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)

[Bearbeiten] 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 ur}\quad a_i = b_j \ {\rm(Alignment)} \\ w(a_i, b_j) = p, & {\rm f\ddot ur}\quad a_i \to b_j \ {\rm(Substitution)} \\ w(-, b_j) = q, & {\rm f\ddot ur}\quad - \to b_j \ {\rm(Einf\ddot ugung)} \\ w(a_i, -) = r, & {\rm f\ddot ur}\quad a_i \to - \ {\rm(L\ddot oschung)} \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 ugung)} \\ D_{i, j - 1}&+ w(a_i, -) \ {\rm(L\ddot oschung)} \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.

[Bearbeiten] 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)

[Bearbeiten] 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)

[Bearbeiten] 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)

[Bearbeiten] 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)

See also ebooksgratis.com: no banners, no cookies, totally FREE.