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].


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.

0	1	2	3	4	5
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.

0	1	2	3	4	5
1	1
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.

0	1	2	3	4	5
1	1
2	2
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.

0	1	2	3	4	5
1	1
2	2
3	2
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.

0	1	2	3	4	5
1	1
2	2
3	2
4	3

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

0	1	2	3	4	5
1	1	2
2	2	1
3	2	2
4	3	3

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

0	1	2	3	4	5
1	1	2	3	4	5
2	2	1	2	3	4
3	2	2	2	2	3
4	3	3	3	3	2

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.