JavaScript의 Levenshtein 거리

레벤슈타인 거리

Levenshtein distance는 두 시퀀스 간의 차이를 측정하기 위한 문자열 메트릭입니다. 한 단어를 다른 단어로 변경하는 데 필요한 단일 문자 편집의 최소 수입니다.

예:

다음과 같은 두 개의 문자열이 있습니다.

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

이 두 문자열 사이의 Levenshtein 거리는 이 세 가지를 수정해야 하기 때문에 3입니다. -

• 새끼 고양이 → 히트("k"를 "h"로 대체)

• hitten → hittin("e"를 "i"로 대체)

• hittin → 타격 (끝에 "g" 삽입)

두 개의 문자열을 받아서 그 사이의 Levenshtein 거리를 계산하는 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