JavaScript 에서 Levenshtein Distance 마스터하기

소개

이 랩에서는 Levenshtein Distance 알고리즘과 JavaScript 에서의 구현을 살펴봅니다. 이 랩의 목적은 한 문자열을 다른 문자열로 변환하는 데 필요한 최소한의 단일 문자 편집 (삽입, 삭제, 대체) 횟수를 측정하여 두 문자열 간의 차이를 계산하는 방법을 이해하는 것입니다. 이 랩을 마치면 Levenshtein Distance 알고리즘에 대한 확실한 이해와 이를 자신의 JavaScript 프로젝트에서 사용하는 방법을 알게 될 것입니다.

Levenshtein Distance 알고리즘

두 문자열 간의 차이를 계산하려면 Levenshtein Distance 알고리즘을 사용할 수 있습니다. 방법은 다음과 같습니다.

문자열 중 하나의 length가 0 이면, 다른 문자열의 length를 반환합니다.
중첩된 for 루프를 사용하여 대상 및 소스 문자열의 문자를 반복합니다.
대상 및 소스에서 각각 i - 1 및 j - 1에 해당하는 문자를 대체하는 비용을 계산합니다 (같으면 0, 그렇지 않으면 1).
Math.min()을 사용하여 2 차원 배열의 각 요소를 위쪽 셀에 1 을 더한 값, 왼쪽 셀에 1 을 더한 값, 또는 왼쪽 위 셀에 이전에 계산된 비용을 더한 값 중 최소값으로 채웁니다.
생성된 배열의 마지막 행의 마지막 요소를 반환합니다.

이 코딩을 연습하려면 터미널/SSH 를 열고 node를 입력하십시오. 사용할 수 있는 코드는 다음과 같습니다.

const levenshteinDistance = (s, t) => {
  if (!s.length) return t.length;
  if (!t.length) return s.length;
  const arr = [];
  for (let i = 0; i <= t.length; i++) {
    arr[i] = [i];
    for (let j = 1; j <= s.length; j++) {
      arr[i][j] =
        i === 0
          ? j
          : Math.min(
              arr[i - 1][j] + 1,
              arr[i][j - 1] + 1,
              arr[i - 1][j - 1] + (s[j - 1] === t[i - 1] ? 0 : 1)
            );
    }
  }
  return arr[t.length][s.length];
};

console.log(levenshteinDistance("duck", "dark")); // 2

요약

축하합니다! Levenshtein Distance 랩을 완료했습니다. LabEx 에서 더 많은 랩을 연습하여 실력을 향상시킬 수 있습니다.

JavaScript 로 Levenshtein Distance 구현하기

소개

Levenshtein Distance 알고리즘

요약