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

Материал из Викиучебника — открытых книг для открытого мира
Перейти к навигации Перейти к поиску

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

Visual Basic 6.0[править]

Option Base 0

Public Function LevenshteinDistance(s1 As String, s2 As String) As Long
    Dim l1 As Long: l1 = VBA.Len(s1) + 1
    Dim l2 As Long: l2 = VBA.Len(s2) + 1

    If l1 = 1 Then Err.Raise 449
    If l2 = 1 Then Err.Raise 449

    Dim diff As Byte
    Dim m() As Long
    Dim i As Long
    ReDim m(l1, l2)
    Dim b1() As Byte: b1 = VBA.StrConv(s1, VBA.VbStrConv.vbUnicode)
    Dim b2() As Byte: b2 = VBA.StrConv(s2, VBA.VbStrConv.vbUnicode)

    For i = 0 To l1
        m(i, 1) = i
    Next

    For j = 0 To l2
        m(1, j) = j
    Next

    For i = 1 To l1
        For j = 1 To l2
            If b1(i - 1) = b2(j - 1) Then diff = 0 Else diff = 1
            m(i, j) = Min(m(i - 1, j) + 1, m(i, j - 1) + 1, m(i - 1, j - 1) + diff)
        Next
    Next

    LevenshteinDistance = m(l1, l2) - 1

End Function

' Вспомогательная функция
Function Min(v1 As Integer, v2 As Integer, v3 As Integer) As Integer
    Min = IIf(v1 < v2, v1, v2)
    If Min > v3 Then Min = v3
End Function

' Пример использования
MsgBox LevenshteinDistance("папа", "мама")

PHP[править]

<?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
?>

JavaScript[править]

/**
 * @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');

Haskell[править]

 import Data.List

 levenshtein s1 s2 = last $ foldl (transform s1) [0..length s1] s2 where
         transform str xs@(x:xs') c = res where
                 res = x + 1 : zipWith4 compute str xs xs' res
                 compute c' x y z = minimum [y + 1, z + 1, x + if c' == c then 0 else 1]

Среда 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

Java[править]

Линейное потребление памяти без выделения памяти в процессе работы алгоритма.

    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);
    }

Scala[править]

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 )

Python[править]

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]

Turbo Pascal[править]

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.

Delphi[править]

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));
...

Perl[править]

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,
                        $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");

C++[править]

Имплементация использует памяти:

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

C#[править]

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);

Transact-SQL[править]

Примечание: Данная процедура может использоваться только в качестве примера, или для тестирования в силу плохой производительности.

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

Go[править]

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

См. также[править]