ähnlichkeitssuche

[cheops]

hallo zusammen,

basierend auf einer 5er mysql möchte ich eine ähnlichkeitssuche bei einer zahlenkette realisieren

beispiel:

in der datenbank steht "0 1 2 3 4 5 6"

finden soll er aber auch z.b.: "0 0 2 3 4 5 6"

meine zeichenkette ist jeweils 128 zahlen lang, die zeichenkette mit der geringsten abweichung (optionaler schwellwert) soll gefunden werden.

einziger ansatz bisher: stored procedure für den levenshtein-algorithmus, befürchte aber, dass das bei tausenden von einträgen eher inperformant wird :-(

hat jemand eine andere idee/lösung?

danke & gruß
cheops

[Texter mit x]

in der datenbank steht "0 1 2 3 4 5 6"

finden soll er aber auch z.b.: "0 0 2 3 4 5 6"

die zeichenkette mit der geringsten abweichung

Was soll das heißen, was ist ähnlicher als was? Anzahl der Abweichungen bei den Ziffern?

levenshtein-algorithmus

Das ist was anderes, aber wenn Du das wirklich willst, dann kommst Du nicht drum rum.

Man könnte aber z.B. durch blockweise gebildete Checksummen eine Vorauswahl treffen um den Vergleichsaufwand zu reduzieren. Das hängt davon ab wie große Ähnlichkeiten zu erwarten sind und welche Konzentration an Unterschieden zu erwarten sind.

0123456789 -> Checksumme bilden über erste und zweite Hälfte

0111256789 -> nur eine Checksumme ist falsch bei drei Unterschieden

0023456779 -> zwei Checksummen sind falsch bei nur zwei Unterschieden