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

Материал из Википедии — свободной энциклопедии

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

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

[править] Пример

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

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

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

[править] Применение

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

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

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

1. При перестановке местами слов или частей слов получаются сравнительно большие расстояния
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];
}

[править] Родственные методы

• Расстояние Хемминга
• Расстояние Йенцена-Шаннона
• Soundex-метод
• Фонетический поиск