Khoảng cách Levenshtein trong JavaScript

Khoảng cách Levenshtein

Khoảng cách Levenshtein là một số liệu chuỗi để đo lường sự khác biệt giữa hai chuỗi. Đây là số lần chỉnh sửa ký tự đơn tối thiểu cần thiết để thay đổi từ này thành từ khác.

Ví dụ -

Hãy xem xét, chúng ta có hai chuỗi này -

const str1 = 'hitting';
const str2 = 'kitten';

Khoảng cách Levenshtein giữa hai chuỗi này là 3 vì chúng tôi được yêu cầu thực hiện ba chỉnh sửa này -

• kitten → hitten (thay thế "h" cho "k")

• hitten → hittin (thay thế "i" cho "e")

• hittin → hit (chèn "g" ở cuối)

Chúng tôi được yêu cầu viết một hàm JavaScript có hai chuỗi và tính toán khoảng cách Levenshtein giữa chúng.

Ví dụ

Sau đây là mã -

const str1 = 'hitting';
const str2 = 'kitten';
const levenshteinDistance = (str1 = '', str2 = '') => {
   const track = Array(str2.length + 1).fill(null).map(() =>
   Array(str1.length + 1).fill(null));
   for (let i = 0; i <= str1.length; i += 1) {
      track[0][i] = i;
   }
   for (let j = 0; j <= str2.length; j += 1) {
      track[j][0] = j;
   }
   for (let j = 1; j <= str2.length; j += 1) {
      for (let i = 1; i <= str1.length; i += 1) {
         const indicator = str1[i - 1] === str2[j - 1] ? 0 : 1;
         track[j][i] = Math.min(
            track[j][i - 1] + 1, // deletion
            track[j - 1][i] + 1, // insertion
            track[j - 1][i - 1] + indicator, // substitution
         );
      }
   }
   return track[str2.length][str1.length];
};
console.log(levenshteinDistance(str1, str2));

Đầu ra

Sau đây là kết quả trên bảng điều khiển -

3