KLED: 한국어를 지원하는 퍼지 검색 라이브러리

거의 3년 전쯤에 대충 만드는 퍼지 문자열 검색 라이브러리에 관한 글을 작성한 적이 있다. 혹시 퍼지 검색 혹은 퍼지 매칭에 관해 궁금하다면 해당 글을 읽어보자. 어쨌든 그때 글을 작성하면서 "제대로 만드는 방법"도 잠깐 언급한 적이 있었다.

정확히 일치하지는 않더라도 대충 비슷한 느낌의 문자열을 찾아주는 방법, 즉 퍼지 문자열 매칭(fuzzy string matching)은 굳이 정규표현식으로 작성할 필요가 없을만큼 이미 다양한 방식으로 구현되어 있다. 대체로 입력한 문자열과 대상 문자열이 얼마나 일치하는지 거리를 반환하며 금방 검색해서 찾을 수 있는 것만 해도 Levenshtein, N-grams, Q-grams, Hamming, Jaro-Winkler, Jaccard 등 다양한 알고리듬이 존재한다. 이름을 알만한 언어에서는 이미 구현된 라이브러리가 존재할테니 관심있으면 코드를 살펴보는 것도 좋다.

최근 개인적으로 작은 오픈소스 챌린지를 하고 있는데 그와 관련해서 아이디어를 찾다가 몇 년 전에 썼던 글이 생각났다. 그리고 이번에는 검증된 알고리듬을 사용하여 "제대로" 만들어보고자 했다.

리벤슈타인 편집 거리

라이브러리의 이름은 제목에 있는 KLED이다. 아마 눈치 빠른 분이라면 짐작할 수도 있겠지만, KLED는 리벤슈타인 편집 거리(Levenshtein Edit Distance) 알고리듬을 기반으로 작성되었다. 여기서 사용된 리벤슈타인 거리 알고리듬에 대해서는 더 잘 설명된 글이 많으니 이를 참고하도록 하자. 여기에 내가 검색해보았던 국내 블로그 몇 개를 링크해본다.

간단하게 말해 리벤슈타인 편집 거리는 A라는 문자열을 B라는 문자열로 바꾸기 위해 몇 번의 편집이 일어나야 하는지 확인한다. 여기서 말하는 편집 행위는 삽입, 삭제, 수정이다. 예를 들어, "abc"라는 문자열을 "abd"로 바꾸려면 마지막에 있는 c 문자를 d로 변경해야 하기 때문에, 두 문자열 사이의 편집 거리는 1이 된다. 여기서는 모든 행위의 편집 거리가 1이라고 가정했지만 편집 행위별로 가중치를 주는 방법도 있다. 알고리듬에 대한 자세한 설명은 위 링크에서 확인해보자. 어쨌든 이를 TypeScript로 작성해보면 다음과 같다.

function distance(a: string, b: string, caseSensitive = false): number {
  if (a.length == 0) return b.length;
  if (b.length == 0) return a.length;

  if (!caseSensitive) {
    a = a.toLowerCase();
    b = b.toLowerCase();
  }
  if (a === b) return 0;

  const table: number[][] = [];

  table[0] = Array(a.length + 1).fill(0).map((_, n) => n);

  for (let i = 1; i <= b.length; i++) {
    table[i] = [i];
  }

  for (let i = 1; i <= b.length; i++) {
    for (let j = 1; j <= a.length; j++) {
      const bChar = b[i - 1];
      const aChar = a[j - 1];

      if (bChar === aChar) {
        table[i][j] = table[i - 1][j - 1];
      } else {
        table[i][j] = Math.min(table[i - 1][j - 1] + 1, table[i][j - 1] + 1, table[i - 1][j] + 1);
      }
    }
  }

  return table[b.length][a.length];
}

그런데 리벤슈타인 편집 거리는 다른 알고리듬과 마찬가지로 한국어 검색은 고려되어 있지 않다. 단순하게 'ㄱ'과 '강'을 완전히 다른 문자로 취급하여 마치 a를 b로 바꾸는 것처럼 편집 거리가 계산된다. 완성된 문서에서는 큰 문제가 아닐 수도 있지만, 한국어 사용자가 검색하는 도중이라면 불편함을 느낄 수 있다. 아이폰 등장 이전, 거의 20년 전 피처폰에서도 되던 초성 검색인데 말이다.

KLED는 기본적으로 조합 중인 상태로 보이는 한글 문자를 모두 같다고 판단한다. 예를 들어, ㄱ, 가, 강은 모두 동일하다고 보고 리벤슈타인 편집 거리를 계산한다. 그런데 이렇게 작성해두면 "강남구"라는 문자열에서 검색할 때 "ㄱㄴ"과 "강남"의 편집 거리가 같다고 나와버린다. 그래서 한글 부분 일치에 대해서는 아주 작은 가중치를 주어서 완전히 일치하는 것보다는 아주 조금 멀지만 한 글자를 수정하는 것보다는 훨씬 작은 거리로 만들었다.

function distance(a: string, b: string, caseSensitive = false): number {
  if (a.length == 0) return b.length;
  if (b.length == 0) return a.length;

  if (!caseSensitive) {
    a = a.toLowerCase();
    b = b.toLowerCase();
  }
  if (a === b) return 0;

  const table: number[][] = [];

  table[0] = Array(a.length + 1).fill(0).map((_, n) => n);

  for (let i = 1; i <= b.length; i++) {
    table[i] = [i];
  }

  for (let i = 1; i <= b.length; i++) {
    for (let j = 1; j <= a.length; j++) {
      const bChar = b[i - 1];
      const aChar = a[j - 1];
      let korSimilarity = 0; // Similarity between Korean characters

      if (bChar !== aChar && isKorean(bChar) && isKorean(bChar)) {
        if (isSimilar(aChar, bChar)) {
          korSimilarity = 0.01;
        }
      }

      if (korSimilarity > 0 || bChar === aChar) {
        table[i][j] = table[i - 1][j - 1] + korSimilarity;
      } else {
        table[i][j] = Math.min(table[i - 1][j - 1] + 1, table[i][j - 1] + 1, table[i - 1][j] + 1);
      }
    }
  }

  return table[b.length][a.length];
}

function isKorean(c: string): boolean {
  return ('ㄱ' <= c && c <= 'ㅎ') || ('가' <= c && c <= '힣');
}

function isSimilar(a: string, b: string): boolean {
  if (a === b) return true;

  // 둘 중 하나가 초성이면 두 문자열의 초성만 비교한다.
  if (isConsonant(a) || isConsonant(b)) {
    return getConsonant(a) === getConsonant(b);
  }

  // 그 외엔 종성을 제거한 글자를 비교한다.
  return omitFinal(a) === omitFinal(b);
}

퍼지 매칭

이제 두 문자열 간의 유사도는 구할 수 있게 되었다. 그 다음에는 검색어와 검색 대상 문자열을 입력하여 유사도 점수를 반환하는 matches 함수를 작성할 차례이다. 이 함수는 기본적으로 두 가지를 가정하고 있다.

검색어의 길이는 검색 대상 문자열의 길이보다 작거나 같아야 한다.
검색어의 모든 글자는 나타난 순서대로 검색 대상 문자열에 반드시 포함되어 있어야 한다.
검색 대상 문자열의 길이에 상관없이 유사도 점수는 0부터 1 사이의 실수로 반환된다.

1번과 2번 조건에 의해 두 문자열 간의 리벤슈타인 거리의 최댓값은 검색 대상 문자열의 길이가 된다. 따라서 1, 2 조건을 만족하는 검색어와 검색 대상 문자열을 기준으로 리벤슈타인 거리를 구하고 이 값을 검색 대상 문자열의 길이로 나눈 다음, 1에서 빼면 유사도 점수를 구할 수 있다. 1에 가까울 수록 근접한 것이며 0에 가까울 수록 일치하지 않다고 본다.

matches 함수는 먼저 두 문자열이 1, 2번 조건을 만족하는지 확인하고 뒤에 설명한 방법으로 유사도 점수를 반환한다. 그리 어렵지 않은 부분이라서 이 글에는 옮기지 않는다. 하지만 모든 코드를 GitHub에 공개해두었으므로 원한다면 직접 살펴볼 수 있다. 또한 위 기능은 kled라는 npm 패키지로도 만들어두었으므로 필요하다면 편하게 사용할 수도 있다.

실제 사용 사례를 보여주기 위해 기존에 만들었던 도시 이름 검색 예제를 조금 변경하여 KLED를 사용하는 버전으로 만들어보았다. 아래 링크에서 사용해 볼 수 있다. 지역 이름 옆에 있는 숫자는 유사도 점수를 의미한다 (이미지를 클릭하면 커진다).

https://output.jsbin.com/cakelan/1

마치며

이 라이브러리를 만들게 된 이유 중 하나는 기존에 만든 버전에 관심을 가져주시는 분들 때문이었다. '대충' 만든 걸 가져다 쓰시겠다고 하는 말을 보니 어쩐지 조금 더 제대로 만들어서 공개해야 할 것 같은 압박을 (스스로) 느꼈다. 그래서 가장 대중적으로 쓰인다는 유사도 측정 알고리듬인 리벤슈타인 편집 거리를 사용해서 작성하게 된 것이다.

간단하게 적용해 본 결과 결과는 만족스러운 편이었다. 다만 지난 번에 '대충' 만든 것과 정확하게 비교하기는 어려웠는데 심지어 일부 사례에서는 지난 번에 정규식을 사용해서 만든 버전이 조금 더 나은 결과를 보여주는 듯도 했다. (당황스러웠다)

지난 번 코드와 이번에 작성한 코드의 가장 큰 차이점 중 하나는 정규식 사용 여부이다. 이번에는 정규식을 사용하지 않고 작성해보았다. 사실 이 라이브러리를 처음 시작할 때부터 학습 목적으로 다른 언어로 포팅할 생각도 있었다. 아마 곧 시작할 것 같은데 결과가 나오면 다시 공유하도록 하고 이번 작업의 소개는 여기서 마친다.

코드쓰는사람