Firebird: Levenshtein-Distanz

1. Einleitung

Schema der Levenshtein-Distanz BerechnungDie Levenshtein-Distanz wurde 1965 von Wladimir Lewenstein eingeführt. Damit ist es möglich die Anzahl der Unterschiede zwischen zwei Zeichenketten durch Zählen der Schritte ersetzen, einfügen und löschen einzelner Zeichen festzustellen. Die Berechnung des Algorithmus ist in der Wikipedie und an anderen Stellen, z.B. levenshtein.de, umfangreich beschrieben, so daß hier nicht weiter darauf eingegangen werden muß.

Matrix

Zum Speichern der einzelnen Berechnungsschritte wird eine Matrix bzw. ein Array gebraucht. Obwohl Firebird (und Interbase) Felder als Array anlegen können, kann das mit PSQL nicht genutzt werden. Auf diese Arrays wird ausschließlich über die API und nicht per SQL zugegriffen, was nur über ein Client-Programm möglich ist.
Hier wird die Matrix als temporäre Tabelle "_temp_levenshtein" angelegt. In der Tabelle stehen I und J für die Position in der Matrix und D für das Ergebnis des aktuellen Berechnungsschrittes. Der Primärschlässel dient einerseits dazu, doppelte Einträge zu vermeiden und andererseits dazu, schnelleren Zugriff auf die Daten zu haben.
CREATE GLOBAL TEMPORARY TABLE "_temp_levenshtein" (
    I  "dom_INT32" NOT NULL,
    J  "dom_INT32" NOT NULL,
    D  "dom_INT32"
) ON COMMIT PRESERVE ROWS;

ALTER TABLE "_temp_levenshtein" ADD CONSTRAINT "PK_temp_levenshtein" PRIMARY KEY (I, J);

Initialisierung der Matrix

Zur Initialisierung der Matrix wird die erste Zeile und die erste Spalte jeweils mit den Indizes eines der zu vergleichenden Zeichenketten vorbelegt. Alle anderen Zellen werden durch die Berechnung jeweils beschrieben, bevor sie zum erstem Mal gelesen werde. Dadurch spart man einige Schreiboperationen auf die temporäre Tabelle.
Aus dem gleichen Grund wurde die temporäre Tabelle auch mit der Option COMMIT PRESERVE ROWS angelegt. Damit steigt die Wahrscheinlichkeit, daß bei Schreibzugriffen der Datensatz bereits im Speicher ist und auch der Primärschlüssel muß seltener aktualisiert werden. Mit dem SQL- Statement UPDATE OR INSERT INTO wird dann der Datensatz erzeugt bzw. aktualisiert.

Indexweiter

Index