Odległość Levenshteina

Odległość Levenshteina jest szeroko wykorzystywana w informatyce, szczególnie w korektorach pisowni, wyszukiwarkach, systemach rozpoznawania tekstu oraz algorytmach analizy danych. Pozwala ocenić stopień podobieństwa między dwoma słowami lub sekwencjami znaków.

Jej działanie opiera się na wyznaczeniu najmniejszej liczby modyfikacji potrzebnych do przejścia z jednego ciągu do drugiego. Im mniejsza wartość odległości, tym bardziej podobne są oba ciągi.

W przeciwieństwie do odległości Hamminga, odległość Levenshteina można stosować również do ciągów o różnej długości.

Przykład obliczania odległości Levenshteina

Rozważmy dwa ciągi znaków:

$$ s = "kitten" $$

$$ t = "sitting" $$

Chcemy określić, ile minimalnie operacji potrzeba, aby przekształcić słowo „kitten” w „sitting”.

1. Zamiana znaku
   Zamieniamy literę \( k \) na \( s \): $$ "kitten" \rightarrow "sitten" $$
2. Zamiana znaku
   Zamieniamy literę \( e \) na \( i \): $$ "sitten" \rightarrow "sittin" $$
3. Wstawienie znaku
   Dodajemy literę \( g \) na końcu: $$ "sittin" \rightarrow "sitting" $$

Do wykonania transformacji potrzebne są więc trzy operacje. Oznacza to, że odległość Levenshteina między słowami „kitten” i „sitting” wynosi:

$$ d(s,t)=3 $$

Macierz odległości Levenshteina

Aby obliczyć odległość Levenshteina w sposób algorytmiczny, buduje się macierz o wymiarach \( (m+1) \times (n+1) \), gdzie:

• \( m \) oznacza długość pierwszego ciągu;
• \( n \) oznacza długość drugiego ciągu.

W analizowanym przykładzie:

$$ m = 6 \qquad n = 7 $$

Dodatkowy wiersz i dodatkowa kolumna odpowiadają operacjom wykonywanym na pustym ciągu znaków.

	""	s	i	t	t	i	n	g
""	0	1	2	3	4	5	6	7
k	1
i	2
t	3
t	4
e	5
n	6

Komórka \( (0,j) \) określa koszt przekształcenia pustego ciągu w prefiks słowa „sitting” o długości \( j \). Koszt ten rośnie liniowo od 0 do 7.

Analogicznie komórka \( (i,0) \) reprezentuje koszt przekształcenia prefiksu słowa „kitten” o długości \( i \) w pusty ciąg. W tym przypadku koszt wzrasta od 0 do 6.

Każda kolejna komórka macierzy jest wyznaczana na podstawie trzech możliwych operacji:

1. usunięcia znaku, czyli przejścia z komórki znajdującej się powyżej;
2. wstawienia znaku, czyli przejścia z komórki po lewej stronie;
3. zamiany znaku, czyli przejścia z komórki diagonalnej.

Jeśli porównywane znaki są identyczne, koszt zamiany wynosi 0. W przeciwnym razie dodawany jest koszt równy 1.

Wypełniając macierz krok po kroku, można wyznaczyć minimalny koszt transformacji całego ciągu. Wartość znajdująca się w prawym dolnym rogu macierzy odpowiada odległości Levenshteina między analizowanymi słowami.

	""	s	i	t	t	i	n	g
""	0	1	2	3	4	5	6	7
k	1	1	2	3	4	5	6	7
i	2	2	1	2	3	4	5	6
t	3	3	2	1	2	3	4	5
t	4	4	3	2	1	2	3	4
e	5	5	4	3	2	2	3	4
n	6	6	5	4	3	3	2	3

Na przykład przekształcenie pustego ciągu w „s", „si", „sit" itd. wymaga dodania jednej kolejnej operacji dla każdego nowego znaku.

Podobnie usuwanie znaków z ciągów „k", „ki", „kit" itd. aż do uzyskania pustego ciągu powoduje wzrost kosztu o jedną jednostkę przy każdej operacji usunięcia.

• Komórka (1,1) określa koszt zamiany „k" na „s". Wynosi on 1, ponieważ potrzebna jest jedna substytucja znaku.
  
• Komórka (2,2) odpowiada kosztowi przekształcenia „ki" w „si". Koszt pozostaje równy 1, ponieważ drugi znak, \( i \), jest identyczny w obu ciągach.
• Komórka (3,3) przedstawia koszt przejścia od „kit" do „sit". Nadal wynosi on 1, gdyż trzeci znak, \( t \), nie ulega zmianie.
• Komórka (4,4) określa koszt przekształcenia „kitt" w „sitt". Również tutaj koszt wynosi 1, ponieważ czwarty znak, \( t \), pozostaje taki sam.
• Komórka (5,5) przyjmuje wartość 2, ponieważ przejście od „kitte" do „sitti" wymaga dodatkowej substytucji \( e \rightarrow i \).
  
• Komórka (6,6) wskazuje koszt przekształcenia „kitten" w „sittin". Koszt pozostaje równy 2, ponieważ ostatni znak, \( n \), jest identyczny.
• Komórka (6,7) przedstawia całkowity koszt równy 3 dla przekształcenia „kitten" w „sitting". Ostatnia operacja polega na dodaniu litery \( g \) na końcu ciągu.
  

W ten sposób dochodzimy do komórki końcowej, która zawiera całkowity skumulowany koszt transformacji.

Komórka znajdująca się w prawym dolnym rogu \( (6,7) \) wyznacza minimalny koszt przekształcenia słowa „kitten" w „sitting". Wartość ta wynosi 3.

Otrzymany wynik odpowiada wcześniej obliczonej odległości Levenshteina, czyli dwóm substytucjom i jednej operacji wstawienia.

Topologia indukowana przez odległość Levenshteina

Odległość Levenshteina indukuje strukturę przestrzeni metrycznej na zbiorze ciągów znaków, podobnie jak odległość Hamminga. Wynika to z faktu, że spełnia wszystkie podstawowe aksjomaty definiujące metrykę.

1. Nieujemność: Odległość Levenshteina między dwoma ciągami \( x \) i \( y \) jest zawsze większa lub równa zeru, a \( D_L(x, y) = 0 \) wtedy i tylko wtedy, gdy \( x = y \). Oznacza to, że przekształcenie ciągu w niego samego nie wymaga żadnej operacji.
2. Symetria: Odległość Levenshteina jest symetryczna, czyli \( D_L(x, y) = D_L(y, x) \). Liczba operacji potrzebnych do przejścia od \( x \) do \( y \) jest taka sama jak liczba operacji potrzebnych do przejścia od \( y \) do \( x \), ponieważ dopuszczalne operacje są odwracalne.
3. Nierówność trójkąta: Zachodzi nierówność \( D_L(x, z) \leq D_L(x, y) + D_L(y, z) \). Oznacza to, że bezpośrednia odległość między \( x \) i \( z \) nigdy nie przekracza sumy odległości uzyskanych przy przejściu przez ciąg pośredni \( y \).

Własności te gwarantują, że odległość Levenshteina definiuje przestrzeń metryczną na zbiorze ciągów znaków.

Jako poprawnie określona metryka pozwala ona również zdefiniować powiązaną z nią topologię metryczną indukowaną.

Dla promienia \( r \) i ciągu \( x \) kulą otwartą o środku w \( x \) nazywa się zbiór wszystkich ciągów \( y \), których odległość od \( x \) jest ściśle mniejsza od \( r \):

$$ B(x, r) = \{ y \mid D_L(x, y) < r \} $$

Zbiór wszystkich takich kul otwartych tworzy bazę topologii indukowanej.

Takie podejście jest szczególnie przydatne w dziedzinach, w których istotne znaczenie ma pojęcie podobieństwa między ciągami znaków. W automatycznych systemach korekty pisowni słowo o niewielkiej odległości Levenshteina od wyrazu znajdującego się w słowniku może zostać zaproponowane jako poprawna forma.

W tym ujęciu ciągi znaków traktuje się jako punkty przestrzeni metrycznej, a topologia indukowana umożliwia formalną analizę ich wzajemnej bliskości.

Przykład

Rozważmy zbiór \( X \) złożony z ciągów trójelementowych:

$$ X = \{"cat", "bat", "cut"\} $$

Definiujemy bazę topologii za pomocą kul otwartych o promieniu \( r = 2 \), których środkami są elementy zbioru \( X \):

$$ B(x, r) = \{ y \mid D_L(x, y) < r \} $$ 

Każda kula otwarta zawiera wszystkie ciągi różniące się od ciągu centralnego co najwyżej jedną operacją według odległości Levenshteina.

Uwaga: Dla promienia \( r = 2 \) uwzględnia się wyłącznie ciągi, których odległość jest ściśle mniejsza niż 2. Otrzymujemy więc: $$ B(x, 2) = \{ y \mid D_L(x, y) < 2 \} $$ Aby zdefiniować zbiór domknięty obejmujący również punkty brzegowe, należy zastosować nierówność nieostrą: $$ C(x, 2) = \{ y \mid D_L(x, y) \le 2 \} $$

Przeanalizujmy teraz kule otwarte o promieniu \( 2 \), których środkami są kolejne elementy zbioru \( X \):

1. Kula otwarta o środku w „cat" $$ B("cat", 2) = \{"cat", "bat"\} $$ Ciągi te można otrzymać jeden z drugiego za pomocą pojedynczej substytucji znaku.
2. Kula otwarta o środku w „bat" $$ B("bat", 2) = \{"bat", "cat"\} $$ Zbiór ten zawiera wszystkie ciągi, które można przekształcić w „bat" przy użyciu jednej operacji.
3. Kula otwarta o środku w „cut" $$ B("cut", 2) = \{"cut"\} $$ Żaden inny ciąg należący do zbioru \( X \) nie znajduje się w odległości 1 od „cut", dlatego kula zawiera wyłącznie sam ciąg „cut".

Zbiory \( B("cat", 2) \), \( B("bat", 2) \) oraz \( B("cut", 2) \) tworzą bazę topologii indukowanej przez odległość Levenshteina dla promienia \( r = 2 \).

Na podstawie tej bazy można skonstruować wszystkie pozostałe zbiory otwarte jako dowolne sumy tych kul otwartych.

Na przykład suma zbiorów \( B("bat", 2) \) oraz \( B("cut", 2) \) ma postać:

$$ B("bat", 2) \cup B("cut", 2) $$

Ponieważ \( B("bat", 2) = \{"cat", "bat"\} \) oraz \( B("cut", 2) = \{"cut"\} \), otrzymujemy:

$$ B("bat", 2) \cup B("cut", 2) = \{"cat", "bat"\} \cup \{"cut"\} $$

$$ B("bat", 2) \cup B("cut", 2) = \{"cat", "bat", "cut"\} $$

Zbiór ten również jest zbiorem otwartym w topologii indukowanej.

W ten sposób otrzymujemy topologię metryczną na zbiorze \( X \), indukowaną przez odległość Levenshteina, w której każdy zbiór otwarty można przedstawić jako sumę elementów bazy.

I tak dalej.