Upravit vzdálenost - Edit distance - Wikipedia
v výpočetní lingvistika a počítačová věda, upravit vzdálenost je způsob, jak kvantifikovat, jak odlišné dva struny (např. slova) jsou k sobě navzájem počítáním minimálního počtu operací potřebných k transformaci jednoho řetězce na druhý. Upravit vzdálenosti, najít aplikace v zpracování přirozeného jazyka, kde automatické oprava pravopisu může určit opravy kandidáta na chybně napsané slovo výběrem slov ze slovníku, která mají malou vzdálenost od dotyčného slova. v bioinformatika, lze jej použít ke kvantifikaci podobnosti DNA sekvence, které lze zobrazit jako řetězce písmen A, C, G a T.
Různé definice editační vzdálenosti používají různé sady řetězcových operací. Levenshteinova vzdálenost operace jsou odebrání, vložení nebo nahrazení znaku v řetězci. Jako nejběžnější metrika, termín Levenshteinova vzdálenost se často používá zaměnitelně s upravit vzdálenost.[1]
Druhy editační vzdálenosti
Různé typy editační vzdálenosti umožňují různé sady řetězcových operací. Například:
- The Levenshteinova vzdálenost umožňuje mazání, vkládání a nahrazování.
- The Nejdelší společná posloupnost Vzdálenost (LCS) umožňuje pouze vkládání a mazání, nikoli substituci.
- The Hammingova vzdálenost umožňuje pouze substituci, proto se vztahuje pouze na řetězce stejné délky.
- The Vzdálenost Damerau – Levenshtein umožňuje vkládání, mazání, nahrazování a transpozice dvou sousedních znaků.
- The Jaro vzdálenost povoluje pouze transpozice.
Některé vzdálenosti úprav jsou definovány jako parametrizovatelná metrika vypočítaná pomocí konkrétní sady povolených operací úprav a každé operaci je přiřazena cena (možná nekonečná). To je dále generalizováno DNA zarovnání sekvence algoritmy jako např Smith – Watermanův algoritmus, díky nimž náklady na operaci závisí na tom, kde se použije.
Formální definice a vlastnosti
Vzhledem k tomu, dva řetězce A a b na abecedě Σ (např. sada ASCII znaky, sada bajtů [0..255] atd.), Vzdálenost pro úpravy d (A, b) je řada úprav s minimální hmotností, která se transformuje A do b. Jednou z nejjednodušších sad operací úprav je ta, kterou definoval Levenshtein v roce 1966:[2]
- Vložení jednoho symbolu. Li A = uproti, poté vložte symbol X vyrábí uXproti. To lze také označit ε →X, k označení prázdného řetězce použijte ε.
- Vymazání jednoho symbolu se změní uXproti na uproti (X→ ε).
- Střídání jednoho symbolu X pro symbol y ≠ X Změny uXproti na uyproti (X→y).
V Levenshteinově původní definici má každá z těchto operací jednotkové náklady (kromě toho, že nahrazení postavy samo o sobě má nulové náklady), takže vzdálenost Levenshtein je rovna minimální číslo operací potřebných k transformaci A na b. Obecnější definice spojuje funkce záporné váhy wins(X), wdel(X) a wsub(X, y) s operacemi.[2]
Byly navrženy další primitivní operace. Vzdálenost Damerau – Levenshtein počítá se jako jedna úprava běžné chyby: transpozice dvou sousedních znaků, formálně charakterizovaných operací, která se mění uXyproti do uyXproti.[3][4]Za úkol opravy OCR výstup, spojit a rozdělit byly použity operace, které nahrazují jeden znak do dvojice nebo naopak.[4]
Další varianty vzdálenosti úprav se získají omezením sady operací. Nejdelší společná subsekvence (LCS) vzdálenost je vzdálenost úpravy s vložením a odstraněním jako jediné dvě úpravy, obě za jednotkovou cenu.[1]:37 Podobně tím, že povolíte pouze substituce (opět za jednotkovou cenu), Hammingova vzdálenost je získán; toto musí být omezeno na řetězce stejné délky.[1]Vzdálenost Jaro – Winkler lze získat z editační vzdálenosti, kde jsou povoleny pouze transpozice.
Příklad
The Levenshteinova vzdálenost mezi „kotě“ a „sedící“ je 3. Minimální editační skript, který transformuje první na druhé, je:
- kitten → sitten (nahradit „s“ za „k“)
- sittEn → sedin (nahradit „i“ za „e“)
- sedět → sedětG (na konec vložte „g“)
Vzdálenost LCS (pouze vkládání a mazání) poskytuje jinou vzdálenost a minimální editační skript:
- kitten → itten (smazat „k“ na 0)
- itten → sitten (vložte „s“ na 0)
- sittEn → sittn (smazat „e“ ve 4)
- sittn → sittin (vložte „i“ na 4)
- sedět → sedětG (vložte „g“ na 6)
pro celkové náklady / vzdálenost 5 operací.
Vlastnosti
Vzdálenost úprav s nezápornými náklady splňuje axiomy a metrický, což vede k a metrický prostor řetězců, pokud jsou splněny následující podmínky:[1]:37
- Každá editační operace má kladné náklady;
- pro každou operaci existuje inverzní operace se stejnými náklady.
S těmito vlastnostmi jsou metrické axiomy splněny takto:
- d(A, b) = 0 právě a jen pokud a = b, protože každý řetězec lze triviálně transformovat na sebe pomocí přesně nulových operací.
- d(A, b)> 0 když A ≠ b, protože by to vyžadovalo alespoň jednu operaci za nenulové náklady.
- d(A, b) = d(b, A) rovností nákladů na každou operaci a její inverzní.
- Nerovnost trojúhelníku: d(A, C) ≤ d(A, b) + d(b, C).[5]
Levenshteinova vzdálenost a vzdálenost LCS s jednotkovými náklady splňují výše uvedené podmínky, a proto metrické axiomy. Varianty editační vzdálenosti, které nejsou správnými metrikami, byly rovněž uvažovány v literatuře.[1]
Mezi další užitečné vlastnosti úpravných jednotek jednotkových nákladů patří:
- Vzdálenost LCS je výše omezena součtem délek dvojice řetězců.[1]:37
- LCS vzdálenost je horní hranice Levenshteinovy vzdálenosti.
- U strun stejné délky je Hammingova vzdálenost horní hranicí Levenshteinovy vzdálenosti.[1]
Bez ohledu na cenu / váhu má tato vlastnost všechny vzdálenosti úprav:
- Když A a b sdílet společnou předponu, tato předpona nemá žádný vliv na vzdálenost. Formálně, kdy A = uv a b = uw, pak d(A, b) = d(proti, w).[4] To umožňuje zrychlit mnoho výpočtů zahrnujících vzdálenost úprav a úpravy skriptů, protože běžné předpony a přípony lze přeskočit v lineárním čase.
Výpočet
První algoritmus pro výpočet minimální editační vzdálenosti mezi dvojicí řetězců publikoval Damerau v roce 1964.[6]
Společný algoritmus
Použitím Levenshteinových původních operací je (nesymetrická) vzdálenost od úpravy na darováno , definovaný opakováním[2]
Tento algoritmus lze zobecnit na zpracování transpozic přidáním dalšího výrazu do minimalizace rekurzivní klauze.[3]
Přímočarý, rekurzivní způsob hodnocení tohoto opakování trvá exponenciální čas. Proto se obvykle počítá pomocí a dynamické programování algoritmus, kterému se běžně připisuje Wagner a Fischer,[7] i když má historii mnohonásobného vynálezu.[2][3]Po dokončení Wagner-Fischerova algoritmu lze minimální sekvenci editačních operací odečíst jako ústup od operací použitých během algoritmu dynamického programování od .
Tento algoritmus má a časová složitost z Θ (mn). Když je vytvořena plná dynamická programovací tabulka, její složitost prostoru je také Θ (mn); toto lze vylepšit na Θ (min (m,n)) pozorováním, že v každém okamžiku algoritmus vyžaduje pouze dva řádky (nebo dva sloupce) v paměti. Tato optimalizace však znemožňuje odečíst minimální sérii operací úprav.[3] Řešení tohoto problému v lineárním prostoru nabízí Hirschbergův algoritmus.[8]:634
Vylepšené algoritmy
Zdokonalení výše popsaného algoritmu Wagner – Fisher Ukkonen popisuje několik variant,[9] jeden z nich má dva řetězce a maximální vzdálenost pro úpravy sa vrátí se min (s, d). Dosahuje toho pouze výpočtem a ukládáním části dynamické programovací tabulky kolem její úhlopříčky. Tento algoritmus vyžaduje čas Ó(s× min (m,n)), kde m a n jsou délky řetězců. Složitost prostoru je Ó(s²) nebo Ó(s), v závislosti na tom, zda je třeba přečíst sekvenci úprav.[3]
Další vylepšení od Landau, Myers a Schmidt [1] dát Ó(s2 + max (m,n)) časový algoritmus.[10]
Aplikace
Upravit vzdálenost vyhledá aplikace v výpočetní biologie a zpracování přirozeného jazyka, např. - opravu pravopisných chyb nebo chyb OCR a - přibližná shoda řetězců, kde cílem je najít shody pro krátké řetězce v mnoha delších textech, v situacích, kdy lze očekávat malý počet rozdílů.
Existují různé algoritmy, které kromě výpočtu vzdálenosti mezi dvojicí řetězců řeší problémy a řeší související typy problémů.
- Hirschbergův algoritmus vypočítá optimální zarovnání dvou řetězců, kde je optimalita definována jako minimalizace editační vzdálenosti.
- Přibližná shoda řetězce lze formulovat z hlediska editační vzdálenosti. Ukkonenův algoritmus z roku 1985 vyžaduje řetězec str, nazvaný vzor, a konstanta k; pak staví a deterministický automat konečných stavů který najde v libovolném řetězci s, podřetězec, jehož editační vzdálenost k str je nanejvýš k[11] (srov Algoritmus Aho – Corasick, který podobně konstruuje automat pro hledání libovolného z mnoha vzorů, ale bez povolení editačních operací). Podobný algoritmus pro přibližnou shodu řetězců je bitapový algoritmus, definováno také z hlediska editační vzdálenosti.
- Levenshteinovy automaty jsou stroje s konečným stavem, které rozpoznávají sadu řetězců v ohraničené editační vzdálenosti pevného referenčního řetězce.[4]
Vzdálenost pro úpravu jazyka
Zevšeobecnění editační vzdálenosti mezi řetězci je jazyková editační vzdálenost mezi řetězcem a jazykem, obvykle a formální jazyk. Místo zohlednění vzdálenosti pro úpravy mezi jedním řetězcem a druhým je vzdálenost pro úpravy jazyka minimální vzdálenost pro úpravy, které lze dosáhnout mezi pevným řetězcem a žádný řetězec převzatý ze sady řetězců. Více formálně, pro jakýkoli jazyk L a řetězec X přes abecedu Σ, jazyk upravit vzdálenost d (L, X) darováno[12], kde je vzdálenost úpravy řetězce. Když jazyk L je kontext zdarma, existuje kubický časový dynamický programovací algoritmus navržený Aho a Petersonem v roce 1972, který počítá vzdálenost úpravy jazyka.[13] Pro méně výrazné rodiny gramatik, jako je běžné gramatiky, existují rychlejší algoritmy pro výpočet editační vzdálenosti.[14]
Vzdálenost pro úpravy jazyků našla mnoho různých aplikací, jako je skládání RNA, korekce chyb a řešení problému Optimum Stack Generation.[12][15]
Viz také
- Vzdálenost úpravy grafu
- Problém s korekcí řetězce na řetězec
- Řetězcová metrika
- Time Warp Upravit vzdálenost
Reference
- ^ A b C d Daniel Jurafsky; James H. Martin. Zpracování řeči a jazyka. Pearson Education International. 107–111.
- ^ A b C d E Esko Ukkonen (1983). Na přibližné shody řetězců. Základy teorie výpočtu. Springer. 487–495. doi:10.1007/3-540-12689-9_129.
- ^ A b C d Schulz, Klaus U .; Mihov, Stoyan (2002). "Rychlá korekce strun pomocí automatů Levenshtein". International Journal of Document Analysis and Recognition. 5 (1): 67–85. CiteSeerX 10.1.1.16.652. doi:10.1007 / s10032-002-0082-8.
- ^ Lei Chen; Raymond Ng (2004). O sňatku norem Lₚ a upravit vzdálenost (PDF). Proc. 30. mezinárodní konf. na velmi velkých databázích (VLDB). 30. doi:10.1016 / b978-012088469-8.50070-x.
- ^ Kukich, Karen (1992). „Techniky automatické opravy slov v textu“ (PDF). ACM Computing Surveys. 24 (4): 377–439. doi:10.1145/146370.146380. Archivovány od originál (PDF) dne 2016-09-27. Citováno 2017-11-09.
- ^ R. Wagner; M. Fischer (1974). Msgstr "Problém s opravou řetězce na řetězec". J. ACM. 21: 168–178. doi:10.1145/321796.321811. S2CID 13381535.
- ^ Skiena, Steven (2010). Příručka pro návrh algoritmu (2. vyd.). Springer Science + Business Media. Bibcode:2008adm..book ..... S. ISBN 978-1-849-96720-4.
- ^ Ukkonen, Esko (1985). "Algoritmy pro přibližnou shodu řetězců" (PDF). Informace a kontrola. 64 (1–3): 100–118. doi:10.1016 / S0019-9958 (85) 80046-2.
- ^ Landau; Myers; Schmidt (1998). Msgstr "Přírůstkové porovnání řetězců". SIAM Journal on Computing. 27 (2): 557–582. CiteSeerX 10.1.1.38.1766. doi:10.1137 / S0097539794264810.
- ^ Esko Ukkonen (1985). Msgstr "Nalezení přibližných vzorů v řetězcích". J. Algoritmy. 6: 132–137. doi:10.1016/0196-6774(85)90023-9.
- ^ A b Bringmann, Karl; Grandoni, Fabrizio; Saha, Barna; Williams, Virginia Vassilevska (2016). „Skutečně subkubické algoritmy pro jazykovou úpravu vzdálenosti a RNA-skládání pomocí produktu Fast Bounded-Difference Min-Plus“ (PDF). 57. výroční sympozium IEEE 2016 o základech informatiky (FOCS). 375–384. arXiv:1707.05095. doi:10.1109 / focs.2016.48. ISBN 978-1-5090-3933-3.
- ^ Aho, A .; Peterson, T. (01.12.1972). "Analyzátor opravy chyb minimální vzdálenosti pro bezkontextové jazyky". SIAM Journal on Computing. 1 (4): 305–312. doi:10.1137/0201022. ISSN 0097-5397.
- ^ Wagner, Robert A. (1974). "Oprava objednávky-n pro běžné jazyky". Komunikace ACM. 17 (5): 265–268. doi:10.1145/360980.360995. S2CID 11063282.
- ^ Saha, B. (01.10.2014). Dyckův problém úpravy vzdálenosti v téměř lineárním čase. 55. výroční sympozium IEEE 2014 o základech informatiky. str. 611–620. doi:10.1109 / FOCS.2014.71. ISBN 978-1-4799-6517-5. S2CID 14806359.