Levenshtein Index

Java-Forum Allgemeine Themen
1

nahe Farben zu suchen mag leicht gehen
http://forum.byte-welt.net/threads/12287-Farbsuche-in-Palette-(nearest-Color-Index)

aber geht das auch bei der Königsdisziplin Strings, Zeichenkettten?
als Maß der Ähnlichkeit meinetwegen http://de.wikipedia.org/wiki/Levenshtein-Distanz

sortiert/ indexiert man 10.000 bekannte Wörter nach Anfangsbuchstaben ist von falsch geschriebenen ‘Levenstein’ auf ‘Levenshtein’ schnell geschlossen,
aber was ist bei Tippfehler am Anfang ‘Klevenshtein’?
wie kann man möglichst schnell einen nahen Nachbarn finden, ohne mit allen bekannten Wörtern einzeln zu vergleichen?

2

Der Wikipedia-Artikel hat doch schon den richtigen Link: http://de.wikipedia.org/wiki/Hirschberg-Algorithmus#Berechnung_der_Levenshtein-Distanz_auf_linearem_Speicherplatz

3

ist das ein Algorithmus um die Levenshtein-Distanz zwischen zwei konkreten Strings zu bestimmen?
für sich sicher nett und nötig, aber im anderen Thread hilft wohl auch kein Vergleichstest zwischen zwei einzelnen Farbwerten

ich meinte wie dort einen allgemeinen Index/ Hashwert/ räumliche Einteilung der Strings,
irgendwas was mir hilft, einen ähnlichen String zu X zu finden, ohne alle 10.000 einzeln anschauen zu müssen,
sofortige Eingrenzung auf 100 Kandidaten,

ich befürchte und hoffe zugleich, dass es was ganz triviales bekanntest gibt, um so ein wichtiges Problem gut zu lösen,
wenn dann hat es sich aber bisher immer gut vor meinen Augen versteckt,
ebenso eine Gegenaussage oder allgemeine Beurteilung, warum das vielleicht unmöglich ist

4

So ganz aus der Hüfte geschossen.

Wie sieht es mit k-means aus?

Aus 10.000 Strings 500 Zufällig auswählen und als Mediane auswählen und dann die 10.000 Strings dem nahestehendsten Median zuordnen.

Danach schauen ob man für ein Cluster einen besseren Median findet und die 10.000 Strings neu auf die neuen Mediane verteilen. Ggf. mehrmals wiederholen.

Damit sollte man dann mittelfristig eine gute Clusterisierung bekommen.

Ein neuer String wird dann dem besten Cluster zugeordnet und man müsste dann nur noch innerhalb des Clusters nach dem besten Wert suchen.
Und ein Cluster könnte man im vorraus wiederum mit k-Means unterteilen.

5

Du brauchst doch nur was, zum “Vorfiltern” und willst dann mit der Levenshtein-Distanz weitersuchen?

Länge +/- 1
Anzahl Vokale +/- 1

würde doch normalerweise schon ziemlich stark “aussieben”, wobei sicher keine Strings mit großer Entfernung zusammen gruppiert werden, oder ist das zu schwach?

6

Ich werfe das Bayes Theorem in den Raum. Dabei wird aus den umliegenden Wörtern die Wahrscheinlichkeit berechnet, welches Wort, dort wohl stehen könnte. Simpel ist das aber alles nicht. Auch bei k-Means muss man sich einiges anschauen. Wenn man mal eine MultiMap hat, geht es natürlich etwas schneller.

7

Analog zu Bildern könnte man ja festhalten, welche Buchstaben in welchen Wörtern wie oft vorkommen. Die Wortliste kann man dann auch nach den Hashes der am häufigsten vorkommenden Buchstaben sortieren und dann kann man die Suche schon mal auf passende Hashcodes eingrenzen. Auch mal eben aus der Hüfte ins Blaue geschossen.

8

[QUOTE=Bleiglanz]Du brauchst doch nur was, zum „Vorfiltern“ und willst dann mit der Levenshtein-Distanz weitersuchen?
[/QUOTE]
konkret habe ich nichts im Sinn, nur die Gelegenheit des anderen Themas genutzt :wink:

meine Vorstellung ist so allgemein und variabel wie sich jeder was passendes denken kann:
ähnliche Strings finden, etwa Tippfehler in Adressen und Namen,

der Fehler kann nicht nur vorne kommen (in meinem Beispiel ‚Klevenshtein‘) sondern theoretisch an jeder Position, auch mehrere Fehler,
Fehler = falsche Buchstaben/ zu viele Buchstaben/ zu wenige Buchstaben, was immer es so gibt,

dazu passt die Levenshtein-Distanz ja besonders gut, denke ich,
habe aber nur abstrakt irgendeine ‚Ähnlichkeit‘ im Sinn, das menschliche Urteil,
z.B. wieder zur Vorlage Entscheidung ob Tippfehler und Gleichheit

[QUOTE=Unregistered;96056]So ganz aus der Hüfte geschossen.

Wie sieht es mit k-means aus?
[/quote]
einzelne Theorien müssen hier wohl nicht besprochen werden,
falls nicht wer was fertiges hat und von guten Erfahrungen damit berichten kann,

‚k-means‘ war aber für mich schon als Begriff neu, insofern hilfreich, ja,
wobei ich eher auf Gleichverteilung als echte Konzentrationen tippe bei beliebigen Problemen, zweifle etwas

noch mehr gewinne ich aber dann doch und allein schon aus dem genannten Begriff ‚Cluster‘ :wink:
nämlich nun endlich Links a la

mit Link auf interessantes
http://matpalm.com/resemblance/simhash/
ergo

(Similarity Estimation Techniques from Rounding Algorithms)

das Thema wird also doch in der Welt behandelt, wie könnte es auch anders sein

zu weiterem genannten wie ‚Bayes Theorem‘ habe ich jetzt vorerst doch gar nicht erst neu nachgeschaut,
wie gesagt habe ich nichts konkretes im Sinn, also auf keine Antworten warten :wink:

9

Das schöne an k-means ist das man nur zwei Funktionen implementieren muss.
(A, B)-> Number, Abstand zwischen Objekten (Levenstein)
(A, B)-> C, ein Mittelwert

Z.B. (Tier, Tuer) -> T?er
Hat man dies, dann kann man das Verfahren auf sehr viel Anwenden.

10

Ich denke auch, dass hier zwei Dinge vermischt werden.

Das eine ist die Definition einer (sinnvollen?!) Sistanzfunktion zwischen Wörtern. Den Tippfehler da drin lass’ ich jetzt mal absichtlich stehen :smiley: Dabei kann man sich verschiedene Varianten von „sinnvoll“ vorstellen: Die Levenshtein-Distanz ist sehr allgemein und so gesehen „neutral“, da sie auf beliebige Strings angewendet werden kann (und - wenn auch nicht unter diesem Namen - auch angewendet wird - nämlich z.B. auch auf DNS-Sequenzen, siehe http://de.wikipedia.org/wiki/Sequenzalignment ). Eine andere Distanzfunktion wäre durch die Kölner Phonetik gegeben ( http://de.wikipedia.org/wiki/Kölner_Phonetik ). Dabei geht es darum, das gleich klingende Worte einen geringen Abstand haben (Mayer ~ Maier). Und eine weitere, die sinnvoll sein könnte, wäre eine, die nicht nur die Zeichen an sicht berücksichtigt, sondern auch, wie wahrscheinlich ein Unterschied nur durch einen Tippfehler entstanden ist. In diesem Sinne sind „renken“, „denken“ und „senken“ (aber eben auch „xenken“) zueinander ähnlicher als „denken“ und „lenken“.

Das andere ist (nicht unabhängig von der Distanzfunktion, aber unabhängig von deren genauer Definition) das, was man als Quantisierung, Klassifikation oder ganz allgemein „Clustering“ bezeichnen könnte (auch wenn die Cluster keine scharfen Grenzen haben, und das deswegen eigentlich unpassend ist). Wenn jemand „denken“ schreibt, muss man davon ausgehen, dass er das meint. Vielleicht hat er sich vertippt und meinte „senken“. Wenn er „xenken“ schreibt, kann beides der Fall sein…

11

Ich xenke, du haxt recht…