Levenshteinova vzdálenost

Levenshteinova vzdálenost (Levenshtein distance, editační vzdálenost) je vzdálenost dvou řetězců definovaná jako minimální počet operací vkládání, mazání a substituce takových, aby po jejich provedení byly zadané řetězce totožné. Levenshteinovu vzdálenost zavedl v roce 1965 Vladimir Levenshtein.

Vyhledávání podřetězců

Vyhledávání podřetězců v zadané Levenshteinově vzdálenosti funguje na principu dynamického programování, které je velmi podobné vyhledávání podřetězců v dané Hammingově vzdálenosti – jedná se o stavbu tabulky, která má stejný počet počet řádků jako má hledaný vzor písmen a počet sloupců odpovídá délce prohledávaného textu.

Pohyb v tabulce

Pohyb v tabulce odpovídá následujícím pravidlům.

Pokud jsou na průsečíku textů $(i,\\; j)$ totožné znaky, použijeme operaci identita, která odpovídá diagonálnímu pohybu v tabulce.

$hodnota(i,\\; j) = hodnota(i - 1,\\; j - 1)$

Pokud ovšem nejsou na průsečíku textů $(i,\\; j)$ totožné znaky, pak je zapotřebí provést editaci prohledávaného textu, což je jedna z následujících transformací.

Odstranění znaku prohledávaného textu, což odpovídá horizontálnímu pohybu v tabulce.

$hodnota(i,\\; j) = hodnota(i,\\; j - 1) + 1$

Vložení znaku do prohledávaného textu, což odpovídá vertikálnímu pohybu v tabulce.

$hodnota(i,\\; j) = hodnota(i - 1,\\; j) + 1$

Substituce znaku prohledávaného textu, což odpovídá diagonálnímu pohybu v tabulce.

$hodnota(i,\\; j) = hodnota(i - 1,\\; j - 1) + 1$

Aby byl celkový počet použitých operací minimální, tak použijeme v každém kroku algoritmu tu transformaci, která zajistí, aby byla vždy také aktuální $hodnota(i,\\; j)$ minimální.

Iniciální hodnoty

Nyní již zbývá pouze doplnit iniciální hodnoty. Nultý sloupec bude obsahovat hodnoty $0, \\; 1, 2 \\;, \\cdots, \\; n$ , což odpovídá vertikálnímu pohybu v tabulce (vkládání znaků před prohledávaný text). Nultý řádek bude obsahovat samé nuly, jelikož hledáme všechny výskyty daného podřetězce.

Příklad

Nalezněte všechny výskyty podřetězce "bbb" v řetězci "bbabababbbb" v Levenshteinově vzdálenosti maximálně 1.

		b	b	a	b	a	b	a	b	b	b	b
	0	0	0	0	0	0	0	0	0	0	0	0
b	1	0	0	1	0	1	0	1	0	0	0	0
b	2	1	0	1	1	1	1	1	1	0	0	0
b	3	2	1	1	1	2	1	2	1	1	0	0

Kód

Java

     /**
      * Vrati seznam vsech vyskytu daneho vzoru (posledni index v textu, 
      * tzn. bez presahu) v danem textu v Levenshteinove vzdalenosti
      * maximalne maxDistance
      * @param text text
      * @param pattern vzor
      * @param maxDistance maximalni vzdalenost (vcetne)
      * @return seznam vsech vyskytu
      */
     public static List<Integer> levenshteinDistance(String text, String pattern, int maxDistance){
         List<Integer> l = new ArrayList<Integer>();
         int[] first = new int[pattern.length()];
         int[] second = new int[pattern.length()];
 
         for(int i = 0; i < first.length; i++){ //inicializace prvniho sloupce
             first[i] = i + 1;
         }
 
         for(int i = 0; i < text.length(); i++){ //vyplnovani tabulky
             for(int j = 0; j < second.length; j++){
                 if(pattern.charAt(j) == text.charAt(i)){ //pismena souhlasi
                     if(j != 0){
                         second[j] = first[j - 1];
                     } else {
                         second[j] = 0;
                     }
                 }else{
                     //vertikalni predchozi
                     int prevVert = 0;
                     if(j != 0) prevVert = second[j-1];
 
                     //horizontalni predchozi
                     int prevHor = j;
                     if(i != 0) prevHor = first[j];
 
                     //diagonalni predchozi
                     int prevDiag = 0;
                     if(i != 0 || j != 0){
                         if(i != 0 && j != 0){
                             prevDiag = first[j - 1];
                         }else if(i != 0){
                             prevDiag = 0;
                         } else if(j != 0) { // j != 0
                             prevDiag = first[j - 1];
                         } else assert true; //tohle nemuze nastat
                     } else {
                         prevDiag = 0;
                     }
 
                     second[j] = 1 + Math.min(prevVert, Math.min(prevHor, prevDiag));
 
                 }
             }
             if(second[pattern.length() - 1] <= maxDistance) l.add(i);
 
             //swap columns
             int[] tmp = first;
             first = second;
             second = tmp;
         }
 
         return l;
     }

Vyhledávání podřetězců

Pohyb v tabulce

Iniciální hodnoty

Příklad

Kód

Doporučujeme