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

В институтах всех нас учат сравнивать две строки по принципу равны/не равны и искать строку в подстроке. На практике же, когда строки не равны, интересен вопрос, а насколько отличаются две строки? Расстояние Левенштейна определяет, сколько раз надо добавить/удалить/заменить символ, чтобы одну строку превратить в другую. Например, расстояние между словами kitten и sitting равно трем. 

Расстояние Левенштейна применяется на практике в следующ случаях:

• в поисковых системах для нахождения объектов или записей по имени
• в базах данных при поиске с неполно-заданным или неточно-заданным именем
• для исправления ошибок при вводе текста
• для исправления ошибок в результате автоматического распознавания отсканированного текста или речи
• в других приложениях, связанных с автоматической обработкой текстов
• для сравнения текстовых файлов утилитой diff и ей подобными. Здесь роль «символов» играют строки, а роль «строк» — файлы.
• в биоинформатике для сравнения генов, хромосом и белков.

Чаще всего используемый, простой алгоритм для расчета расстояния редактирования нуждается в матрице d формы (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,    // вставка
                             d[i,  j-1] + 1,    // удаление
                             d[i-1,j-1] + cost) // замена
   return d[n,m]

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

На практике расстояние Левенштейна обладет следующими недостатками:

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