FE 검색 구현에서 검색어와 타겟의 유사성 체크하기 - 레벤슈타인 거리 (Levenshtein Distance) ♥️ With 타입스크립트

프론트엔드 개발자로서, 우리는 사용자의 오타를 교정하거나 비슷한 단어를 찾는 기능을 종종 구현한다.

 

예를 들어, 검색 창에서 "javascipt"라고 입력하면 "javascript"를 추천해주는 기능은 흔하게 찾을 수 있다 👍

(r이 빠졌는데도 찾아준다)

이처럼 두 문자열의 차이를 계산하는 알고리즘 중 하나가 바로 레벤슈타인 거리(Levenshtein Distance)입니다.

 

이번 글에서는 레벤슈타인 거리란 무엇인지, 그리고 이를 타입스크립트로 구현하는 방법을 단계별로 알아보았다.

---

리벤슈타인 거리란?

리벤슈타인 거리는 두 문자열 사이의 최소 편집 거리를 계산하는 알고리즘이다.

여기서 [편집]은 다음 세 가지 작업을 의미한다.

1. 삽입 (Insertion): 문자 하나를 추가
2. 삭제 (Deletion): 문자 하나를 제거
3. 교체 (Substitution): 문자 하나를 다른 문자로 대체

예를 들어:

• "kitten" -> "sitting"의 리벤슈타인 거리는 3이다.
  1. "k"를 "s"로 교체.
  2. "e"를 "i"로 교체.
  3. 마지막에 "g"를 삽입.

---

리벤슈타인 거리 계산 방법

리벤슈타인 거리를 계산하기 위해 우리는 2차원 배열을 사용하여 동적 프로그래밍(Dynamic Programming) 방식으로 문제를 풀 수 있다.

단계별로 접근해보자 ! 🙌

1. 문제
   두 문자열 A와 B가 주어졌을 때, A를 B로 변환하는 최소 편집 거리를 구한다.
2. 조건
   빈 문자열을 다른 문자열로 변환하려면, 삽입이나 삭제 작업만 필요하다.
3. 아이디어
   두 문자가 같다면, 이전 값 그대로 가져온다.
   다르다면 삽입, 삭제, 교체 중 최소 비용을 선택한다.

공식은 다음과 같다.

---

타입스크립트로 구현하기 🍟

이제 직접 타입스크립트로 리벤슈타인 거리 알고리즘을 구현해 보자.

function levenshteinDistance(a: string, b: string): number {
  const m = a.length;
  const n = b.length;

  // 2차원 배열 생성
  const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  // 초기 값 설정
  for (let i = 0; i <= m; i++) {
    dp[i][0] = i;
  }

  for (let j = 0; j <= n; j++) {
    dp[0][j] = j;
  }

  // 동적 프로그래밍 계산
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],    // 삭제
          dp[i][j - 1],    // 삽입
          dp[i - 1][j - 1] // 교체
        );
      }
    }
  }

  return dp[m][n];
}

// 테스트
console.log(levenshteinDistance("kitten", "sitting")); // 3
console.log(levenshteinDistance("flaw", "lawn"));     // 2

 

작성한 코드는 위와 같다 ❗

1. 2차원 배열 생성
   dp는 편집 거리를 저장하는 테이블로,
   dp[i][j]는 문자열 A의 처음 i개 문자와 문자열 B의 처음 j개 문자의 최소 편집 거리를 나타낸다.
2. 초기 값 설정
   첫 번째 행과 첫 번째 열은 빈 문자열과 비교한 결과로, 인덱스 값으로 초기화한다.
3. 동적 프로그래밍 계산
   두 문자가 같으면 이전 값(dp[i-1][j-1])을 그대로 가져온다.
   다르면 삽입, 삭제, 교체 중 최소 값을 선택하고 1을 더한다.
4. 결과 반환
   최종적으로 dp[m][n]에 두 문자열의 최소 편집 거리가 저장된다.

 

이 알고리즘은 실제로는 어디에 사용될 수 있을까 ❓

오타 교정 기능

레벤슈타인 거리 알고리즘을 사용하여 사용자의 입력값과 사전에 저장된 단어들 간의 편집 거리를 계산하면, 가장 비슷한 단어를 추천할 수 있다.

function suggestWord(input: string, dictionary: string[]): string {
  let closestWord = "";
  let minDistance = Infinity;

  for (const word of dictionary) {
    const distance = levenshteinDistance(input, word);
    if (distance < minDistance) {
      minDistance = distance;
      closestWord = word;
    }
  }

  return closestWord;
}

// 테스트
const dictionary = ["javascript", "typescript", "java", "python"];
console.log(suggestWord("javascipt", dictionary)); // "javascript"

 

👻  위에서 사용한 예제와 비슷하게 정해진 List 내에서 검색을 할 때 검색어와 List 내부의 후보들의 유사성을 확인한 뒤 사용자에게 결과를 추천해줄 수도 있다 !

 

레벤슈타인 거리는 문자열 유사도를 계산하는 강력한 알고리즘으로, 프론트엔드 개발에서도 유용하게 활용할 수 있다.

 

특히 검색, 자동 완성, 오타 교정 등에서 큰 역할을 하기에, 알아두면 좋을 것 같다 🥝

 

+ 개인적으로 이번 글을 통해 타입스크립트를 사용해 구현하면서 오랜만에 알고리즘에 대해서 생각해볼 수 있었다!

 

😊 참고 자료

https://en.wikipedia.org/wiki/Levenshtein_distance

Levenshtein distance - Wikipedia

https://www.npmjs.com/package/kled

kled