Как закодировать матрицу в JavaScript

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

Во-первых, важно понимать, что матрица — это просто вложенный массив. Например, следующий массив:

arry = [[0, 1, 2],[3, 4, 5],[6, 7, 8]]

можно переписать как:

arry =
[[0, 1, 2],
 [3, 4, 5],
 [6, 7, 8]]

Далее давайте посмотрим, как получить доступ к значениям в матрице с помощью JavaScript. Мы можем получить доступ к горизонтальным «строкам», используя нотацию arry[0] (которая возвращает [0, 1, 2]) и arry [1] (для [3, 4, 5]) и т. д. Можно использовать второй индекс для доступа к значению внутри выбранного массива или к компоненту вертикального «столбца» массива. Например, Arry[1][2] возвращает значение второго индекса массива [3, 4, 5], которое равно 5.

Чтобы использовать такую ​​матрицу в нашем коде для расстояния Левенштейна, нам потребуется возможность динамического доступа к этим значениям (то есть использовать переменные вместо жестко запрограммированных значений индекса). Пусть i представляет выбранный внутренний массив или горизонтальный индекс строки, а пусть j представляет значение в выбранном массиве или вертикальном индексе столбца. Чтобы лучше понять это, представьте, что вертикальная и горизонтальная оси матрицы помечены с помощью i и j следующим образом:

Если i = 1 и j = 0, значением матрицы будет arry[1][0] или 3. При кодировании алгоритма расстояния Левенштейна наш код JavaScript будет генерировать значения для i и j, которые будут использоваться для сравнения двух строк.

Вспомним нашу матрицу сравнения двух строк из Части 1.

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

Первым шагом в кодировании этой или любой другой матрицы является создание экземпляра внешнего массива, который будет содержать наши вложенные массивы. Установите этот пустой внешний массив равным переменной с именем grid. Затем мы заполним его внутренними массивами, используя цикл for.

Поскольку символы строки 1 являются понятными метками строк, мы знаем, что нам нужно создать такое же количество массивов, сколько букв в строке 1, плюс одна для пустой строки в начале. В цикле for начальное значение равно i = 0, условие состоит в том, что итерация должна продолжаться для всех значений, меньших длины строки плюс один, и с каждым циклом порядковый номер i должно увеличиваться на 1. Для каждой итерации создавайте пустой массив с именем row. В нашем примере из Части 1, где строка 1 — это центры, это создаст восемь пустых массивов, по одному для каждого символа в центрах плюс один для пустой строки в начале.

Затем используйте вложенный цикл for для заполнения значений внутри каждой строки. Нам потребуется столько же значений, сколько символов в строке 2, плюс один для пустой строки в начале. Значение каждого индекса j станет числом, которое будет помещено в массив row. Итак, во втором цикле for пусть индекс j также начинается с 0. Итерация должна снова продолжаться для всех индексов, меньших длины строки плюс один. И с каждым циклом номер индекса j также должен увеличиваться на 1. Вставьте j в качестве значения в каждую позицию индекса, созданную в качестве заполнителя на данный момент. Это создаст значение столбца в каждой из строк для каждого символа в строке 2. В нашем примере «центры» и «наставник» это создаст значения из семи столбцов в каждой строке, по одному для каждой буквы в «наставнике» плюс пустая строка.

Вместо того, чтобы иметь 0 в качестве первого значения каждого внутреннего массива, мы можем обновить эти числа до числовых меток строк в качестве удобного визуального ориентира для каждой строки. Мы можем сделать это, установив значение индекса 0 в каждой строке на i (которое равно 0 и увеличивается в зависимости от длины строки 1) и поместив эти значения в матрицу. Это заполнит базовый массив первым столбцом, пронумерованным от 0 до длины строки 1, и значениями остальных строк, установленными в 1 до длины строки 2.

Это также пригодится при кодировании логики заполнения такой матрицы значениями расстояния Левенштейна в следующей части этой серии. Из первой части мы знаем, что первое значение каждой строки, то есть первого столбца, всегда представляет собой количество удалений, необходимых для перехода от строки 2 по заданному индексу к пустой строке, или числа от 0 до значения длины строки. 1 плюс пустая строка. Обозначив наши строки цифрами, мы уже правильно заполнили нашу матрицу первым столбцом вычисления расстояния Левенштейна для любых двух строк.

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

Передача «центров» и «наставников» в функцию приведет к следующей матрице:

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

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)
   }
   return grid
}

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

Источники:
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 -уФ-0М

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