JavaScriptでのレーベンシュタイン距離

レーベンシュタイン距離

レーベンシュタイン距離は、2つのシーケンス間の差を測定するための文字列メトリックです。これは、ある単語を別の単語に変更するために必要な1文字の編集の最小数です。

例-

これらの2つの文字列があると考えてください-

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

これらの3つの編集を行う必要があるため、これら2つの文字列間のレーベンシュタイン距離は3です-

• 子猫→殴られた（「k」の代わりに「h」を使用）

• hitten→hittin（「e」の代わりに「i」を使用）

• hittin→hitting（末尾に「g」を挿入）

2つの文字列を受け取り、それらの間のレーベンシュタイン距離を計算するJavaScript関数を作成する必要があります。

例

以下はコードです-

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));

出力

以下はコンソールでの出力です-

3