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; }
SEO od společnosti Digital Pylon
Online casino s algoritmem
České casino online online slot-vegas.cz
Hrajte nejlepší hry jako je GoodGame Empire.
Zajímavé články: Jak najít práci snů? Zvolte kariéru v IT!, Češi mají rádi hrací automaty online, Jak funguje algoritmické obchodování Casino, Online výuka Algoritmus a online marketing mají svá pravidla, Automaty, Matematický vliv, Ratings, Jak fungují algoritmy hazardních her online: více znalostí, více peněz, SYPWAI - nástroj pro vědecký vývoj, Vynikají na globálním trhu: Nejlepší vývojáři softwaru pro online výherní automaty, Jak si vybrat nejlepší české online casino, Proč byste měli hrát online casino VPN revoluce, Kde najdeme algoritmy v každodenním životě?, Čeká vás pracovní pohovor mimo město? Podívejte se, jak dokonale zvládnout včasný příchod, 5 úžasných technologií ze světa hazardních her, Mirror and access to Mostbet, Svou kancelář můžete mít stále po ruce, Jaké výhody má digitalizovaná firma oproti off-line konkurenci?, Jaký systém vybrat pro snadné řízení výroby?, Nahradí umělá inteligence ajťáky?, Důvody, proč používat SnapTik ke stahování videí TikTok, Dokonalý den na pláži: Co si vzít s sebou, aby byl výlet zábavný a bezpečný?, Jak přežít dlouhý let?, Go pay GoodGame Empire, Blockchain, Rozhovor