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.

pokaż źródło

drukujpomoc

01.import java.util.Scanner;

02. 

03./**

04. * Obliczanie odległości Levenshteina (odległości edycyjnej)

05. * Wyznaczanie podobieństwa łancuchów znaków

06. * @author kodatnik.blogspot.com

07. */

08.public class Levenshtein {

09. 

10. public static int obliczOdleglosc(String p, String d) {

11.  // określamy długości łańcuchów znaków

12.  int dlugoscP = p.length();

13.  int dlugoscD = d.length();

14. 

15.  // tworzymy odpowiednią macierz

16.  int[][] macierz = new int[dlugoscP + 1][dlugoscD + 1];

17. 

18.  // uzupełniamy pierwszy wiersz i pierwszą kolumnę

19.  for(int i = 0; i <= dlugoscP; macierz[i][0] = i++);

20.  for(int j = 1; j <= dlugoscD; macierz[0][j] = j++);

21. 

22.  // sprawdzamy poszczególne znaki

23.  for(int i = 1; i <= dlugoscP; i++) {

24.   char znak = p.charAt(i - 1);

25.   for(int j = 1; j <= dlugoscD; j++) {

26.    // obliczamy koszt

27.    int koszt = macierz[i - 1][j - 1];

28.    if(d.charAt(j - 1) !=  znak ) koszt++;

29.    // wstawiamy minimum

30.    macierz[i][j] = Math.min( Math.min( macierz[i - 1][j] + 1, macierz[i][j - 1] + 1), koszt);

31.   }

32.  }

33.  // zwracamy całkowity koszt, odległość Levenshteina

34.  return macierz[dlugoscP][dlugoscD];

35. }

36. 

37. public static double obliczPodobienstwo(String lancuchPierwszy, String lancuchDrugi) {

38.  // obliczamy i zwracamy podobieństwo łańcuchów

39.  return (1.0/(1.0 + obliczOdleglosc(lancuchPierwszy, lancuchDrugi)));

40. }

41. 

42. public static void main(String[] args) {

43.  String lancuchPierwszy, lancuchDrugi;

44. 

45.  // pobieramy dane

46.  Scanner wejscie = new Scanner(System.in);

47.  System.out.print("Podaj pierwszy ciąg znaków: ");

48.  lancuchPierwszy = wejscie.nextLine();

49.  System.out.print("Podaj drugi ciąg znaków: ");

50.  lancuchDrugi = wejscie.nextLine();

51. 

52.  // wyświetlamy obliczone wyniki

53.  System.out.println("Odległość Levenshteina: " + obliczOdleglosc(lancuchPierwszy, lancuchDrugi));

54.  System.out.println("Podobieństwo ciągów znaków: " + obliczPodobienstwo(lancuchPierwszy, lancuchDrugi));

55. }

56.}

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.