AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Levenshtein-Distanz

Ein Thema von Nicolai1234 · begonnen am 11. Dez 2005 · letzter Beitrag vom 15. Dez 2005
Antwort Antwort
Seite 2 von 4     12 34      
Chewie

Registriert seit: 10. Jun 2002
Ort: Deidesheim
2.886 Beiträge
 
Turbo Delphi für Win32
 
#11

Re: Levenshtein-Distanz

  Alt 11. Dez 2005, 18:05
Wenn es des Programm erlaubt, könnte man durch Einsatz eines Multiprozessor-Systems die Leistungsfähigkeit vervielfachen, wenn man schon nichts mehr am Algorithmus verbessern kann.
Martin Leim
Egal wie dumm man selbst ist, es gibt immer andere, die noch dümmer sind
  Mit Zitat antworten Zitat
Benutzerbild von stoxx
stoxx

Registriert seit: 13. Aug 2003
1.111 Beiträge
 
#12

Re: Levenshtein-Distanz

  Alt 11. Dez 2005, 20:43
Zitat:
Nun geht es darum, selbe Titel zu finden (3. Spalte (durch Tilde getrennt)).
Es handelt sich dabei um ca. 6000 Zeilen.

Augerufen wird die Funktion mit jedem der 6000 Titel, da er jeden Titel mit jedem wieder vergleicht.
Genau das ist das Problem, bei diesem "naiven" Algorithmus.
Der Weg wäre, dass Du Deine Textdatei aufbereitest.
Lösungen würde Dir wahrscheinlich die Bioinformatik liefern. Aber mit 16, könnte ich mir das arg schwierig für Dich vorstellen.
Suffix Trees sind Deine ersten Stichworte für google ...

vlg stoxx
Phantasie ist etwas, was sich manche Leute gar nicht vorstellen können.
  Mit Zitat antworten Zitat
Benutzerbild von glkgereon
glkgereon

Registriert seit: 16. Mär 2004
2.287 Beiträge
 
#13

Re: Levenshtein-Distanz

  Alt 11. Dez 2005, 21:09
Man müsste auch nicht jedes mit jedem vergleichen (6000 * 6000) sondern könnte bereits verglichene rausnehmen, und damit nur die Hälfte durchlaufen müssen (6000*3000).
und das macht schon mal eine ganze menge^^
»Unlösbare Probleme sind in der Regel schwierig...«
  Mit Zitat antworten Zitat
Nicolai1234

Registriert seit: 21. Feb 2004
1.008 Beiträge
 
Turbo Delphi für Win32
 
#14

Re: Levenshtein-Distanz

  Alt 11. Dez 2005, 21:13
Zitat von glkgereon:
Man müsste auch nicht jedes mit jedem vergleichen (6000 * 6000) sondern könnte bereits verglichene rausnehmen, und damit nur die Hälfte durchlaufen müssen (6000*3000).
und das macht schon mal eine ganze menge^^
Hehe, das mache ich sogar^^

Zitat:
Lösungen würde Dir wahrscheinlich die Bioinformatik liefern. Aber mit 16, könnte ich mir das arg schwierig für Dich vorstellen.
Suffix Trees sind Deine ersten Stichworte für google ...
MAch das mal nicht vom Alter abhängig. Ich wäre trotzdem über Hilfe dankbar...
  Mit Zitat antworten Zitat
Benutzerbild von glkgereon
glkgereon

Registriert seit: 16. Mär 2004
2.287 Beiträge
 
#15

Re: Levenshtein-Distanz

  Alt 11. Dez 2005, 21:18
Zitat von Nicolai1605:
Zitat von glkgereon:
Man müsste auch nicht jedes mit jedem vergleichen (6000 * 6000) sondern könnte bereits verglichene rausnehmen, und damit nur die Hälfte durchlaufen müssen (6000*3000).
und das macht schon mal eine ganze menge^^
Hehe, das mache ich sogar^^
Ja, ich hatte mich schon gewundert das du es nicht machst...hatte dich wohl mist-verstanden^^

kannst du denn nicht vorher schon was filtern?
zum beispiel könnte man eventuell ganz grob nach der länge gucken, da diese ja sehr unterschiedlich zu sein scheint...
»Unlösbare Probleme sind in der Regel schwierig...«
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#16

Re: Levenshtein-Distanz

  Alt 12. Dez 2005, 09:58
Der Hinweis von Stoxx ist schon richtig hat aber auch einen Hacken in deinem speziellen Fall.

Die Komplexität deiner Suche ist O(n^2) also ziemlich mies. Tries wiederum haben eine Komplexität vergleichbar mit binärer Suche von O(n*ln(n)) also schon viel viel besser.

Der Hacken an der Sache ist deine Levinstein Distanz, diese ist nämlich kontraher zu den auf exakter Suche basierenden Tries. Ich persönlich kenne keinen Trie der mit der Levinstein Distanz = also unscharferm Vergleich funktionieren würde. Tries sind auf exakte 1 zu 1 Vergleiche angewiesen.

Ein zweites Problem besteht darin das du deine DB aus der Textdatei in ein anderes Format bringen müsstest.

Es gibt aber noch andere Verfahren als die Levinstein Distanz. Essentiell ist es für dich wichtig einen dieser Algos auszuwählen die es ermöglichen offline deine 6000 Datensätze der DB vorrauszuberechnen und diese dann in einem Trie speichern zu können. Der Suchvergleich würde als erstes dein Suchwort ebenfalls, nun online, konvertieren und dann kannst du mit dem unscharfen Vergleich suchen.

Gruß Hagen
  Mit Zitat antworten Zitat
Robert Marquardt
(Gast)

n/a Beiträge
 
#17

Re: Levenshtein-Distanz

  Alt 12. Dez 2005, 10:19
Das mit der Laenge ist eine offensichtliche Optimierung.
Also nicht Prozentzahlen liefern, die sowieso ungenau sind, sondern eine Mindestaehnlichkeit mit in die Funktion geben.
Unterscheiden sich die Wortlaengen um mehr als diese Mindestaehnlichkeit, so kann man sich weitere Pruefungen sparen.
Das funktinoiert allerdings nur wenn das Kosteninkrement immer 1 ist.
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#18

Re: Levenshtein-Distanz

  Alt 12. Dez 2005, 10:30
Also fragen wir uns was macht die Levenshtein Distanz ?

Sie berechnet die Anzahl der nötigen Editierungen zwischen String A und B, also wieviele Editierungen sind nötig um vom String a zu b zu kommen. Das ist IDEAL für uns

Du hast eine DB mit 6000 Titeln und möchtest sehr sehr schnell ein Suchtitel mit diesen vergleichen. Zur Zeit vergleichst du also Suchtitel A mit 6000 B's.

Dazu erechnest du LevD(Suchttitel, 6000* DBTitel) korekt ?

Was wäre wenn du aber einen "Zwischenschritt" einbaust. Angenommen die Titel in der DB haben maximale Länge 60 Zeichen. Du erzeugst nun eine DB mit der Levenshtein-Distanz von dem 60 Zeichen Wort "AAAAAAAAAA.." zu den Titeln. Wir erzeuigen also X = LevD(DBTitel, "AAAAAAAAA...") und speichert diese Zahl in der DB. Die DB wird sortiert nach diesem Wert.

Bei der Suche vom Titel, zb. "Test" erzeugst du die Distanz mit Y = LevD("AAAAAAAAAAA", "Test"); und suchst in der DB per binärer Suche den Wert X - Y = 0.

Der Trick ist also LevD(A, B) = LevD(A, C) - LevD(B, C).
X = LevD(A, C) kann offline für jeden Titel A mit dem festen Wert C erfolgen. Die DB kann sortiert werden nach X.
Y = LevD(B, C) wird online zur Suche erzeugt und Y kann nun per schneller binärer Suche in der DB per Vergleich zu X gesucht werden.

Probier mal ob das so geht, ist nur so eine Idee von mir.

Gruß Hagen
  Mit Zitat antworten Zitat
Benutzerbild von glkgereon
glkgereon

Registriert seit: 16. Mär 2004
2.287 Beiträge
 
#19

Re: Levenshtein-Distanz

  Alt 12. Dez 2005, 14:58
hmm...
wenn ich das richtig verstanden habe hört sich das gut an.

Du willst also einen "Referenzwert" erstellen ("AAA...") und alle Werte mit diesem vergleichen, und diesen Wert zwischenspeichern.
Dann müsste man nur noch, wie bisher, die bereits berechneten Werte vergleichen, was um ein vielfaches schneller wäre.

war das deine idee?
»Unlösbare Probleme sind in der Regel schwierig...«
  Mit Zitat antworten Zitat
Benutzerbild von stoxx
stoxx

Registriert seit: 13. Aug 2003
1.111 Beiträge
 
#20

Re: Levenshtein-Distanz

  Alt 12. Dez 2005, 15:01
Zitat:
Der Trick ist also LevD(A, B) = LevD(A, C) - LevD(B, C).
Hallo Hagen, das kann aber nicht ganz stimmen.

a := 'AAAAAB';
b := 'AAAAAC';
c := 'AAAAAA';

LevD(A,B) = 1;
LevD(A,C) = 1;
LevD(B,C) = 1;

LevD(A,B) <> LevD(A, C) - LevD(B, C)

1 <> 1 - 1
1 <> 0

Suffix Tries sind wie Du schon richtig sagst, nur zur exakten Stringgsuche geeignet, ich bin auf dem Gebiet leider noch nicht so fit, ich weiß aber, dass die Bioinformatik auch Algorithmen zur unscharfen Suche benötigt und verwendet.
Phantasie ist etwas, was sich manche Leute gar nicht vorstellen können.
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 2 von 4     12 34      


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 00:44 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz