Levenshtein-Distanz

[Nicolai1234]

Danke erstml für die Tipps.
Gibt es eigentlich noch andere Algorithmen mit denen man diese Aufgabe erledigen könnte? Oder ist die Levenshtein-Distanz schon das "Optimum"?

[marabu]

Hallo Nicolai,

Zitat von Nicolai1605:

Gibt es eigentlich noch andere Algorithmen mit denen man diese Aufgabe erledigen könnte? Oder ist die Levenshtein-Distanz schon das "Optimum"?

die Levenshtein-Distanz (LevD) ist die Edit-Distanz-Metrik schlechthin. Die Frage ist nur, ob es das ist, was du brauchst. Um das zu entscheiden ist deine Problembeschreibung noch zu dürftig. Werden da Schreibfehler gesucht? Sind die Texte ein OCR-Produkt? Kurz, wie enstehen die Daten? LevD liefert dir Gleichheit durch Ähnlichkeit bei frei wählbarer Schranke. Welche Aktionen sollen dadurch begründet werden?

Text-Ähnlichkeit ist ein Forschungsgebiet der KI. Die Algorithmen werden von Computer-Linguisten zur Analyse von geschriebenen Sprachen verwendet.

Ein Link der jede Menge Stichwörter zum Weitersuchen bringen könnte: klick

Grüße vom marabu

[Nicolai1234]

Zitat von marabu:

Werden da Schreibfehler gesucht? Sind die Texte ein OCR-Produkt? Kurz, wie enstehen die Daten? LevD liefert dir Gleichheit durch Ähnlichkeit bei frei wählbarer Schranke. Welche Aktionen sollen dadurch begründet werden?

Die Daten werden von Menschen manuell eingegeben. In diesem Fall sind es die Autoren selber, die ihre Buchtitel etc. eingeben. Das Programm hat dann die Aufgabe doppelte Einträge zu finden, falls ein Autor sein Buch zweimal (in ähnlicher Schreibweise) eingegeben hat oder falls 2 Autoren den selben Titel eingeben. (es ist durchaus so, dass diese Menschen versuchen, das System bewusst zu betrügen. Klingt seltsam, ist aber wahr) Also kann man nicht auf das bessere Verhalten bei den Eingaben hoffen^^

[glkgereon]

Dann scheint diese Methode sinnvoll zu sein.

Müssen diese 12 Millionen mal denn "immer" d.h. regeläßig durchlaufen werden?

vielleicht wäre es eine Überlegung wert, es einfach so zu lassen, falls das nur einmal der Fall wäre, und danach immer nur einmal alle^^

[alzaimar]

Noch ein Tip, sogar ganz in der Nähe ...
http://www.delphipraxis.net/internal...ct.php?t=51913
Das sieht doch ganz gut aus...

[stoxx]

also ich hätte da noch eine Idee.
Ähnlichkeiten heißen ja in Deinem Fall, dass einzelne Wörter komplett gleich sind. Nur etwas anders dargestellt, einmal mit Leerzeichen einmal hinten, einmal vorne.
Deshalb folgender Vorschlag.

1. den Suchstring teilst Du in einzelne Wörter auf
2. diese Worter suchst Du einzeln hintereinander in der Textdatei, und zwar auf exaktes Vorkommen.
3. Du überprüfst nur die Zeilen auf die Levenstein Distanz, wo die Wörter vorkommen. ( ich würde mit dem Wort anfangen, dass die wenigsten Vorkommen liefert und nur bis zu einer bestimmten Anzahl)

der 2. Schritt klingt zunächst kompliziert, ist aber über diese Suffix Trees lösbar und schnell realisierbar.
(eine Suchanfrage bei google hängt ja auch nicht von der Größe des Internets ab)

[Phoenix]

Also für eine einmalige Bereinigung der Datenbank von doubletten ist das imho nicht so performance-Kritisch.

Wichtig wäre, bei der Eingabe eines neuen Titels diesen direkt nach der Eingabe gegen die bestehende Datenbank zu prüfen. Ist es eine doublette wird der Eintrag verweigert oder der Eintrag gleich intern als Doublette markiert und kann dann vor der nächsten komplett-Bereinigung einfacher entfernt werden. Vor allem muss in diesem Fall ja nur ein einzelner Eintrag gegen die DB verglichen werden und nicht gleich alle miteinander.

[Nicolai1234]

Zitat von Phoenix:

Also für eine einmalige Bereinigung der Datenbank von doubletten ist das imho nicht so performance-Kritisch.

Wichtig wäre, bei der Eingabe eines neuen Titels diesen direkt nach der Eingabe gegen die bestehende Datenbank zu prüfen. Ist es eine doublette wird der Eintrag verweigert oder der Eintrag gleich intern als Doublette markiert und kann dann vor der nächsten komplett-Bereinigung einfacher entfernt werden. Vor allem muss in diesem Fall ja nur ein einzelner Eintrag gegen die DB verglichen werden und nicht gleich alle miteinander.

Das ist leider aus diversen Gründen nicht möglich. Die Eingaben müssen alle auf einmal überprüft werden.

[stoxx]

Zitat von Nicolai1605:

Das ist leider aus diversen Gründen nicht möglich. Die Eingaben müssen alle auf einmal überprüft werden.

von meiner Idee hälst Du wohl nix ? durchdenke das nochmal !
Ich denke, so würde das richtig gut funktionieren.
Also nur die Zeilen zu prüfen, wo überhaupt die Wörter vorkommen.
Das Wort "Lärmwirkungsforschung" kommt vielleicht nur in einer einzigen Zeile vor, also brauchst Du den aktuell durchlaufenen Eintrag nur mit dieser einzigen Zeile überprüfen, ob sie ähnlich ist, nicht mit allen Zeilen.
Das war die Idee dahinter..

[Nicolai1234]

Aber was wäre, wenn sich jemand bei einem längeren Wort verschreibt. Dann sind auch 2 einzelne Wörter nicht mehr exakt gleich. Daher war ich ein wenig irritiert. Vielleicht habe ich das aber auch falsch verstanden...