Расстояние Левенштейна

Расстояние Левенштейна (также дистанция Левенштейна, функция Левенштейна, алгоритм Левенштейна или дистанция редактирования) в теории информации и компьютерной лингвистике — это мера разницы двух последовательностей символов (строк) относительно минимального количества операций вставки, удаления и замены, необходимых для перевода одной строки в другую.

Метод разработан в 1965 году советским математиком Владимиром Иосифовичем Левенштейном и назван его именем.

Пример

Чтобы перевести слово «конь» в слово «кот» нужно совершить одно удаление и одну замену, соответственно расстояние Левенштейна составляет 2:

Конь → Коть (Заменяем н на т)
Коть → Кот (Удаляем ь)

Практическим применением расстояния Левенштейна является определение похожести последовательностей символов, к примеру в исправлении орфографии или при поиске повторов.

Применение

Расстояние Левенштейна активно применяется при поиске и обработке текстов

в поисковых системах для нахождения объектов или записей по имени
в базах данных при поиске с неполно-заданным или неточно-заданным именем
для коррекции ошибок при вводе текста
для коррекции ошибок в результате автоматического распознавания отсканнированного текста или речи
в других приложениях, связанных с автоматической обработкой текстов

С точки зрения приложений определение расстояния между словами или текстовыми полями по Левенштейну обладает следующими недостатками:

При перестановке местами слов или частей слов получаются сравнительно большие расстояния
Расстояния между абсолютно разными короткими словами оказываются небольшими, в то время как расстояние между сильно похожими длинными словами оказываются значительными

Алгоритм

Чаще всего используемый, простой алгоритм для расчета расстояния редактирования нуждается в матрице формы (n + 1) × (m+1), где n и m суть длины сравниваемых строк. В псевдокоде алгоритм выглядит так:

int LevenshteinDistance(char s[1..n], char t[1..m])
   declare int d[0..n,0..m]
   declare int i, j, cost
   for i := 0 to n
       d[i,0] := i
   for j := 0 to m
       d[0,j] := j
   for i := 1 to n
       for j := 1 to m
           if s[i] = t[j] then cost := 0
                          else cost := 1
           d[i,j] := minimum(d[i-1,j  ] + 1,    // insertion
                             d[i,  j-1] + 1,    // deletion
                             d[i-1,j-1] + cost) // substitution
   return d[n,m]

Этот алгоритм легко реализуем и вручную в виде таблицы.

В языке программирования PHP этот алгоритм реализован функцией levenshtein.

Границы

Для Дистанции Левенштейна существуют следующие верхние и нижние границы:

Дистанция Левенштейна, как минимум, равна разнице длины сравниваемых строк
Она не может быть больше длины самой длинной строки
Она равна 0 только когда обе строки равны
Если обе строки имеют одинаковую длину, то расстояние Хэмминга является верхней границей
Если длина строк различна, то верхней границей является расстояние Хэмминга плюс разница в длине

Реализации

Алгоритм Левенштейна в среде 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 (где нумерация элементов массивов начинается с нуля):

static int levDistance(String s1, String s2)
{
    int lengthS1 = s1.length();
    int lengthS2 = s2.length();
    int tab[][] = new int[lengthS1 + 1][lengthS2 + 1];
    int i, j, diff;
    for( i = 0; i <= lengthS1; i++ )
        tab[i][0] = i;
    for( j = 0; j <= lengthS2; j++ )
        tab[0][j] = j;
    for( i = 1; i <= lengthS1; i++ )
    {
        for( j = 1; j <= lengthS2; j++ )
        {
            if ( s1.charAt( i - 1 ) == s2.charAt( j - 1 ) )
                diff = 0;
            else
                diff = 1;
            tab[i][j] = min( min(tab[i-1][j] + 1,       // insertion
                                 tab[i][j-1] + 1),      // deletion
                                 tab[i-1][j-1] + diff); // substitution
        }
    }
    return tab[lengthS1][lengthS2];
}

Алгоритм Левенштейна на языке 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]*m
        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 = change + 1
            current_row[j] = min(add, delete, change)
            
    return current_row[n]

Алгоритм Левенштейна на языке 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));
...

Алгоритм Левенштейна на языке C++:

#include <vector>
#include <algorithm>

template <typename T>
typename T::size_type levenshtein_distance(const T & src, const T & dst) {
  const typename T::size_type m = src.size();
  const typename T::size_type n = dst.size();
  if (m == 0) {
    return n;
  }
  if (n == 0) {
    return m;
  }

  std::vector< std::vector<typename T::size_type> > matrix(m + 1);

  for (typename T::size_type i = 0; i <= m; ++i) {
    matrix[i].resize(n + 1);
    matrix[i][0] = i;
  }
  for (typename T::size_type i = 0; i <= n; ++i) {
    matrix[0][i] = i;
  }

  typename T::size_type above_cell, left_cell, diagonal_cell, cost;

  for (typename T::size_type i = 1; i <= m; ++i) {
    for(typename T::size_type j = 1; j <= n; ++j) {
      cost = src[i - 1] == dst[j - 1] ? 0 : 1;
      above_cell = matrix[i - 1][j];
      left_cell = matrix[i][j - 1];
      diagonal_cell = matrix[i - 1][j - 1];
      matrix[i][j] = std::min(std::min(above_cell + 1, left_cell + 1), diagonal_cell + cost);
    }
  }
      
  return matrix[m][n];
}

Пример использования:

// Может быть использован любой подходящий контейнер (напр. std::vector).
// В нашем примере использованы строки:
...
const std::string src = "125";
const std::string dst = "521";
const std::string::size_type distance = levenshtein_distance(src, dst);
...

Алгоритм Левенштейна на языке 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);

Родственные методы

Расстояние Левенштейна

Содержание

Пример

Применение

Алгоритм

Границы

Реализации

Родственные методы

Навигация

Расстояние Левенштейна

Пример

Применение

Алгоритм

Границы

Реализации

Родственные методы

Навигация

Поиск