Wagner – Fischerův algoritmus - Wagner–Fischer algorithm

v počítačová věda, Wagner – Fischerův algoritmus je dynamické programování algoritmus, který počítá upravit vzdálenost mezi dvěma řetězci znaků.

Dějiny

Algoritmus Wagner – Fischer má historii vícenásobný vynález. Navarro uvádí jeho následující vynálezce s datem vydání a potvrzuje, že seznam není úplný:^[1]:43

• Vintsyuk, 1968
• Needleman a Wunsch, 1970
• Sankoff, 1972
• Prodejci, 1974
• Wagner a Fischer, 1974
• Lowrance a Wagner, 1975

Výpočet vzdálenosti

Algoritmus Wagner – Fischer vypočítá vzdálenost úprav na základě pozorování, že pokud si rezervujeme a matice držet editační vzdálenosti mezi všemi předpony prvního řetězce a všech předpon druhého, pak můžeme vypočítat hodnoty v matici podle povodňová výplň matici, a tak najít vzdálenost mezi dvěma úplnými řetězci jako poslední vypočítanou hodnotu.

Jednoduchá implementace, as pseudo kód pro funkci LevenshteinDistance to trvá dva řetězce, s délky m, a t délky na vrátí Levenshteinova vzdálenost mezi nimi, vypadá následovně. Všimněte si, že vstupní řetězce jsou jednoindexované, zatímco matice d je bez indexu, a [i..k] je uzavřený rozsah.

funkce LevenshteinDistance(char s[1..m], char t[1..n]):  // pro všechna i a j, d [i, j] bude držet Levenshteinovu vzdálenost mezi nimi  // první i znaky s a první j znaků t  // všimněte si, že d má (m + 1) * (n + 1) hodnoty  prohlásit int d[0..m, 0..n]   soubor každý živel v d na nula   // zdrojové předpony lze převést na prázdný řetězec pomocí  // vypuštění všech znaků  pro i z 1 na m:      d[i, 0] := i   // cílové předpony lze dosáhnout z prázdné předpony zdroje  // vložením každého znaku  pro j z 1 na n:      d[0, j] := j   pro j z 1 na n:      pro i z 1 na m:          -li s[i] = t[j]:            substitutionCost := 0          jiný:            substitutionCost := 1          d[i, j] := minimální(d[i-1, j] + 1,                   // smazání                             d[i, j-1] + 1,                   // vložení                             d[i-1, j-1] + substitutionCost)  // substituce   vrátit se d[m, n]

Dva příklady výsledné matice (přejetím nad podtržené číslo odhalíte operaci provedenou za účelem získání tohoto čísla):

The neměnný v celém algoritmu je to, že můžeme transformovat počáteční segment s [1..i] do t [1..j] s použitím minimálně d [i, j] operace. Na konci obsahuje prvek vpravo dole pole odpověď.

Důkaz správnosti

Jak již bylo zmíněno dříve, neměnný je, že můžeme transformovat počáteční segment s [1..i] do t [1..j] s použitím minimálně d [i, j] operace. Tento invariant platí od:

• Zpočátku platí na řádku a sloupci 0, protože s [1..i] lze transformovat do prázdného řetězce t [1..0] pouhým odhodením všech i postavy. Podobně se můžeme transformovat s [1..0] na t [1..j] jednoduchým přidáním všech j postavy.
• Li s [i] = t [j]a můžeme se transformovat s [1..i-1] na t [1..j-1] v k pak můžeme udělat totéž s [1..i] a nechte poslední postavu na pokoji, dávat k operace.
• Jinak je vzdálenost minimální ze tří možných způsobů provedení transformace:
  • Pokud se dokážeme transformovat s [1..i] na t [1..j-1] v k operace, pak můžeme jednoduše přidat t [j] poté získat t [1..j] v k + 1 operace (vložení).
  • Pokud se dokážeme transformovat s [1..i-1] na t [1..j] v k operace, pak můžeme odstranit s [i] a poté proveďte stejnou transformaci, celkem k + 1 operace (vypuštění).
  • Pokud se dokážeme transformovat s [1..i-1] na t [1..j-1] v k pak můžeme udělat totéž s [1..i]a vyměňte originál s [i] pro t [j] poté celkem k + 1 operace (substituce).
• Operace potřebné k transformaci s [1..n] do t [1..m] je samozřejmě počet potřebný k transformaci všech s do všech ta tak d [n, m] drží náš výsledek.

Tento důkaz nepotvrzuje, že číslo bylo vloženo d [i, j] je ve skutečnosti minimální; to je těžší ukázat, a zahrnuje argument rozporem ve kterém předpokládáme d [i, j] je menší než minimum ze tří a pomocí toho ukážeme, že jeden ze tří není minimální.

Možné úpravy

Možné úpravy tohoto algoritmu zahrnují:

• Můžeme přizpůsobit algoritmus tak, aby využíval méně prostoru, Ó (m) namísto Ó(mn), protože vyžaduje pouze to, aby byl předchozí řádek a aktuální řádek uložen současně.
• Můžeme ukládat počet vložení, odstranění a substitucí samostatně, nebo dokonce pozice, na kterých se vyskytují, což je vždy j.
• Můžeme normalizovat vzdálenost k intervalu [0,1].
• Pokud nás vzdálenost zajímá, pouze pokud je menší než prahová hodnota k, pak stačí vypočítat diagonální pruh šířky 2k + 1 v matici. Tímto způsobem lze spustit algoritmus Ó (kl) čas, kde l je délka nejkratšího řetězce.^[2]
• Můžeme dát různé sankční náklady na vložení, smazání a nahrazení. Můžeme také uvést pokutu, která závisí na tom, které znaky jsou vloženy, odstraněny nebo nahrazeny.
• Tento algoritmus paralelizuje špatně, kvůli velkému počtu datové závislosti. Nicméně, všechny náklady hodnoty lze vypočítat paralelně a algoritmus lze upravit tak, aby prováděl minimální funkce ve fázích k odstranění závislostí.
• Prozkoumáním úhlopříček místo řádků a použitím líné hodnocení, můžeme najít Levenshteinovu vzdálenost v Ó(m (1 + d)) čas (kde d je Levenshteinova vzdálenost), která je mnohem rychlejší než běžný algoritmus dynamického programování, pokud je vzdálenost malá.^[3]

Varianta prodejce pro vyhledávání řetězců

Inicializací první řady matice nulami získáme variantu Wagner – Fischerova algoritmu, kterou lze použít pro fuzzy vyhledávání řetězců řetězce v textu.^[1] Tato úprava dává koncovou pozici odpovídajících podřetězců textu. K určení počáteční pozice odpovídajících podřetězců lze počet vložení a odstranění uložit samostatně a použít k výpočtu počáteční polohy z koncové polohy.^[4]

Výsledný algoritmus není v žádném případě efektivní, ale byl v době jeho vydání (1980) jedním z prvních algoritmů, které prováděly přibližné vyhledávání.^[1]

Reference