hallo leute,
ich habe eine knifflige frage, und setze ein preisgeld auf die lösung aus. 
also: für ein projekt benötige ich eine unscharfe string-suche, um z.b. tippfehler erkennen zu können. den "ähnlichkeitsgrad" zweier gegebener strings (z.b. als prozent-wert) kann man nun natürlich relativ einfach feststellen (siehe http://de.wikipedia.org/wiki/Levenshtein-Distanz).
so, nun soll in einer datenbank nach dem eingabestring unscharf gesucht werden. die "naive" möglichkeit ist natürlich einfach über alle strings den ähnlichkeitsgrad zum suchstring auszurechnen (also lineare laufzeit, was angesichts des aufwändigen vergleichs und der möglicherweise sehr großen datenmengen schon ziemlich viel ist).
die preisfrage also: kennt jemand eine möglichkeit eine unscharfe stringsuche auf einen datenbestand in logarithmischer laufzeit durchzuführen (analog zur binärsuche für z.b. die "scharfe" string-suche)??
ps: die möglichkeit in der datenbank einen index auf den soundex-wert der strings (siehe http://de.wikipedia.org/wiki/Soundex) zu definieren ist mir bekannt - aber soundex ist kein wirklich zuverlässiger algorithmus, der außerdem nur für englischen text (einigermaßen) funktioniert.
also, hat da schon jemand mal was mit unscharfer string-suche programmiert? irgendwelche ideen, anybody?
mfg