Перейти к содержанию

Реализации алгоритмов/Расстояние Левенштейна

Материал из Викиучебника — открытых книг для открытого мира

Здесь приведены реализации алгоритма Левенштейна на разных языках программирования.

  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

нумерация элементов массивов начинается с единицы

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

См. также

[править]