Реализации алгоритмов/Расстояние Левенштейна
(перенаправлено с «Расстояние Левенштейна»)
Здесь приведены реализации алгоритма Левенштейна на разных языках программирования.
Public Function levenshtein(ByVal string1 As String, ByVal string2 As String) As Long
Dim i As Long, j As Long, bs1() As Byte, bs2() As Byte
Dim string1_length As Long
Dim string2_length As Long
Dim distance() As Long
Dim min1 As Long, min2 As Long, min3 As Long
string1_length = Len(string1)
string2_length = Len(string2)
ReDim distance(string1_length, string2_length)
bs1 = string1
bs2 = string2
For i = 0 To string1_length
distance(i, 0) = i
Next
For j = 0 To string2_length
distance(0, j) = j
Next
For i = 1 To string1_length
For j = 1 To string2_length
'slow way: If Mid$(string1, i, 1) = Mid$(string2, j, 1) Then
If bs1((i - 1) * 2) = bs2((j - 1) * 2) Then ' *2 because Unicode every 2nd byte is 0
distance(i, j) = distance(i - 1, j - 1)
Else
'distance(i, j) = Application.WorksheetFunction.Min _
(distance(i - 1, j) + 1, _
distance(i, j - 1) + 1, _
distance(i - 1, j - 1) + 1)
' spell it out, 50 times faster than worksheetfunction.min
min1 = distance(i - 1, j) + 1
min2 = distance(i, j - 1) + 1
min3 = distance(i - 1, j - 1) + 1
If min1 <= min2 And min1 <= min3 Then
distance(i, j) = min1
ElseIf min2 <= min1 And min2 <= min3 Then
distance(i, j) = min2
Else
distance(i, j) = min3
End If
End If
Next
Next
levenshtein = distance(string1_length, string2_length)
End Function
' Пример использования
MsgBox levenstein("папа", "мама")
<?PHP
function distance($source, $dest) {
if ($source == $dest) {
return 0;
}
list($slen, $dlen) = [strlen($source), strlen($dest)];
if ($slen == 0 || $dlen == 0) {
return $dlen ? $dlen : $slen;
}
$dist = range(0, $dlen);
for ($i = 0; $i < $slen; $i++) {
$_dist = [$i + 1];
for ($j = 0; $j < $dlen; $j++) {
$cost = ($source[$i] == $dest[$j]) ? 0 : 1;
$_dist[$j + 1] = min(
$dist[$j + 1] + 1, // deletion
$_dist[$j] + 1, // insertion
$dist[$j] + $cost // substitution
);
}
$dist = $_dist;
}
return $dist[$dlen];
}
$source = 'PHP';
$dest = 'new PHP test';
echo distance($source, $dest) . "\n";
echo levenshtein($source, $dest); // built-in PHP function
?>
/**
* @param {string} s1 Исходная строка
* @param {string} s2 Сравниваемая строка
* @param {object} [costs] Веса операций { [replace], [replaceCase], [insert], [remove] }
* @return {number} Расстояние Левенштейна
*/
function levenshtein(s1, s2, costs) {
var i, j, l1, l2, flip, ch, chl, ii, ii2, cost, cutHalf;
l1 = s1.length;
l2 = s2.length;
costs = costs || {};
var cr = costs.replace || 1;
var cri = costs.replaceCase || costs.replace || 1;
var ci = costs.insert || 1;
var cd = costs.remove || 1;
cutHalf = flip = Math.max(l1, l2);
var minCost = Math.min(cd, ci, cr);
var minD = Math.max(minCost, (l1 - l2) * cd);
var minI = Math.max(minCost, (l2 - l1) * ci);
var buf = new Array((cutHalf * 2) - 1);
for (i = 0; i <= l2; ++i) {
buf[i] = i * minD;
}
for (i = 0; i < l1; ++i, flip = cutHalf - flip) {
ch = s1[i];
chl = ch.toLowerCase();
buf[flip] = (i + 1) * minI;
ii = flip;
ii2 = cutHalf - flip;
for (j = 0; j < l2; ++j, ++ii, ++ii2) {
cost = (ch === s2[j] ? 0 : (chl === s2[j].toLowerCase()) ? cri : cr);
buf[ii + 1] = Math.min(buf[ii2 + 1] + cd, buf[ii] + ci, buf[ii2] + cost);
}
}
return buf[l2 + cutHalf - flip];
}
Пример использования:
var diff = levenshtein('Hello', 'HelA_1');
import Data.List
{- |
Функция 'levenshtein' вычисляет расстояние Левенштейна для заданных списков.
Ненужные строки отбрасываются в процессе. Требует O(N) памяти на каждом шаге.
-}
levenshtein :: (Eq a) => [a] -> [a] -> Int
levenshtein cs = last . foldl transform [0 .. length cs]
where
transform ds'@(d : ds) d' = res
where
compute c x y z = (min y z + 1) `min` if c == d' then x else x + 1
res = d + 1 : zipWith4 compute cs ds' ds res
-- | Функция 'levenshtein'' вычисляет полную матрицу. Требует O(NM) памяти.
levenshtein' :: Eq a => [a] -> [a] -> [[Int]]
levenshtein' cs = scanl transform [0 .. length cs]
where
transform ds'@(d : ds) d' = res
where
compute c x y z = (min y z + 1) `min` if c == d' then x else x + 1
res = d + 1 : zipWith4 compute cs ds' ds res
Среда PowerBuilder
правитьнумерация элементов массивов начинается с единицы
function integer gf_lev_distance (string a_vsource, string a_vtarget);
integer l_nlength_vsource
integer l_nlength_vtarget
integer v_cost
integer column_to_left[],current_column[]
integer i,j
v_cost = 0
l_nlength_vsource = len(a_vsource)
l_nlength_vtarget = len(a_vtarget)
if l_nlength_vsource = 0 then
return l_nlength_vtarget
elseif l_nlength_vtarget = 0 then
return l_nlength_vsource
ELSE
FOR j = 1 to (l_nlength_vtarget + 1)
column_to_left[j] = j
next
FOR i = 1 to l_nlength_vsource
current_column[1] = i
FOR j = 2 to (l_nlength_vtarget + 1)
IF mid(a_vsource, i, 1) = mid(a_vtarget, j - 1, 1) THEN
v_cost = 0
ELSE
v_cost = 1
END IF
current_column[j] = current_column[j - 1] + 1
if (column_to_left[j] + 1) < current_column[j] then
current_column[j] = column_to_left[j] + 1
end if
if (column_to_left[j - 1] + v_cost) < current_column[j] then
current_column[j] = column_to_left[j - 1] + v_cost
end if
next
FOR j = 1 to (l_nlength_vtarget + 1)
column_to_left[j] = current_column[j]
next
next
end if
return current_column[l_nlength_vtarget + 1] - 1
end function
Линейное потребление памяти без выделения памяти в процессе работы алгоритма.
public static int levenstain(@Nonnull String str1, @Nonnull String str2) {
// Массивы должны быть одинаковой длины, т.к. отражают две строки (или столбца) одной и той же таблицы (см. алгоритм расстояния Левенштейна)
int[] Di_1 = new int[str2.length() + 1];
int[] Di = new int[str2.length() + 1];
for (int j = 0; j <= str2.length(); j++) {
Di[j] = j; // (i == 0)
}
for (int i = 1; i <= str1.length(); i++) {
System.arraycopy(Di, 0, Di_1, 0, Di_1.length);
Di[0] = i; // (j == 0)
for (int j = 1; j <= str2.length(); j++) {
int cost = (str1.charAt(i - 1) != str2.charAt(j - 1)) ? 1 : 0;
Di[j] = min(
Di_1[j] + 1,
Di[j - 1] + 1,
Di_1[j - 1] + cost
);
}
}
return Di[Di.length - 1];
}
private static int min(int n1, int n2, int n3) {
return Math.min(Math.min(n1, n2), n3);
}
class Lowenstein(s1: String, s2: String) {
private val m: Int = s1.length
private val n: Int = s2.length
private val matrix = Array.ofDim[Int](m + 1, n + 1)
private val distance: Int = {
def mo(i: Int, j: Int): Int = if (s1(i) == s2(j)) 0 else 1
def min(numbers: Int*): Int = numbers.min
for (i <- 0 to m) matrix(i)(0) = i
for (i <- 1 to n) matrix(0)(i) = i
for (i <- 1 to m; j <- 1 to n) {
matrix(i)(j) = min(
matrix(i - 1)(j) + 1,
matrix(i)(j - 1) + 1,
matrix(i - 1)(j - 1) + mo(i - 1, j - 1)
)
}
matrix(m)(n)
}
def getDistance = distance
}
пример использования:
println( new Lowenstein("Hi, men!", "Hi, women!").getDistance )
def distance(a, b):
"Calculates the Levenshtein distance between a and b."
n, m = len(a), len(b)
if n > m:
# Make sure n <= m, to use O(min(n, m)) space
a, b = b, a
n, m = m, n
current_row = range(n + 1) # Keep current and previous row, not entire matrix
for i in range(1, m + 1):
previous_row, current_row = current_row, [i] + [0] * n
for j in range(1, n + 1):
add, delete, change = previous_row[j] + 1, current_row[j - 1] + 1, previous_row[j - 1]
if a[j - 1] != b[i - 1]:
change += 1
current_row[j] = min(add, delete, change)
return current_row[n]
program LeveDist; {Turbo PASCAL}
{ реализация функции в принципе соответствует описанию с одной оговоркой:
матрица из описания заменена статическим буфером, длина которого
равна удвоенной максимальной длине строк это сделано для
1) экономии памяти и во избежание её перераспределений
2) повышения быстродействия
таким образом, в реализации половинами буфера представлены только
две последние строки матрицы, которые меняются местами каждую
итерацию внешнего цикла (по i)... для определения того, какая из половин
буфера является "нижней строкой", служит переменная flip
т.е. при flip = false первая половина буфера является предпоследней
строкой, а вторая-последней; при flip = true наоборот,
первая половина-последняя строка, вторая половина-предпоследняя}
function levenshtein(s, t: string): integer;
function min3(a, b, c: integer): integer; {вспомогательная функция}
var res: integer;
begin
res:= a;
if b < res then
res:= b;
if c < res then
res:= c;
min3:= res;
end;
const cuthalf = 255; {макс. длина обрабатываемых строк}
var i, j, m, n: integer;
cost: integer;
flip: boolean;
Res: integer;
buf: array[0..((cuthalf*2)-1)] of integer;
{ рабочий буфер, заменяет матрицу, представленную в описании}
begin
s:=copy(s, 1, cuthalf-1);
t:=copy(t, 1, cuthalf-1);
m:=length(s);
n:=length(t);
if m = 0 then Res:=n else
if n = 0 then Res:=m else
begin
flip:=false;
for i:=0 to n do
buf[i]:=i;
for i:=1 to m do
begin
if flip then buf[0]:=i else
buf[cuthalf]:=i;
for j:=1 to n do
begin
if s[i] = t[j] then cost:=0 else
cost:=1;
if flip then
buf[j]:=min3((buf[cuthalf+j]+1),
(buf[j-1]+1), (buf[cuthalf+j-1]+cost))
else
buf[cuthalf+j]:=min3((buf[j]+1),
(buf[cuthalf+j-1]+1), (buf[j-1]+cost));
end;
flip:=not flip;
end;
if flip then Res:=buf[cuthalf+n] else
Res:=buf[n];
end;
levenshtein:=Res;
end;
var s1, s2: string;
begin
readln(s1);
readln(s2);
writeln(levenshtein(s1,s2));
end.
const
cuthalf = 100; // константа, ограничивающая макс. длину
// обрабатываемых строк
var
buf: array[0..((cuthalf * 2) - 1)] of integer; // рабочий буфер, заменяет
// матрицу, представленную
// в описании
function min3(a, b, c: integer): integer; // вспомогательная функция
begin
Result := a;
if b < Result then
Result := b;
if c < Result then
Result := c;
end;
// реализация функции в принципе соответствует описанию с одной оговоркой:
// матрица из описания заменена статическим буфером, длина которого
// равна удвоенной максимальной длине строк
// это сделано для 1) экономии памяти и во избежание её перераспределений
// 2) повышения быстродействия (у меня функция работает
// в обработчике onfilterRecord)
// таким образом, в реализации половинами буфера представлены только
// две последние строки матрицы, которые меняются местами каждую
// итерацию внешнего цикла (по i)... для определения того, какая из половин
// буфера является "нижней строкой", служит переменная flip
// т. е. при flip = false первая половина буфера является предпоследней
// строкой, а вторая - последней; при flip = true наоборот,
// первая половина - последняя строка, вторая половина - предпоследняя
function LeveDist(s, t: string): integer;
var
i, j, m, n: integer;
cost: integer;
flip: boolean;
begin
s := copy(s, 1, cuthalf - 1);
t := copy(t, 1, cuthalf - 1);
m := length(s);
n := length(t);
if m = 0 then
Result := n
else if n = 0 then
Result := m
else
begin
flip := false;
for i := 0 to n do
buf[i] := i;
for i := 1 to m do
begin
if flip then
buf[0] := i
else
buf[cuthalf] := i;
for j := 1 to n do
begin
if s[i] = t[j] then
cost := 0
else
cost := 1;
if flip then
buf[j] := min3((buf[cuthalf + j] + 1),
(buf[j - 1] + 1),
(buf[cuthalf + j - 1] + cost))
else
buf[cuthalf + j] := min3((buf[j] + 1),
(buf[cuthalf + j - 1] + 1),
(buf[j - 1] + cost));
end;
flip := not flip;
end;
if flip then
Result := buf[cuthalf + n]
else
Result := buf[n];
end;
end;
Пример использования:
// на форме имеются поля Edit1 и Edit2, метка Label1
...
Label1.Caption := IntToStr(LeveDist(Edit1.Text, Edit2.Text));
...
sub levenshtein($$){
my @A=split //, lc shift;
my @B=split //, lc shift;
my @W=(0..@B);
my ($i, $j, $cur, $next);
for $i (0..$#A){
$cur=$i+1;
for $j (0..$#B){
$next=min(
$W[$j+1]+1,d
$cur+1,
($A[$i] ne $B[$j])+$W[$j]
);
$W[$j]=$cur;
$cur=$next;
}
$W[@B]=$next;
}
return $next;
}
sub min($$$){
if ($_[0] < $_[2]){ pop; } else { shift; }
return $_[0] < $_[1]? $_[0]:$_[1];
}
Пример использования:
print levenshtein("google","googol");
Имплементация использует памяти:
#include <algorithm>
#include <vector>
template<typename T>
typename T::size_type LevenshteinDistance(const T &source,
const T &target) {
if (source.size() > target.size()) {
return LevenshteinDistance(target, source);
}
using TSizeType = typename T::size_type;
const TSizeType min_size = source.size(), max_size = target.size();
std::vector<TSizeType> lev_dist(min_size + 1);
for (TSizeType i = 0; i <= min_size; ++i) {
lev_dist[i] = i;
}
for (TSizeType j = 1; j <= max_size; ++j) {
TSizeType previous_diagonal = lev_dist[0], previous_diagonal_save;
++lev_dist[0];
for (TSizeType i = 1; i <= min_size; ++i) {
previous_diagonal_save = lev_dist[i];
if (source[i - 1] == target[j - 1]) {
lev_dist[i] = previous_diagonal;
} else {
lev_dist[i] = std::min(std::min(lev_dist[i - 1], lev_dist[i]), previous_diagonal) + 1;
}
previous_diagonal = previous_diagonal_save;
}
}
return lev_dist[min_size];
}
Пример использования:
// Может быть использован любой подходящий контейнер (напр. std::vector).
// В нашем примере использованы строки:
...
const std::string src = "125";
const std::string dst = "521";
const std::string::size_type distance = LevenshteinDistance(src, dst);
...
Имплементация обобщённого расстояния Левенштейна с произвольными стоимостями вставки, удаления и замены символа:
#include <algorithm>
#include <vector>
template<typename T>
typename T::size_type GeneralizedLevenshteinDistance(const T &source,
const T &target,
typename T::size_type insert_cost = 1,
typename T::size_type delete_cost = 1,
typename T::size_type replace_cost = 1) {
if (source.size() > target.size()) {
return GeneralizedLevenshteinDistance(target, source, delete_cost, insert_cost, replace_cost);
}
using TSizeType = typename T::size_type;
const TSizeType min_size = source.size(), max_size = target.size();
std::vector<TSizeType> lev_dist(min_size + 1);
lev_dist[0] = 0;
for (TSizeType i = 1; i <= min_size; ++i) {
lev_dist[i] = lev_dist[i - 1] + delete_cost;
}
for (TSizeType j = 1; j <= max_size; ++j) {
TSizeType previous_diagonal = lev_dist[0], previous_diagonal_save;
lev_dist[0] += insert_cost;
for (TSizeType i = 1; i <= min_size; ++i) {
previous_diagonal_save = lev_dist[i];
if (source[i - 1] == target[j - 1]) {
lev_dist[i] = previous_diagonal;
} else {
lev_dist[i] = std::min(std::min(lev_dist[i - 1] + delete_cost, lev_dist[i] + insert_cost), previous_diagonal + replace_cost);
}
previous_diagonal = previous_diagonal_save;
}
}
return lev_dist[min_size];
}
public static int LevenshteinDistance(string string1, string string2)
{
if (string1 == null) throw new ArgumentNullException("string1");
if (string2 == null) throw new ArgumentNullException("string2");
int diff;
int[,] m = new int[string1.Length + 1, string2.Length + 1];
for (int i = 0; i <= string1.Length; i++) { m[i, 0] = i; }
for (int j = 0; j <= string2.Length; j++) { m[0, j] = j; }
for (int i = 1; i <= string1.Length; i++)
{
for (int j = 1; j <= string2.Length; j++)
{
diff = (string1[i - 1] == string2[j - 1]) ? 0 : 1;
m[i, j] = Math.Min(Math.Min(m[i - 1, j] + 1, m[i, j - 1] + 1), m[i - 1, j - 1] + diff);
}
}
return m[string1.Length, string2.Length];
}
Пример использования:
string s1="мама";
string s2="папа";
int diff=LevenshteinDistance(s1,s2);
Примечание: Данная процедура может использоваться только в качестве примера, или для тестирования в силу плохой производительности.
create procedure LevenshteinDistance(@string1 varchar(4000), @string2 varchar(4000))
as
begin
set nocount on
if (@string1 is null) Raiserror ('Строка 1 не должна быть пустой', 16, 1);
if (@string2 is null) Raiserror ('Строка 2 не должна быть пустой', 16, 1);
declare @diff int
declare @len1 int
declare @len2 int
set @len1 = len(@string1)
set @len2 = len(@string2)
declare @m table (i int, j int, val int)
declare @i int, @j int
set @i = 0
while (@i <= @len1)
begin
delete @m where i=@i and j=0
insert into @m (i, j, val)
values (@i, 0, @i)
set @i = @i + 1
end
set @j = 0
while (@j <= @len2)
begin
delete @m where i=0 and j=@j
insert into @m (i, j, val)
values (0, @j, @j)
set @j = @j + 1
end
set @i = 1
while (@i <= @len1) begin
set @j = 1
while (@j <= @len2) begin
if (substring(@string1, @i, 1) = substring(@string2, @j, 1))
set @diff = 0
else
set @diff = 1
declare @minval int
select @minval = min(val)
from (
select isnull(val, 0) + 1 as val
from @m
where i = @i-1 and j = @j
union
select isnull(val, 0) + 1 as val
from @m
where i = @i and j = @j-1
union
select isnull(val, 0) + @diff as val
from @m
where i = @i-1 and j = @j-1
) t
delete @m where i=@i and j=@j
insert into @m (i, j, val)
values (@i, @j, isnull(@minval, 0))
set @j = @j + 1
end
set @i = @i + 1
end
declare @retval int
select @retval = isnull(val, 0)
from @m
where i = @len1 and j = @len2
return @retval
end
Пример использования:
declare @retval int
exec @retval = LevenshteinDistance 'Петрова Дарья Ивановна', 'Петрова Марья Ивановна'
select @retval
func distance(s1, s2 string) int {
min := func(values ...int) int {
m := values[0]
for _, v := range values {
if v < m {
m = v
}
}
return m
}
r1, r2 := []rune(s1), []rune(s2)
n, m := len(r1), len(r2)
if n > m {
r1, r2 = r2, r1
n, m = m, n
}
currentRow := make([]int, n+1)
previousRow := make([]int, n+1)
for i := range currentRow {
currentRow[i] = i
}
for i := 1; i <= m; i++ {
for j := range currentRow {
previousRow[j] = currentRow[j]
if j == 0 {
currentRow[j] = i
continue
} else {
currentRow[j] = 0
}
add, del, change := previousRow[j]+1, currentRow[j-1]+1, previousRow[j-1]
if r1[j-1] != r2[i-1] {
change++
}
currentRow[j] = min(add, del, change)
}
}
return currentRow[n]
}