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:

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:

  1. kitten → sitten (nahradit „s“ za „k“)
  2. sittEn → sedin (nahradit „i“ za „e“)
  3. 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:

  1. kitten → itten (smazat „k“ na 0)
  2. itten → sitten (vložte „s“ na 0)
  3. sittEn → sittn (smazat „e“ ve 4)
  4. sittn → sittin (vložte „i“ na 4)
  5. 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

Hlavní článek: Wagner – Fischerův 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é

Reference

  1. ^ A b C d E F G Navarro, Gonzalo (1. března 2001). „Prohlídka s cílem přiblížit shodu řetězců“ (PDF). ACM Computing Surveys. 33 (1): 31–88. CiteSeerX  10.1.1.452.6317. doi:10.1145/375360.375365. Citováno 19. března 2015.
  2. ^ A b C d Daniel Jurafsky; James H. Martin. Zpracování řeči a jazyka. Pearson Education International. 107–111.
  3. ^ 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.
  4. ^ 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.
  5. ^ 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.
  6. ^ 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.
  7. ^ 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.
  8. ^ 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.
  9. ^ 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.
  10. ^ 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.
  11. ^ 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.
  12. ^ 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.
  13. ^ 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.
  14. ^ 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.
  15. ^ 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.