(unscharfer) Vergleich zweier Listen

[DocBorn]

Hallo Leute,

ich habe im Moment ein algorithmisches Problem. Ich habe zwei Listen mit Album-Titeln und möchte herausfinden welche Titel in der zweiten Liste vorkommen, nicht aber in der ersten.

Zu allererst hab ich natürlich alle gleichen rausgeworfen und dann halt noch so kleine Tricks wie vorher "ersetze alle nicht-Buchstaben durch Leerzeichen, entferne doppelte Leerzeichen". Allerdings will das alles nicht so richtig gut werden.

Dann habe ich zum Vergleich die Levenshtein-Distanz genommen. Sie nimmt zwei String entgegen und gibt eine Integer zurück wie viele Bearbeitungsschritte nötig sind um den einen String in den andern zu überführen, dabei ist "Zeichen hinzufügen", "Zeichen entfernen" und "Zeichen durch ein anderes ersetzen" je ein Arbeitsschritt.

Wenn diese Distanz dann (Wortlänge div 10) unterschreitet behandle ich die Titel als gleich. Der Vorteil ist halt, dass ich dadurch mit Tippfehlern und sowas wie "(maxi)" am Ende des Album-Titels klar komme. Leider ist diese Vorgehensweise relativ inperformant, also so Ausführungszeiten von ner halben Minute oder so sind ja unangenehem.

Ich wollte jetzt einfach hier mal fragen ob jemand konstruktive Vorschläge hat, oder ob der ein oder andere sowas schonmal gemacht hat und evtl. Erfahrungen weitergeben kann.

Danke im Vorraus.

Lars

[shmia]

Dann scheint deine Levenshtein - Implementierung etwas unperformant zu sein.
Zeig mal den Code.
Meine Levenshtein-DLL braucht für 1 Mio Vergleiche ca 2.13 Sekunden.

Delphi-Quellcode:

var
   i, p : Integer;
   x : IStopWatch;
begin
   x := CreateStopWatch;
   x.Start;
   for i := 1 to 1000000 do
      p := LevenshteinDistance('delphipraxis', 'delphinpraxnix');

   ShowMessageFmt('%f', [x.Seconds]);
end;

[alzaimar]

Ich kenn den genauen Algorithmus nicht, aber versuchs doch mal mit zwei anderen Strings. Ich meine, wenn die eh fast identisch sind, was soll der Algorithmus denn noch ausrechnen?