Odległość Levenshteina - podobieństwo łańcuchów

Do obliczania podobieństwa łańcuchów tekstowych wykorzystuje się algorytm Levenshteina (Vladimir Levenshtein - rosyjski uczony), znany również jako odległość edycyjna, albo odległość Levenshteina. Otrzymana w wyniku działania algorytmu liczba symbolizuje ile działań prostych musimy wykonać, aby dokonać konwersji/zamiany jednego łańcucha na drugi. Działania proste to wstawienie znaku, usunięcie znaku oraz zamiana znaku na inny. Dla łańcucha "kot" i "kod" odległość edycyjna wynosi 1. Musimy dokonać tylko jednej zamiany znaku. Im większa odległość tym bardziej różne są łańcuchy znaków.

Jak działa sam algorytm:

1. ustalamy długość łańcuchów znaków (dlugoscP - długość łańcucha pierwszego, dlugoscD - długość łańcucha drugiego),
2. tworzymy macierz o rozmiarze (dlugoscP+1) x (dlugoscD+1),
3. inicjalizujemy pierwszy wiersz wartościami od 0 do dlugoscP,
4. inicjalizujemy pierwszą kolumnę wartościami od 0 do dlugoscD,
5. sprawdzamy każdy znak z łańcucha pierwszego (indeks i od 1 do dlugoscP),
6. sprawdzamy każdy znak z łańcucha drugiego (indeksy j od 1 do dlugoscD),
7. jeżeli znak na pozycji i równa się znakowi na pozycji j to koszt jest równy zero,
8. jeżeli znak na pozycji i jest różny od znaku na pozycji j to koszt wynosi 1,
9. ustawiamy wartość komórki i,j jako minimum:
• komórka powyżej + 1,
• komórka z lewej + 1,
• komórka po skosie (góra, lewo) + koszt.
10. algorytm powtarzamy dla wszystkich znaków, całkowity koszt otrzymamy w komórce o indeksie dlugoscP, dlugoscD

Sprawdźmy działanie algorytmu na przykładzie dwóch łańcuchów: "notatnik" i "kodatnik". Poniżej utworzona została macierz i obliczone zostały odpowiednie wartości komórek.

    n o t a t n i k
  0 1 2 3 4 5 6 7 8
k 1 1 2 3 4 5 6 7 7
o 2 2 1 2 3 4 5 6 7
d 3 3 2 2 3 4 5 6 7
a 4 4 3 3 2 3 4 5 6
t 5 5 4 3 3 2 3 4 5
n 6 5 5 4 4 3 2 3 4
i 7 6 6 5 5 4 3 2 3
k 8 7 7 6 6 5 4 3 2

Odczytana odległość edycyjna wynosi zatem 2 (wartość komórki o indeksie [8][8]). Dodatkowo możemy określić podobieństwo wyrazów stosując następujący wzór:

1 / (1 + OL)

gdzie OL to odległość Levenshteina dla dwóch łańcuchów obliczona zgodnie z powyższym algorytmem. Dla naszego przykładu podobieństwo wynosi: 1/3.

Poniżej prosty program liczący odległość Levenshteina oraz podobieństwo łańcuchów.

import java.util.Scanner;

/**
 * Obliczanie odległości Levenshteina (odległości edycyjnej)
 * Wyznaczanie podobieństwa łancuchów znaków
 * @author kodatnik.blogspot.com
 */
public class Levenshtein {

 public static int obliczOdleglosc(String p, String d) {
  // określamy długości łańcuchów znaków
  int dlugoscP = p.length();
  int dlugoscD = d.length();

  // tworzymy odpowiednią macierz
  int[][] macierz = new int[dlugoscP + 1][dlugoscD + 1];

  // uzupełniamy pierwszy wiersz i pierwszą kolumnę
  for(int i = 0; i <= dlugoscP; macierz[i][0] = i++);
  for(int j = 1; j <= dlugoscD; macierz[0][j] = j++);

  // sprawdzamy poszczególne znaki
  for(int i = 1; i <= dlugoscP; i++) {
   char znak = p.charAt(i - 1);
   for(int j = 1; j <= dlugoscD; j++) {
    // obliczamy koszt
    int koszt = macierz[i - 1][j - 1];
    if(d.charAt(j - 1) !=  znak ) koszt++;
    // wstawiamy minimum
    macierz[i][j] = Math.min( Math.min( macierz[i - 1][j] + 1, macierz[i][j - 1] + 1), koszt);
   }
  }
  // zwracamy całkowity koszt, odległość Levenshteina
  return macierz[dlugoscP][dlugoscD];
 }

 public static double obliczPodobienstwo(String lancuchPierwszy, String lancuchDrugi) {
  // obliczamy i zwracamy podobieństwo łańcuchów
  return (1.0/(1.0 + obliczOdleglosc(lancuchPierwszy, lancuchDrugi)));
 }

 public static void main(String[] args) {
  String lancuchPierwszy, lancuchDrugi;

  // pobieramy dane
  Scanner wejscie = new Scanner(System.in);
  System.out.print("Podaj pierwszy ciąg znaków: ");
  lancuchPierwszy = wejscie.nextLine();
  System.out.print("Podaj drugi ciąg znaków: ");
  lancuchDrugi = wejscie.nextLine();

  // wyświetlamy obliczone wyniki
  System.out.println("Odległość Levenshteina: " + obliczOdleglosc(lancuchPierwszy, lancuchDrugi));
  System.out.println("Podobieństwo ciągów znaków: " + obliczPodobienstwo(lancuchPierwszy, lancuchDrugi));
 }
}

Wynik działania programu dla przykładowych danych.

Podaj pierwszy ciąg znaków: notatnik
Podaj drugi ciąg znaków: kodatnik
Odległość Levenshteina: 2
Podobieństwo ciągów znaków: 0.3333333333333333

Praktyczne wykorzystanie algorytmu to między innymi sprawdzanie pisownii, rozpoznawanie mowy, analiza DNA, wykrywanie plagiatów itp.