algorytm.org

Odległość Levenshteina (odległość edycyjna)

Praca
Interesuje Cię praca przy weryfikacji oprogramowania do samolotów?
Sprawdź to!
Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Odległość Levenshteina (odległość edycyjna)
Ocena użytkowników:***** / 23
SłabyŚwietny 
Wpisany przez Rafał Świetlicki, 06 lutego 2009 18:51

Algorytm Levenshteina, służy do liczenia odległości edycyjnej (odległości Levenshteina). Jest to najmniejsza liczba działań prostych, przeprowadzająca jeden napis w drugi.
Działania proste to:
  • wstawienie nowego znaku
  • usuniecie znaku
  • zamiana na inny znak

Idea algorytmu to stworzenie tablicy dwuwymiarowej, o wymiarach n+1 na m+1 gdzie n i m to odpowiednio długości porównywanych słów.
Pierwszy wiersz i kolumnę uzupełniamy wartościami od 0 do, odpowiednio n i m.
Następnie bierzemy po kolei wartości wiersza i porównujemy literkę dotyczącą tego wiersza z literą dotyczącą kolumny. Dokonujemy porównania liter na zasadzie każdy z każdym. Przy każdym porównaniu wykonujemy poniższą procedurę. Jeśli literki są identyczne, ustawiamy koszt na 0, jeśli nie, na 1. Teraz musimy daną komórkę wypełnić wartością, którą będzie minimum z:
  • wartości komórki leżącej bezpośrednio nad naszą aktualną komórka zwiększonej o 1,
  • wartości komórki leżącej bezpośrednio w lewo od naszej aktualnej komórki + 1
  • wartości komórki leżącej bezpośrednio w lewą-górna stronę od aktualnej komórki + koszt

Po wykonaniu wszystkich porównań, naszą odległością edycyjną będzie wartość w komórce [n+1, m+1].

Przykład:

Obliczymy odległość Levenshteina dla wyrazów: "foka" i "kotka".
Na początek zainicjujemy pierwszy wiersz i kolumnę w naszej tablicy wielkości 4+1 na 5+1.

012345
1     
2     
3     
4     

Teraz policzmy wartości dla drugiej kolumny, czyli pierwszej litery wyrazu kotka i kolejnych liter wyrazu foka.
k jest różne od f, zatem nasz koszt wynosi 1, bierzemy zatem minimum z liczb: 1+1 (komórka nad powiększona o 1), 1+1 (komórka z lewej powiększona o 1) oraz 0+1 (komórka po ukosie lewa-górna + koszt). Zatem wpisujemy 1.

012345
11    
2     
3     
4     

Kolejna para to k i o, zatem koszt wynosi 1. Bierzemy więc minimum z liczb: 1+1 (komórka nad powiększona o 1), 2+1 (komórka z lewej powiększona o 1) oraz 1+1 (komórka po ukosie lewa-górna + koszt). Zatem wpisujemy 2.

012345
11    
22    
3     
4     

Następna para to k i k, zatem koszt wynosi 0. Bierzemy więc minimum z liczb: 2+1 (komórka nad powiększona o 1), 3+1 (komórka z lewej powiększona o 1) oraz 2+0 (komórka po ukosie lewa-górna + koszt). Zatem wpisujemy 2.

012345
11    
22    
32    
4     

Ostatnia para w tej kolumnie to k i a, zatem koszt wynosi 1. Bierzemy więc minimum z liczb: 2+1 (komórka nad powiększona o 1), 4+1 (komórka z lewej powiększona o 1) oraz 3+1 (komórka po ukosie lewa-górna + koszt). Zatem wpisujemy 3.

012345
11    
22    
32    
43    

Teraz policzmy wartości dla drugiej kolumny, czyli drugiej litery wyrazu kotka i kolejnych liter wyrazu foka.

012345
112   
221   
322   
433   

Postępując analogicznie dla kolejnych wierszy uzupełnimy tabelę następująco.

012345
112345
221234
322223
433332

W dolnym prawym narożniku znajduje się wynik 2 czyli odległość edycyjna wyrazów "foka" i "kotka". Zatem od jednego do drugiego wyrazu możemy przejść w dwóch prostych działaniach:
foka -> kotka: 1) zamieniając f na k, 2) dodając literę t,
kotka -> foka: 1) zamieniając k na f, 2) usuwając literę t.

Algorytm ten stosuje się m.in w analizie DNA, rozpoznawaniu plagiatów, korekcie pisowni - wyszukiwanie podpowiedzi prawidłowego wyrazu.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC#
.cs
.cs
***** / 6
Rafał ŚwietlickiC/C++
.cpp
.cpp
***** / 3
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 1
Tomasz LubińskiJava
.java
.java
***** / 2
Paweł ŁuczakRuby
.rb
.rb
***** / 1
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 29 września 2012 16:33
Komentarze
photo
0 # Kubuś & Gabi 2013-12-16 08:51
Super ;))
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Romek 2014-01-25 14:44
W PHP jest już ta funkcja zaimplementowan a.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Bartek_Gość 2015-03-16 14:33
Ad.1
oraz 0+1 (komórka po ukosie lewa-górna + koszt). Zatem wpisujemy 1.

Ad.2
oraz 1+1 (komórka po ukosie lewa-górna + koszt). Zatem wpisujemy 2.

Ad.3
oraz 2+0 (komórka po ukosie lewa-górna + koszt). Zatem wpisujemy 2.

W Ad.1, Ad.2 oraz Ad.3 doszło do zsumowania 0+1 = 1; 1+1=2 oraz 0+2 = 0

Ad.4
oraz 3+1 (komórka po ukosie lewa-górna + koszt). Zatem wpisujemy 3.

Ale dlaczego nie doszło do zsumowania w Ad.4 ???
3+1=4 a zostaje 3 ???
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Tomasz Lubiński 2015-09-08 08:47
Dlatego że bierzemy minimum z 3 liczb:
- komórka nad + 1, czyli: 2 + 1 = 3
- komórka z lewej + 1, czyli 4 + 1 = 5
- komórka po ukosie + koszt = 3 + 1 = 4.

Minimum z (3, 5, 4) to 3, dlatego ostatecznie wpisujemy tą właśnie wartość.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz