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
01./**02. * Vrati seznam vsech vyskytu daneho vzoru (posledni index v textu, 03. * tzn. bez presahu) v danem textu v Levenshteinove vzdalenosti04. * maximalne maxDistance05. * @param text text06. * @param pattern vzor07. * @param maxDistance maximalni vzdalenost (vcetne)08. * @return seznam vsech vyskytu09. */10.public static List<Integer> levenshteinDistance(String text, String pattern, int maxDistance){11. List<Integer> l = new ArrayList<Integer>();12. int[] first = new int[pattern.length()];13. int[] second = new int[pattern.length()];14. 15. for(int i = 0; i < first.length; i++){ //inicializace prvniho sloupce16. first[i] = i + 1;17. }18. 19. for(int i = 0; i < text.length(); i++){ //vyplnovani tabulky20. for(int j = 0; j < second.length; j++){21. if(pattern.charAt(j) == text.charAt(i)){ //pismena souhlasi22. if(j != 0){23. second[j] = first[j - 1];24. } else {25. second[j] = 0;26. }27. }else{28. //vertikalni predchozi29. int prevVert = 0;30. if(j != 0) prevVert = second[j-1];31. 32. //horizontalni predchozi33. int prevHor = j;34. if(i != 0) prevHor = first[j];35. 36. //diagonalni predchozi37. int prevDiag = 0;38. if(i != 0 || j != 0){39. if(i != 0 && j != 0){40. prevDiag = first[j - 1];41. }else if(i != 0){42. prevDiag = 0;43. } else if(j != 0) { // j != 044. prevDiag = first[j - 1];45. } else assert true; //tohle nemuze nastat46. } else {47. prevDiag = 0;48. }49. 50. second[j] = 1 + Math.min(prevVert, Math.min(prevHor, prevDiag));51. 52. }53. }54. if(second[pattern.length() - 1] <= maxDistance) l.add(i);55. 56. //swap columns57. int[] tmp = first;58. first = second;59. second = tmp;60. }61. 62. return l;63.}