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

Введение

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

Skills Graph

Алгоритм расстояния Левенштейна

Для вычисления разницы между двумя строками можно использовать алгоритм расстояния Левенштейна. Вот, как это можно сделать:

1. Если длина любой из строк равна нулю, вернуть длину другой строки.
2. Использовать вложенный цикл for для перебора букв в целевой и исходной строках.
3. Вычислить стоимость замены букв, соответствующих i - 1 и j - 1 в целевой и исходной строках соответственно (0, если они одинаковые, 1 в противном случае).
4. Использовать Math.min() для заполнения каждого элемента в двумерном массиве минимальным значением из ячейки выше, увеличенной на один, ячейки слева, увеличенной на один, или ячейки в верхнем левом углу, увеличенной на ранее вычисленную стоимость.
5. Вернуть последний элемент последней строки сформированного массива.

Для начала практики кодирования откройте Терминал/SSH и введите node. Вот код, который можно использовать:

const levenshteinDistance = (s, t) => {
  if (!s.length) return t.length;
  if (!t.length) return s.length;
  const arr = [];
  for (let i = 0; i <= t.length; i++) {
    arr[i] = [i];
    for (let j = 1; j <= s.length; j++) {
      arr[i][j] =
        i === 0
          ? j
          : Math.min(
              arr[i - 1][j] + 1,
              arr[i][j - 1] + 1,
              arr[i - 1][j - 1] + (s[j - 1] === t[i - 1] ? 0 : 1)
            );
    }
  }
  return arr[t.length][s.length];
};

console.log(levenshteinDistance("duck", "dark")); // 2

Резюме

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