Как кодировать матрицу расстояний Левенштейна

Части 1 и 2 этой серии охватывают базовое объяснение расстояния Левенштейна и пошаговые инструкции как закодировать простую матрицу. Далее мы создадим код, который заполняет матрицу значениями расстояния Левенштейна для любых двух строк. Давайте вернемся к окончательной матрице, сгенерированной нашим кодом в части 2, если в функцию передаются строки центры и ментор.

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

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

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

Давайте закодируем эту функциональность. Удалите возвратную сетку в нижней части существующего кода. Мы заменим это новой логикой: во-первых, мы хотим перебрать каждый элемент в каждой строке, чтобы мы могли установить его значение. Для этого мы можем создать еще один вложенный цикл for. На этот раз, однако, начнем с первого индекса (установив начальные значения для i и j равными 1), так как нулевой индекс является пустой строкой и поскольку это значение уже заполнен нашей матрицей, созданной из Части 2.

Затем создайте оператор if, который проверяет, равна ли строка 1 строке 2 по этому текущему индексу. Помните, что в матрице обе строки имеют пустую строку («») в начале каждого слова, но фактические строки передаются в качестве аргументов. Таким образом, чтобы проверить последний символ в каждой строке, вы должны использовать индекс, отличный от текущего индекса в матрице. Символ конечной точки для каждой строки имеет индексы str1[i -1] и str2[j -1]. .

Если символы конечной точки совпадают, установите для текущего значения индекса то же значение, что и для индекса в верхнем левом углу. Если текущий индекс — grid[i][j], то верхний левый угловой индекс — (grid [i – 1][j – 1]).

В противном случае, если символы конечной точки не равны, найдите минимальное из трех окружающих значений, либо значение слева от текущего индекса (grid[i] [ j -1]), значение в левом верхнем углу текущего индекса (grid[i - 1][j - 1]), или значение непосредственно над текущим индексом (grid[i -1][j]), и установите текущее значение индекса до этого минимума увеличивается на единицу.

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

Это значение представляет собой расстояние Левенштейна для ваших двух строк.

Окончательный код вместе выглядит так:

function levDist(str1, str2) {
   const grid = []
   for (let i = 0; i < str1.length + 1; i++) {
      const row = []
      for (let j = 0; j < str2.length + 1; j++) {
         row.push(j)
      }
      row[0] = i
      grid.push(row)
   }
   for (let i = 1; i < str1.length + 1; i++) {
      for (let j = 1; j < str2.length + 1; j++) {
         if (str1[i - 1] === str2[j - 1]) {
            grid[i][j] = grid[i - 1][j - 1]
         }else {
            grid[i][j] = 1 + Math.min(
               grid[i][j - 1],
               grid[i - 1][j - 1], 
               grid[i - 1][j])
         }
      }
   }
   return grid[str1.length][str2.length]
}

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

Расстояние Левенштейна — это сложный алгоритм для понимания, а тем более для кодирования. Я изо всех сил пытался найти существующие учебные пособия, предназначенные для начинающих программистов, когда мне нужно было изучить этот алгоритм, поэтому я создал свой собственный. Это руководство, состоящее из трех частей, предназначено для того, чтобы разбить каждый шаг на процесс, доступный для программистов с любым уровнем опыта. Имея базовые знания JavaScript, справиться с этой задачей может любой!

Источники:

https://www.30secondsofcode.org/js/s/Levenshtein enshtein-distance
https://www.youtube.com/watch?v=_1Qb95R87jU
https://medium.com/@ ethannam/understanding-the-Levenshtein enshtein-distance-equation-for-beginners-c4285a5604f0
https://www.youtube.com/watch?v=MiqoA-yF-0M

Больше контента на plainenglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Получите эксклюзивный доступ к возможностям написания и советам в нашем сообществе Discord.