unscharfer Variablenvergleiich

[sprudel]

Hallo,
ich möchte zwei Variablen leicht unscharf vergleichen, also auch trotz leichten Schreibfehlern die Gleichheit feststellen können.
Wie geht das? Gibts da schon was vorgefertigtes?

LG Chris

[Marthog]

Ein fertiges Modul kenn ich jetzt nicht.

Du könntest die unterschiedlichen Zeichen zählen und dann vergleichen oder wenn es etwas mehr sein soll, auch einige Zeichenfolgen aus den Strings vergleichen.

[numerix]

Hallo,
ich möchte zwei Variablen leicht unscharf vergleichen, also auch trotz leichten Schreibfehlern die Gleichheit feststellen können.
Wie geht das? Gibts da schon was vorgefertigtes?

Das Problem ist die unscharfe Definition von "leicht unscharf".
Eventuell hilft dir das hier: http://de.wikipedia.org/wiki/Levenshtein-Distanz

[Hyperion]

Um was handelt es sich denn? Strings? Numerische Werte?

Für erstere könnte das interessant sein:
http://de.wikipedia.org/wiki/Levenshtein-Distanz

In diesem Thread hatte Gerold dazu auch schon auf ein Python Modul verwiesen:
http://www.python-forum.de/topic-22195, ... t&start=15

Ansonsten gibts noch die Möglichkeit mit der difflib zu arbeiten.

[cofi]

Man kann keine "Variablen" unscharf vergleichen.

Wenn du von Strings spricht, koennte dir http://de.wikipedia.org/wiki/Levenshtein-Distanz helfen.

Edit: Seufz.

[philistion]

Zur Ergänzung: http://www.guyrutenberg.com/2008/12/15/ ... in-python/

[snafu]

Möglicherweise könnte dir auch die ... ach, lassen wir den dummen Witz.

[mkesper]

@philiston: Soll angeblich besser/schneller sein: http://mwh.geek.nz/2009/04/26/python-da ... -distance/

[numerix]

Bei SPOJ gibt es die Aufgabe Edit distance, bei der nichts anderes zu tun ist, als die Levenshtein-Distanz zwischen zwei Zeichenketten zu berechnen. In diesem Zusammenhang habe ich mir auch die beiden Implementierungen angesehen, auf die in diesem Thread hingewiesen wurde.

Fazit: Beide Implementierungen sind fehlerhaft. Beispiel: Die "Distanz" zwischen HURQBOHP und QKHOZ beträgt 7, beide Algorithmen liefern jedoch 6 als Ergebnis. Davon abgesehen, sind beide Implementierung auch ineffizient. Konkret:

[A] http://www.guyrutenberg.com/2008/12/15/ ... in-python/
http://mwh.geek.nz/2009/04/26/python-da ... -distance/
[C] Meine eigene Version (zeige ich nicht, weil sich die o.g. SPOJ-Aufgabe damit lösen lässt ...)

Nimmt man zwei Zeichenketten mit den Längen m und n, dann wird bei [A] eine mxn-Matrix aufgebaut. Sieht man sich die Funktionsweise des Algorithmus einmal genauer an, merkt man schnell, dass das überflüssig ist. Abgesehen vom überflüssigen Speicherbedarf, führt das gerade in Python, das keine echten zweidimensionalen Arrays kennt, zu sehr schlechter Performance. Dass im konkreten Fall statt verschachtelter Listen mit einem Dictionary mit Tupeln als Schlüsseln gearbeitet wird, macht die Perfomance auch nicht gerade besser.
Algorithmus ist da schon um Längen besser, weil ohne komplette Matrix gearbeitet wird. Allerdings ist die Implementierung unnötig umständlich und an einigen Stellen auch ineffizient. Und, wie ich oben schon erwähnte, ohnehin fehlerhaft.

Zum Vergleich der Performance-Unterschiede habe ich die L-Distanz zweier zufällig generierter Zeichenketten mit je 2000 Zeichen berechnet (das mag in der Praxis unrealistisch sein, aber bei der o.g. SPOJ-Aufgabe geht es um diese Größenordnung). Die Laufzeiten auf meinem (sehr alten) Rechner waren (mit Verwendung von psyco!): [A] 228 s, 2,73 s und [C]: 0,16 s.

Grundlage für meinen eigenen Code war im Übrigen der gut verständliche Pseudo-Code des Wikipedia-Artikels.

[bords0]

Fazit: Beide Implementierungen sind fehlerhaft. Beispiel: Die "Distanz" zwischen HURQBOHP und QKHOZ beträgt 7, beide Algorithmen liefern jedoch 6 als Ergebnis.

Beides sind aber gar keine Implementierung der Levensthein-Distanz, sondern der Damerau-Levenshtein-Distanz. Zitat von der zweiten Webseite zum obigen Beispiel:
"Both algorithms give the correct answer for that pair: delete H, U, R, replace B with K, transpose O and H, replace P with Z. Six steps."

[philistion]

Fazit: Beide Implementierungen sind fehlerhaft. Beispiel: Die "Distanz" zwischen HURQBOHP und QKHOZ beträgt 7, beide Algorithmen liefern jedoch 6 als Ergebnis.

Beides sind aber gar keine Implementierung der Levensthein-Distanz, sondern der Damerau-Levenshtein-Distanz. Zitat von der zweiten Webseite zum obigen Beispiel:
"Both algorithms give the correct answer for that pair: delete H, U, R, replace B with K, transpose O and H, replace P with Z. Six steps."

Exakt. Die Damenrau-Levenshtein-Distanz liefert für das Vergleichen menschlicher Eingaben eben einen nützlicheren Wert, gerade das Vertauschen kommt doch sehr häufig vor und ist m.E. nicht 2 Operationen wert.

[numerix]

Danke euch beiden für die Korrektur und Hinweise. Mir war nicht bewusst, dass "Levensthein-Distanz" != "Damerau-Levenshtein-Distanz" gilt. Eine erhebliche Verbesserung der Performance der beiden verlinkten Algorithmen ist allerdings trotzdem möglich.

[philistion]

Wenn du das Thema Performance-Verbesserung schon ansprichst, welche Teilbereiche des Algorithmus B findest du besonders schlecht/langsam implementiert?
Mir erscheint dieser gar nicht so uneffektiv.

Diese Frage wäre sicher auch für andere User hier im Forum interessant.