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.
/* Berechnung */
I = 1;
WHILE (I <= LEN1)
DO
BEGIN
  CHAR_I = SUBSTRING(WORD1 FROM I FOR 1);
  J = 1;
  WHILE (J <= LEN2)
  DO
  BEGIN

    CHAR_J = SUBSTRING(WORD2 FROM J FOR 1);
    IF (CHAR_I = CHAR_J)
    THEN
      COST = 0;
    ELSE
      COST = 1;

    IF (
         (USE_DAMERAU = 1)
         AND
         (I > 1)
         AND
         (J > 1)
         AND
         (CHAR_I = SUBSTRING(WORD2 FROM J - 1 FOR 1))
         AND
         (SUBSTRING(WORD1 FROM I - 1 FOR 1) = CHAR_J)
       )
    THEN /* Damerau-Levenshtein-Distanz */
    BEGIN
      IF (COST = 1)
      THEN /* COST = 1 */
        UPDATE OR INSERT INTO "_temp_levenshtein"
        (I, J, D)
        VALUES
        (
          :I, :J,
          (
            SELECT MIN(D) + 1
              FROM "_temp_levenshtein"
             WHERE (I = :I - 1 AND J = :J    )
                OR (I = :I     AND J = :J - 1)
                OR (I = :I - 1 AND J = :J - 1)
                OR (I = :I - 2 AND J = :J - 2)
          )
        )
        MATCHING
        (I, J);
      ELSE /* COST = 0 */
        UPDATE OR INSERT INTO "_temp_levenshtein"
        (I, J, D)
        VALUES
        (
          :I, :J,
          (
            SELECT MIN(D) FROM
            (
              SELECT D + 1 AS D
                FROM "_temp_levenshtein"
               WHERE (I = :I - 1 AND J = :J    )
                  OR (I = :I     AND J = :J - 1)
              UNION ALL
              SELECT D
                FROM "_temp_levenshtein"
               WHERE (I = :I - 1 AND J = :J - 1)
                  OR (I = :I - 2 AND J = :J - 2)
            )
          )
        )
        MATCHING
        (I, J);
    END
    ELSE /* Levenshtein-Distanz */
    BEGIN
      IF (COST = 1)
      THEN /* COST = 1 */
        UPDATE OR INSERT INTO "_temp_levenshtein"
        (I, J, D)
        VALUES
        (
          :I, :J,
          (
            SELECT MIN(D) + 1
              FROM "_temp_levenshtein"
             WHERE (I = :I - 1 AND J = :J    )
                OR (I = :I     AND J = :J - 1)
                OR (I = :I - 1 AND J = :J - 1)
          )
        )
        MATCHING
        (I, J);
      ELSE /* COST = 0 */
        UPDATE OR INSERT INTO "_temp_levenshtein"
        (I, J, D)
        VALUES
        (
          :I, :J,
          (
            SELECT MIN(D) FROM
            (
              SELECT D + 1 AS D
                FROM "_temp_levenshtein"
               WHERE (I = :I - 1 AND J = :J    )
                  OR (I = :I     AND J = :J - 1)
              UNION ALL
              SELECT D
                FROM "_temp_levenshtein"
               WHERE (I = :I - 1 AND J = :J - 1)
            )
          )
        )
        MATCHING
        (I, J);
    END
    /* nächste Runde */
    J = J + 1;
  END
  /* nächste Runde */
  I = I + 1;
END

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;