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ů totožné znaky, použijeme operaci identita, která odpovídá diagonálnímu pohybu v tabulce.
Pokud ovšem nejsou na průsečíku textů 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.
Vložení znaku do prohledávaného textu, což odpovídá vertikálnímu pohybu v tabulce.
Substituce znaku prohledávaného textu, což odpovídá diagonálnímu pohybu v tabulce.
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í minimální.
Iniciální hodnoty
Nyní již zbývá pouze doplnit iniciální hodnoty. Nultý sloupec bude obsahovat hodnoty , 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
/**
* 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;
}
