Firebird: Levenshtein-Distanz

2. Berechnung der Levenshtein-Distanz

Bei der Berechnung kann mittels des übergebenen Flags USE_DAMERAU zwischen der klassischen Levenshtein-Distanz und der Damerau-Levenshtein-Distanz gewählt werden. Mit der Damerau-Levenshtein-Distanz werden Zeichenvertauschungen als eine Änderung gezählt und nicht als zwei Ersetzungen.
Lesezugriffe auf die Matrix werden als SELECT auf die temporäre Tabelle ausgeführt. Dabei wird der Minimalwert ganz SQL-Like mit der Agregatfunktion MIN ermittelt.
Schreibzugriffe werden wieder mit UPDATE OR INSERT INTO realisiert, damit die Zellen nur dann angelegt werden, wenn sie wirklich benutzt werden und vorhandene Zellen wiederverwendet werden.
Wenn COST=1 kann man sich das UNION ALL sparen, da hier jeder gefundene Minimalwert inkrementiert wird.

Ergebnis

Das Ergebnis steht dann an der höchsten Indexposition in der Matrix und kann durch ein einfaches SELECT auf diese Zelle bestimmt werden.
/* Ergebnis */
SELECT D
  FROM "_temp_levenshtein"
 WHERE I = :LEN1 AND J = :LEN2
  INTO :DISTANCE;