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

Описание

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

Определение

Математически, расстояние Левенштейна между двумя строками a и b (длиной |a| и |b|, соответственно) определяется с помощью

где

Здесь

это индикаторная функция (indicator function), равная 0, когда

и 1, в противном случае, а

это расстояние между первыми i символами a и первыми j символами b.

Обратите внимание, что первый элемент min соответствует удалению, второй - вставке, третий - совпадению или несовпадению в зависимости от одинаковости символов.

Пример

Расстояние Левенштейна между kitten и sitting равняется 3, поскольку для преобразования первой строки во вторую необходимо выполнить следующие операции:

kitten -> sitten (замена k на s)
sitten -> sittin (замена e на i)
sittin -> sitting (вставка g в конец)

Применение

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

Динамическое программирование

Рассмотрим простой пример нахождения минимального редакционного расстояния между строками ME и MY. Интуитивно мы понимаем, что оно равняется 1 операции, которой является замена E на Y. Однако давайте формализуем это в алгоритм, чтобы иметь возможность решать более сложные задачи, например, задачу преобразования Saturday в Sunday.

Для применения указанной выше математической формулы к преобразованию ME -> MY нам для начала нужно вычислить минимальные расстояния ME -> M, M -> MY и M -> M. Затем надо взять минимальное расстояние и добавить одну операцию для замены E на Y. Поэтому минимальное редакционное расстояние трансформации ME -> MY вычисляется на основе трех предыдущих возможных преобразований.

Нарисуем матрицу:

Ячейка (0:1) содержит красное число 1. Это означает, что для преобразования M в пустую строку требуется 1 операция. Этой операцией является удаление. Вот почему число красное
ячейка (0:2) содержит красное число 2. Это означает, что для преобразования ME в пустую строку требуется 2 операции. Этими операциями являются удаление E и M
ячейка (1:0) содержит зеленое число 1. Это означает, что для преобразования пустой строки в M требуется 1 операция. Этой операцией является вставка M. Вот почему число зеленое
ячейка (2:0) содержит зеленое число 2. Это означает, что для преобразования пустой строки в MY требуется 2 операции. Этими операциями являются вставка Y и M
ячейка (1:1) содержит число 0. Это означает, что для преобразования M в M ничего делать не нужно
ячейка (1:2) содержит красное число 1. Это означает, что для преобразования ME в M требуется 1 операция. Этой операцией является удаление E
и т.д.

Для небольших матриц (в нашем случае 3x3) все выглядит просто, но тоже самое применяется для вычисления таких чисел для больших матриц (например, 9x7 для преобразования Saturday -> Sunday).

Согласно формуле нам нужны 3 соседние ячейки (i-1:j), (i-1:j-1) и (i:j-1) для вычисления числа для текущей ячейки (i:j). Все, что нужно сделать - найти минимальную соседнюю ячейку и прибавить к ней 1 в случае, если строка i и колонка j содержат разные символы.

Рекурсивную природу задачи можно проиллюстрировать следующим образом:

Нарисуем граф решений для этой задачи:

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

Также можно видеть, что каждое число ячейки вычисляется на основе предыдущих. Поэтому здесь применяется техника табулирования (заполнение кэша снизу вверх).

Дальнейшее применение этого принципа позволяет решать более сложные задачи, например, преобразование Saturday -> Sunday:

Реализация

// algorithms/strings/levenshtein-distance.js
export default function levenshteinDistance(a, b) {
  // Создаем пустую матрицу редактирования
  const matrix = new Array(b.length + 1)
    .fill(null)
    .map(() => new Array(a.length + 1).fill(null))

  // Заполняем первую строку матрицы.
  // Если это первая строка, тогда мы преобразуем пустую строку в `a`.
  // В этом случае количество модификаций равняется размеру подстроки
  for (let i = 0; i <= a.length; i++) {
    matrix[0][i] = i
  }

  // Заполняем первую колонку матрицы.
  // Если это первая колонка, тогда мы преобразуем пустую строку в `b`.
  // В этом случае количество модификаций равняется размеру подстроки
  for (let j = 0; j <= b.length; j++) {
    matrix[j][0] = j
  }

  // Заполняем матрицу редактирования
  for (let j = 1; j <= b.length; j++) {
    for (let i = 1; i <= a.length; i++) {
      const indicator = b[j - 1] === a[i - 1] ? 0 : 1
      matrix[j][i] = Math.min(
        matrix[j][i - 1] + 1, // удаление
        matrix[j - 1][i] + 1, // вставка
        matrix[j - 1][i - 1] + indicator, // замена
      )
    }
  }

  return matrix[b.length][a.length]
}

Тестирование

// algorithms/strings/__tests__/levenshtein-distance.test.js
import levenshteinDistance from '../levenshtein-distance'

describe('levenshteinDistance', () => {
  it('должен вычислить расстояния Левенштейна между двумя строками', () => {
    expect(levenshteinDistance('', '')).toBe(0)
    expect(levenshteinDistance('a', '')).toBe(1)
    expect(levenshteinDistance('', 'a')).toBe(1)
    expect(levenshteinDistance('abc', '')).toBe(3)
    expect(levenshteinDistance('', 'abc')).toBe(3)

    // Нужно добавить `I` в начало
    expect(levenshteinDistance('islander', 'slander')).toBe(1)

    // Нужно заменить `M` на `K`, `T` на `M` и добавить `A` в конец
    expect(levenshteinDistance('mart', 'karma')).toBe(3)

    // Нужно заменить `K` на `S`, `E` на `I` и добавить `G` в конец
    expect(levenshteinDistance('kitten', 'sitting')).toBe(3)

    // Нужно добавить 4 буквы `FOOT` в начало
    expect(levenshteinDistance('ball', 'football')).toBe(4)

    // Нужно удалить 4 буквы `FOOT` в начале
    expect(levenshteinDistance('football', 'foot')).toBe(4)

    // Нужно заменить первые 5 букв `INTEN` на `EXECU`
    expect(levenshteinDistance('intention', 'execution')).toBe(5)
  })
})

Запускаем тесты:

npm run test ./algorithms/strings/__tests__/levenshtein-distance