Algoritmus Wagner-Fischer je řetězcový algoritmus pro výpočet Levenshteinovy vzdálenosti mezi dvěma řetězci. Je založený na dynamickém programování.

  1. €n€ = délka řetězce €s€
  2. €m€ = délka řetězce €t€
  3. Vytvoř matici s €m+1€ řádky a €n+1€ sloupci.
  4. Do prvního řádku matice vlož posloupnost 0 až €n+1€.
  5. Do prvního sloupce matice vlož posloupnost 0 až €m+1€.
  6. Pro každý znak řetězce €s€ (€i \in \langle1,n\rangle€):
    1. Pro každý znak řetězce €t€ (€j \in \langle1,m\rangle€):
      1. Pokud jsou znaky na těchto pozicích shodné, pak €cost = 0€, jinak €cost = 1€.
        1. Do matice na pozici €[i,j]€ vlož nejmenší z těchto hodnot:
          1. Hodnotu políčka o jednu pozici výše + 1.
          2. Hodnotu políčka o jednu pozici vlevo + 1.
          3. Hodnotu políčka diagonály (vlevo nahoře) + €cost€.
  7. Výsledek je v matici na pozici €(n,m)€.

Levenshteinova vzdálenost

Vladimir Levenshtein
Vladimir Levenshtein

Levenshteinova vzdálenost (Vladimir Levenshtein, publikováno v roce 1965) mezi dvěma řetězci €s, t€ vyjadřuje míru jejich odlišnosti. Čím je levenshteinova vzdálenost větší, tím jsou řetězce odlišnější.

Tato vzdálenost je definovaná jako nejmenší počet operací, které je nutné provést s řetězcem €s€, abychom dostali řetězec €t€. Povolené operace jsou vložení znaku, odebrání znaku a nahrazení znaku. Levenstheinova vzdálenost je symetrická pouze v případě, že všechny tyto operace mají stejnou váhu.

Existují i varianty, které přikládají odlišné váhy různým operacím nebo kombinacím znaků při nahrazení. Tímto způsobem je možné lépe pracovat například s překlepy na klávesnici: nahrazení znaků P a O dáme menší váhu, než nahrazení znaků P a X a tím pádem se vzájemná vzdálenost takových slov sníží.

Levenstheinova vzdálenost se využívá například při implementaci kontroly pravopisu, analýze DNA, detekce plagiarismu nebo "fuzzy" vyhledávání podobných slov (např. s překlepy).

Příklad: DOG → BUGGY

Levenshteinova vzdálenost mezi slovy DOG a BUGGY je 4. Můžeme například nahradit DB, nahradit OU, ponechat G a přidat GY. To jsou dva znaky nahrazené a dva znaky přidané, výsledný počet operací je tedy 4.

BUGGY
012345
D112345
O222345
G33323=4

Příklad: NANNY → MAN

Levenshteinova vzdálenost mezi slovy NANNY a MAN je 3. Můžeme například nahradit NM, ponechat AN a smazat NY. To je jeden znak nahrazený a dva smazané, výsledný počet operací je tedy 3.

MAN
0123
N1122
A2212
N3321
N4432
Y554=3

Implementace

Pro snadnější pochopení je lepší začít původní verzí algoritmu s maticí.

package levenshtein;

public class LevenshteinWagnerFischer {
    /**
     * Calculates the Levenshtein distance of two strings.
     * Uses a Wagner-Fischer algorithm.
     * @param s first string
     * @param t second string
     * @return Levenshtein distance
     * @see https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm
     */
    public static int distanceWagnerFischer(final char[] s, final char[] t) {
        if (s.length == 0) {
            // edge case: S is empty
            return t.length;
        } else if (t.length == 0) {
            // edge case: T is empty
            return s.length;
        }

        final int[][] d = new int[s.length + 1][t.length + 1];

        for (int i = 0; i <= s.length; i++) {
            // reset first row
            d[i][0] = i;
        }

        for (int i = 0; i <= t.length; i++) {
            // reset first column
            d[0][i] = i;
        }

        for (int it = 1; it <= t.length; it++) {
            for (int is = 1; is <= s.length; is++) {
                // up = deletion
                final int costDeletion = d[is - 1][it] + 1;
                // left = insertion
                final int costInsertion = d[is][it - 1] + 1;
                // cost for replacing the character in case it is different
                final int costReplacement = (s[is - 1] == t[it - 1]) ? 0 : 1;
                // diagonal = substitution (if necessary)
                final int costSubstitution = d[is - 1][it - 1] + costReplacement;

                d[is][it] = min(costDeletion, costInsertion, costSubstitution);
            }
        }

        return d[s.length][t.length];
    }

    private static int min(final int a, final int b, final int c) {
        return Math.min(a, Math.min(b, c));
    }
}

Zdrojový kód Pokrytí testy

Protože jsou vždy k výpočtu potřeba jen dva poslední řádky matice, není nutné ukládat celou matici a ušetřit nějakou pameť:

package levenshtein;

public class LevenshteinWagnerFischerOptimized {
    /**
     * Calculates the Levenshtein distance of two strings.
     * Uses an optimized Wagner-Fischer algorithm.
     * @param s first string
     * @param t second string
     * @return Levenshtein distance
     * @see https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm
     */
    public static int distanceWagnerFischerOptimized(final char[] s, final char[] t) {
        if (t.length > s.length) {
            // to save memory, we want the shorter string to be the second parameter
            // (as long as the distance is symmetrical, we do not care about the order)
            return distanceWagnerFischerOptimized(t, s);
        }

        int[] previousRow = new int[t.length + 1];
        int[] currentRow = new int[t.length + 1];

        for (int i = 0; i < previousRow.length; i++) {
            // 0, 1, 2, 3, 4, 5...
            previousRow[i] = i;
        }

        for (int is = 1; is <= s.length; is++) {
            currentRow[0] = is;

            for (int it = 1; it <= t.length; it++) {
                // up = deletion
                final int costDeletion = previousRow[it] + 1;
                // left = insertion
                final int costInsertion = currentRow[it - 1] + 1;
                // cost for replacing the character in case it is different
                final int costReplacement = (s[is - 1] == t[it - 1]) ? 0 : 1;
                // diagonal = substitution (if necessary)
                final int costSubstitution = previousRow[it - 1] + costReplacement;

                currentRow[it] = min(costDeletion, costInsertion, costSubstitution);
            }

            // swap arrays (currentRow will be re-used and overwritten)
            final int[] temp = previousRow;
            previousRow = currentRow;
            currentRow = temp;
        }

        return previousRow[t.length];
    }

    private static int min(final int a, final int b, final int c) {
        return Math.min(a, Math.min(b, c));
    }
}

Zdrojový kód Pokrytí testy

Reference