Jak działa sam algorytm:
- ustalamy długość łańcuchów znaków (dlugoscP - długość łańcucha pierwszego, dlugoscD - długość łańcucha drugiego),
- tworzymy macierz o rozmiarze (dlugoscP+1) x (dlugoscD+1),
- inicjalizujemy pierwszy wiersz wartościami od 0 do dlugoscP,
- inicjalizujemy pierwszą kolumnę wartościami od 0 do dlugoscD,
- sprawdzamy każdy znak z łańcucha pierwszego (indeks i od 1 do dlugoscP),
- sprawdzamy każdy znak z łańcucha drugiego (indeksy j od 1 do dlugoscD),
- jeżeli znak na pozycji i równa się znakowi na pozycji j to koszt jest równy zero,
- jeżeli znak na pozycji i jest różny od znaku na pozycji j to koszt wynosi 1,
- 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.
- 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.
3 Komentarze - Odległość Levenshteina - podobieństwo łańcuchów
Dobrze wiedzieć o istnieniu tego algorytmu. Jednak czy zamiast własnej implementacji nie prościej skorzystać z metody StringUtils#getLevenshteinDistance, dostępnej w pakiecie Commons Lang od 8 lat?
@TN: Oczywiście masz rację....ale znając algorytm i kawałek kodu możemy wprowadzić na przykład inne wagi dla poszczególnych operacji usuwania, wstawiania, zamiany. Większość kodów tu dostępnych ma swoje odpowiedniki w postaci gotowych klas...ale warto czasami zrozumieć samą ideę :)
wartosciowa wiedza
Prześlij komentarz
Możesz użyć niektórych tagów HTML, takich jak <b>, <i>, <u>, <a> Nie spamuj :)