Edytuj odległość — Edit distance

W lingwistyki komputerowej i informatyki , edycja odległość jest sposobem ilościowym, jak odmienne dwa ciągi znaków (np słowa) są ze sobą licząc minimalną liczbę operacji potrzebnych do przekształcenia jeden ciąg na drugą. Edytowanie odległości znajduje zastosowanie w przetwarzaniu języka naturalnego , gdzie automatyczna korekta pisowni może określić potencjalne poprawki dla błędnie napisanego słowa, wybierając słowa ze słownika, które mają małą odległość od danego słowa. W bioinformatyce można go wykorzystać do ilościowego określenia podobieństwa sekwencji DNA , które można postrzegać jako ciągi liter A, C, G i T.

Różne definicje odległości edycji wykorzystują różne zestawy operacji na ciągach. Operacje Levenshteina na odległość to usuwanie, wstawianie lub zastępowanie znaku w ciągu. Jako najpopularniejsza metryka, termin odległość Levenshteina jest często używany zamiennie z określeniem odległości edycji .

Rodzaje odległości edycji

Różne typy odległości edycji umożliwiają różne zestawy operacji na ciągach. Na przykład:

Odległość Levenshteina pozwala delecję, insercję i zastąpienia.
Odległość najdłuższej wspólnej podsekwencji (LCS) umożliwia tylko wstawianie i usuwanie, a nie podstawienie.
Odległość Hamminga pozwala jedynie podstawienie, a więc ma ona zastosowanie tylko do ciągów o tej samej długości.
Odległość Damerau-Levenshteina umożliwia wstawianie, usuwanie, podstawianie i transpozycję dwóch sąsiednich znaków.
Odległość Jaro pozwala jedynie transpozycję .

Niektóre odległości edycji są zdefiniowane jako parametryzowalne metryki obliczane za pomocą określonego zestawu dozwolonych operacji edycji, a każdej operacji przypisywany jest koszt (prawdopodobnie nieskończony). Jest to dalej uogólniane przez algorytmy dopasowywania sekwencji DNA , takie jak algorytm Smitha-Watermana , które sprawiają, że koszt operacji zależy od miejsca jej zastosowania.

Formalna definicja i właściwości

Biorąc pod uwagę dwa łańcuchy $a$ i $b$ w alfabecie $Σ$ (np. zbiór znaków ASCII , zbiór bajtów [0..255] itd.), odległość edycji d( $a$ , $b$ ) jest serią edycji o minimalnej wadze operacje, które przekształcają $a$ w $b$ . Jednym z najprostszych zestawów operacji edycyjnych jest ten zdefiniowany przez Levenshteina w 1966 roku:

Wstawienie pojedynczego symbolu. Jeśli

a

=

u

v

, to wstawienie symbolu

x

daje

u

x

v

. Można to również oznaczyć jako ε→

x

, używając ε do oznaczenia pustego łańcucha.

Usunięcie pojedynczego symbolu zmienia

u

x

v

na

u

v

(

x

→ε).

Zastąpienie pojedynczego symbolu

x

symbolem

y

≠

x

zmienia

u

x

v

na

u

y

v

(

x

→

y

).

W pierwotnej definicji Levenshteina każda z tych operacji ma koszt jednostkowy (z wyjątkiem tego, że samo podstawienie znaku ma zerowy koszt), więc odległość Levenshteina jest równa minimalnej liczbie operacji wymaganych do przekształcenia $a$ do $b$ . Bardziej ogólnie współpracownicy rozdzielczości niż negatywne funkcje wagowe $W$ _ins ( $X$ ), $w$ _del ( $X$ ) i $w$ _ramach ( $x$ , $y$ ) o operacji.

Zasugerowano dodatkowe prymitywne operacje. Odległość Damerau–Levenshteina liczy się jako pojedyncza edycja częstym błędem: transpozycja dwóch sąsiednich znaków, formalnie charakteryzująca się operacją zmieniającą $u$ $x$ $y$ $v$ na $u$ $y$ $x$ $v$ . W celu poprawienia wyników OCR wykorzystano operacje łączenia i dzielenia, które zamieniają pojedynczy znak na parę lub odwrotnie.

Inne warianty odległości edycji uzyskuje się poprzez ograniczenie zestawu operacji. Najdłuższa wspólna odległość podciągu (LCS) to odległość edycji z wstawianiem i usuwaniem jako jedynymi dwiema operacjami edycji, obie po koszcie jednostkowym. Podobnie, dopuszczając tylko zamiany (ponownie po koszcie jednostkowym), uzyskuje się odległość Hamminga ; musi to być ograniczone do ciągów o równej długości. Odległość Jaro–Winklera można uzyskać z odległości edycyjnej, w której dozwolone są tylko transpozycje.

Przykład

Odległość Levenshteina między „kotek” i „siedzenie” to 3. Minimalny edytować skrypt, który przekształca byłe do tej drugiej jest:

k itten → s itten (zamień "s" na "k")
sitt e n → sitt i n ( zamień "i" na "e")
sittin → sittin g (wkładka "g" na końcu)

Odległość LCS (tylko wstawienia i usunięcia) daje inną odległość i minimalny skrypt edycji:

k itten → itten (usuń „k” w 0)
itten → s itten (wstaw "s" na 0)
sitt e n → sittn (usuń "e" w 4)
sittn → sitt ja n (wstaw "i" w 4)
sittin → sittin g (wkładka "g" na 6)

za łączny koszt/odległość 5 operacji.

Nieruchomości

Edycja odległości z nieujemnym kosztem spełnia aksjomaty metryki , dając początek przestrzeni metrycznej ciągów, gdy spełnione są następujące warunki:

Każda operacja edycji ma dodatni koszt;
dla każdej operacji istnieje operacja odwrotna o równych kosztach.

Dzięki tym właściwościom aksjomaty metryczne są spełnione w następujący sposób:

d

(

a

,

b

) = 0 wtedy i tylko wtedy, gdy a=b, ponieważ każdy łańcuch może zostać w prosty sposób przekształcony w siebie za pomocą operacji dokładnie zerowych.

d

(

a

,

b

) > 0 gdy

a

≠

b

, ponieważ wymagałoby to co najmniej jednej operacji o niezerowym koszcie.

d

(

a

,

b

) =

d

(

b

,

a

) przez równość kosztu każdej operacji i jej odwrotność.

Nierówność trójkąta:

d

(

a

,

c

) ≤

d

(

a

,

b

) +

d

(

b

,

c

).

Odległość Levenshteina i odległość LCS z kosztem jednostkowym spełniają powyższe warunki, a zatem aksjomaty metryczne. W literaturze rozważano również warianty odległości edycji, które nie są właściwymi metrykami.

Inne przydatne właściwości odległości edycji kosztu jednostkowego obejmują:

Odległość LCS jest ograniczona powyżej sumą długości pary ciągów.
Odległość LCS to górna granica odległości Levenshteina.
W przypadku strun o tej samej długości odległość Hamminga jest górną granicą odległości Levenshteina.

Niezależnie od kosztu/wagi, następujące właściwości wszystkich odległości edycji:

Gdy $a$ i $b$ mają wspólny przedrostek, ten przedrostek nie ma wpływu na odległość. Formalnie, gdy $a$ = $uv$ i $b$ = $uw$ , to $d$ ( $a$ , $b$ ) = $d$ ( $v$ , $w$ ). Pozwala to przyspieszyć wiele obliczeń obejmujących edycję odległości i edycję skryptów, ponieważ popularne przedrostki i przyrostki można pomijać w czasie liniowym.

Obliczenie

Pierwszy algorytm obliczania minimalnej odległości edycji między parą ciągów został opublikowany przez Damerau w 1964 roku.

Wspólny algorytm

Używając oryginalnych operacji Levenshteina, (niesymetryczna) odległość edycji od do jest określona przez , zdefiniowana przez powtarzanie $a=a_{1}\ldots a_{m}$ $b=b_{1}\ldots b_{n}$ $d_{mn}$

{\ Displaystyle {\ zacząć {wyrównany} d_ {i0} i = \ suma _ {k = 1} ^ {i} w_ {\ operatorka {del}} (a_ {k}), & & \ quad {\ tekst {dla }}\;1\leq i\leq m\\d_{0j}&=\sum _{k=1}^{j}w_{\mathrm {ins} }(b_{k}),&&\quad { \text{for}}\;1\leq j\leq n\\d_{ij}&={\begin{cases}d_{i-1,j-1}&{\text{for}}\;a_ {i}=b_{j}\\\min {\begin{przypadki}d_{i-1,j}+w_{\mathrm {del} }(a_{i})\\d_{i,j-1 }+w_{\mathrm {ins} }(b_{j})\\d_{i-1,j-1}+w_{\mathrm {sub} }(a_{i},b_{j})\end {przypadki}}&{\text{dla}}\;a_{i}\neq b_{j}\end{przypadki}}&&\quad {\text{dla}}\;1\leq i\leq m, 1\leq j\leq n.\end{wyrównany}}}

Algorytm ten można uogólnić do obsługi transpozycji, dodając kolejny termin w minimalizacji klauzuli rekurencyjnej.

Prosty, rekurencyjny sposób oceny tej powtarzalności wymaga czasu wykładniczego . Dlatego jest zwykle obliczany przy użyciu dynamicznego algorytmu programowania , który jest powszechnie przypisywany Wagnerowi i Fischerowi , chociaż ma historię wielu wynalazków. Po zakończeniu algorytmu Wagnera-Fischera minimalną sekwencję operacji edycyjnych można odczytać jako ślad operacji stosowanych podczas algorytmu programowania dynamicznego, począwszy od . $d_{mn}$

Algorytm ten ma złożoność czasową Θ( $m$ $n$ ), gdzie $m$ i $n$ są długościami ciągów. Gdy konstruowana jest pełna tablica programowania dynamicznego, jej złożoność przestrzenna również wynosi Θ( $m$ $n$ ) ; można to poprawić do Θ(min( $m$ , $n$ )) przez obserwację, że w dowolnym momencie algorytm wymaga tylko dwóch wierszy (lub dwóch kolumn) w pamięci. Jednak ta optymalizacja uniemożliwia odczytanie minimalnej serii operacji edycyjnych. Rozwiązanie tego problemu w przestrzeni liniowej oferuje algorytm Hirschberga .

Ulepszone algorytmy

Udoskonalając opisany powyżej algorytm Wagnera-Fishera, Ukkonen opisuje kilka wariantów, z których jeden przyjmuje dwa ciągi znaków i maksymalną odległość edycji $s$ i zwraca min( $s$ , $d$ ) . Osiąga to tylko poprzez obliczanie i przechowywanie części tabeli programowania dynamicznego wokół jej przekątnej. Ten algorytm zajmuje czas O( $s$ ×min( $m$ , $n$ )) , gdzie $m$ i $n$ są długościami ciągów. Złożoność przestrzeni to O( $s$ ² ) lub O( $s$ ) , w zależności od tego, czy sekwencja edycyjna musi zostać odczytana.

Dalsze ulepszenia Landaua , Myersa i Schmidta [1] dają algorytm czasu O( $s$ ² + max( $m$ , $n$ )) .

Aplikacje

Dystans edycji znajduje zastosowanie w biologii obliczeniowej i przetwarzaniu języka naturalnego, np. korekta błędów ortograficznych lub błędów OCR oraz przybliżone dopasowanie ciągów , gdzie celem jest znalezienie dopasowań dla krótkich ciągów w wielu dłuższych tekstach, w sytuacjach, gdy niewielka liczba różnic należy się spodziewać.

Istnieją różne algorytmy, które rozwiązują problemy poza obliczaniem odległości między parą ciągów, aby rozwiązywać powiązane typy problemów.

Algorytm Hirschberga oblicza optymalne wyrównanie dwóch ciągów, gdzie optymalność jest definiowana jako minimalizacja odległości edycji.
Przybliżone dopasowanie ciągów można sformułować na podstawie odległości edycji. Algorytm Ukkonena z 1985 roku bierze łańcuch $p$ , zwany wzorcem, oraz stałą $k$ ; następnie buduje deterministyczny automat skończony, który znajduje w dowolnym ciągu $s$ , podłańcuch, którego odległość edycji od $p$ wynosi co najwyżej $k$ (por. algorytm Aho-Corasick , który podobnie konstruuje automat do wyszukiwania dowolnego z wielu wzorce, ale bez zezwalania na operacje edycji). Podobnym algorytmem przybliżonego dopasowywania ciągów jest algorytm bitap , również definiowany w kategoriach odległości edycji.
Automaty Levenshteina to automaty skończone, które rozpoznają zbiór ciągów znaków w ograniczonej odległości edycji od ciągu ustalonego odniesienia.

Odległość edycji języka

Uogólnienie odległości edycji między ciągami znaków to odległość między tekstem a językiem, zwykle językiem formalnym . Zamiast uwzględniać odległość edycji między jednym ciągiem a drugim, odległość edycji języka jest minimalną odległością edycji, którą można osiągnąć między ustalonym ciągiem a dowolnym ciągiem pobranym z zestawu ciągów. Bardziej formalnie, dla dowolnego języka L i łańcucha x nad alfabetem $Σ$ , odległość edycji języka d( L , x ) jest wyrażona wzorem , gdzie jest odległością edycji łańcucha. Gdy język L jest bezkontekstowy , istnieje algorytm dynamicznego programowania czasu sześciennego zaproponowany przez Aho i Petersona w 1972 r., który oblicza odległość edycji języka. W przypadku mniej wyrazistych rodzin gramatyk, takich jak gramatyki regularne , istnieją szybsze algorytmy obliczania odległości edycji. ${\ Displaystyle d (L, x) = \ min _ {y \ w L} d (x, y)}$ $d(x,y)$

Odległość edycji języka znalazła wiele różnych zastosowań, takich jak składanie RNA, korekcja błędów i rozwiązania problemu Optimum Stack Generation.

Languages

In other projects