Ergebnis der Suchanfrage

• Forum: Sonstige Fragen zu Delphi

  Re: Levenshtein-Distanz

    Delphi
    by negaH, 12. Dez 2005
  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...
• Forum: Sonstige Fragen zu Delphi

  Re: Levenshtein-Distanz

    Delphi
    by negaH, 12. Dez 2005
  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....