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

JavaScriptJavaScriptBeginner
Практиковаться сейчас

This tutorial is from open-source community. Access the source code

💡 Этот учебник переведен с английского с помощью ИИ. Чтобы просмотреть оригинал, вы можете перейти на английский оригинал

Введение

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


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL javascript(("JavaScript")) -.-> javascript/BasicConceptsGroup(["Basic Concepts"]) javascript(("JavaScript")) -.-> javascript/ToolsandEnvironmentGroup(["Tools and Environment"]) javascript/BasicConceptsGroup -.-> javascript/variables("Variables") javascript/BasicConceptsGroup -.-> javascript/data_types("Data Types") javascript/BasicConceptsGroup -.-> javascript/arith_ops("Arithmetic Operators") javascript/BasicConceptsGroup -.-> javascript/comp_ops("Comparison Operators") javascript/BasicConceptsGroup -.-> javascript/cond_stmts("Conditional Statements") javascript/BasicConceptsGroup -.-> javascript/loops("Loops") javascript/BasicConceptsGroup -.-> javascript/array_methods("Array Methods") javascript/ToolsandEnvironmentGroup -.-> javascript/debugging("Debugging") subgraph Lab Skills javascript/variables -.-> lab-28469{{"Реализация расстояния Левенштейна на JavaScript"}} javascript/data_types -.-> lab-28469{{"Реализация расстояния Левенштейна на JavaScript"}} javascript/arith_ops -.-> lab-28469{{"Реализация расстояния Левенштейна на JavaScript"}} javascript/comp_ops -.-> lab-28469{{"Реализация расстояния Левенштейна на JavaScript"}} javascript/cond_stmts -.-> lab-28469{{"Реализация расстояния Левенштейна на JavaScript"}} javascript/loops -.-> lab-28469{{"Реализация расстояния Левенштейна на JavaScript"}} javascript/array_methods -.-> lab-28469{{"Реализация расстояния Левенштейна на JavaScript"}} javascript/debugging -.-> lab-28469{{"Реализация расстояния Левенштейна на JavaScript"}} end

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

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

  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, чтобы улучшить свои навыки.