CJK 바이그램 토크나이저가 9개 언어 검색을 구동하는 방법

이 블로그는 9개 언어로 포스트를 제공하며, 모든 포스트에 제목 검색 기능이 필요합니다. 영어 제목은 공백을 기준으로 문제없이 분리됩니다. 한국어, 중국어, 일본어 제목은 단어 사이에 공백을 두지 않고 쓰기 때문에 공백으로 분리되지 않습니다. 하나의 검색창에서 이 두 가지 경우를 모두 처리해야 합니다. 이를 해결한 방법은 바이그램(bigram) 토크나이저입니다. CJK 텍스트의 경우 겹치는 두 글자 단위로 인덱싱하고, 라틴(Latin) 텍스트의 경우 전체 단어를 유지합니다. 이 포스트에서는 왜 공백 분리가 작동하지 않는지, 바이그램 토크나이저를 어떻게 구축하는지, 그리고 언제 더 무거운 형태소 분석기가 필요한지에 대해 살펴봅니다.

CJK 텍스트에서 공백 기준 분할이 실패하는 이유

토크나이저(tokenizer)는 문자열을 인덱싱하고 검색할 단위로 변환합니다. 대부분의 데이터베이스에서 기본 토크나이저는 공백과 구두점을 기준으로 분할합니다. 영어의 경우, 이는 단어가 어디에서 시작하고 끝나는지에 대한 합리적인 모델입니다. "cursor pagination in firestore"라는 제목은 네 개의 토큰이 되며, "pagination"을 검색하면 해당 제목을 찾을 수 있습니다.

한국어, 중국어, 일본어는 단어 사이에 공백을 넣지 않습니다. "전세보증금월세"와 같은 한국어 구문은 읽는 사람이 여러 개념으로 분석하더라도 끊어지지 않는 하나의 연속된 문자로 작성됩니다. 공백 토크나이저는 이 전체 문자열을 단일 토큰으로 봅니다. 일치하는 유일한 쿼리는 글자 하나하나 정확히 일치하는 전체 문자열뿐입니다. "월세"만 단독으로 검색하면 아무것도 찾을 수 없습니다. 왜냐하면 "월세"는 토큰이 아니고 "전세보증금월세"가 토큰이기 때문입니다.

따라서 영어에 효과적인 동일한 토크나이저는 CJK 텍스트에 대해서는 하나의 거대하고 쓸모없는 토큰을 생성합니다. 하나의 전략을 선택해서 모든 곳에 적용할 수는 없습니다. 토크나이저는 텍스트를 보고 문자 단위로 어떤 규칙을 적용할지 결정해야 합니다.

바이그램: 두 글자씩 겹치는 창

바이그램 토크나이저의 기본 개념은 CJK 텍스트에서 단어 경계를 찾으려는 시도를 중단하고 대신 인접한 모든 글자 쌍을 인덱싱하는 것입니다. "전세보증금"에 두 글자 창을 슬라이딩해 보겠습니다.

다섯 글자는 네 개의 바이그램을 생성합니다. 창은 한 글자씩 겹치며, 이 부분이 검색이 작동하게 만드는 요소입니다. "보증"이 이제 그 자체로 토큰이므로 "보증"에 대한 쿼리가 일치합니다. "전세"도 마찬가지이며, 전체 "전세보증금"도 동일한 네 개의 바이그램으로 확장되어 모든 바이그램이 존재할 때 일치합니다.

절대 어겨서는 안 되는 한 가지 규칙은 인덱싱과 쿼리에 정확히 동일한 토크나이저를 사용해야 한다는 것입니다. 만약 인덱스는 바이그램을 저장하지만 쿼리는 공백 토크나이저를 통과한다면, 쿼리 토큰 "전세보증금"은 저장된 어떤 바이그램과도 일치하지 않으므로 검색 결과는 아무것도 반환하지 않습니다. 이것이 바이그램 검색이 조용히 실패하는 가장 흔한 방식입니다. 문서도 있고 토큰도 있지만, 양측이 문자열을 자르는 방법에 대해 동의하지 않기 때문에 모든 쿼리가 빈 결과를 반환합니다. 두 경로 모두 하나의 함수를 통과하도록 라우팅하면 이러한 종류의 버그는 사라집니다.

라틴어 텍스트는 바이그램 경로를 거치지 않습니다. "firestore"를 "fi", "ir", "re" 등으로 나누면 인덱스가 비대해지고 의미 없는 조각에 일치하게 됩니다. 공백으로 이미 단어 경계를 표시하는 스크립트의 경우, 전체 단어가 올바른 단위입니다.

유니코드 블록으로 문자별 스크립트 감지

두 전략을 한 번에 혼합하기 위해 토크나이저는 각 문자를 유니코드 블록으로 분류합니다. 문자는 고정된 숫자 범위에 있으며 CJK 스크립트는 알려진 블록을 차지합니다. 작은 함수가 룬이 바이그램 경로에 속하는지 여부를 결정합니다.

func isCJK(r rune) bool {
	switch {
	case r >= 0x4E00 && r <= 0x9FFF: // CJK Unified Ideographs
		return true
	case r >= 0x3400 && r <= 0x4DBF: // CJK Extension A
		return true
	case r >= 0xAC00 && r <= 0xD7A3: // Hangul syllables
		return true
	case r >= 0x3040 && r <= 0x309F: // Hiragana
		return true
	case r >= 0x30A0 && r <= 0x30FF: // Katakana
		return true
	}
	return false
}

한글은 한국어를, 표의 문자 블록은 중국어와 일본어의 한자를, 가나 블록은 나머지 일본어를 다룹니다. 라틴 문자, 숫자, 태국어, 힌디어, 베트남어를 포함하여 이 범위 밖의 모든 것은 단어 경로를 사용합니다. 베트남어는 분음 부호가 있는 라틴 스크립트로 작성되고 단어를 공백으로 구분하므로 지리적으로는 CJK 인접 언어이지만 여기서는 영어처럼 작동합니다.

토크나이저는 문자열을 룬 단위로 탐색하며 라틴 문자는 현재 단어로, CJK 문자는 현재 버퍼로 수집합니다. 경계, 공백, 구두점 또는 한 스크립트에서 다른 스크립트로 전환될 때 가지고 있는 것을 플러시합니다.

func Tokenize(s string) []string {
	s = strings.ToLower(norm.NFKC.String(s))

	var tokens []string
	var latin, cjk []rune

	flushLatin := func() {
		if len(latin) > 0 {
			tokens = append(tokens, string(latin))
			latin = latin[:0]
		}
	}
	flushCJK := func() {
		tokens = append(tokens, bigrams(cjk)...)
		cjk = cjk[:0]
	}

	for _, r := range s {
		switch {
		case isCJK(r):
			flushLatin()
			cjk = append(cjk, r)
		case unicode.IsLetter(r) || unicode.IsDigit(r):
			flushCJK()
			latin = append(latin, r)
		default:
			flushLatin()
			flushCJK()
		}
	}
	flushLatin()
	flushCJK()
	return dedupe(tokens)
}

바이그램 헬퍼는 슬라이딩 윈도우를 처리하며, 실행이 한 문자로만 구성된 경우를 위한 폴백이 있습니다.

func bigrams(rs []rune) []string {
	if len(rs) == 0 {
		return nil
	}
	if len(rs) == 1 {
		return []string{string(rs)}
	}
	out := make([]string, 0, len(rs)-1)
	for i := 0; i+1 < len(rs); i++ {
		out = append(out, string(rs[i:i+2]))
	}
	return out
}

"Firestore 색인"과 같이 스크립트가 혼합된 제목은 라틴 토큰 "firestore"와 한국어 부분의 바이그램 "색인"을 생성합니다. 둘 다 동일한 토큰 목록에 들어가며, 어느 언어로 검색하든 해당 게시물을 찾을 수 있습니다.

토큰화 전 정규화

독자에게 동일하게 보이는 두 문자열이 바이트 단위로는 다를 수 있습니다. 전각 라틴 문자 "Ａ"는 일반 "A"와 다른 코드 포인트입니다. 일부 악센트 문자는 단일 조합 코드 포인트로도 존재하고, 기본 문자 뒤에 결합 표시가 오는 형태로도 존재합니다. 인덱스가 한 가지 형태로 저장하고 쿼리가 다른 형태로 들어오면, 사람이 보기에는 같은 텍스트일지라도 일치하지 않습니다.

토크나이저는 먼저 NFKC로 정규화한 다음 소문자로 변환합니다. NFKC는 유니코드 정규화 형식 호환성 조합(Unicode normalization form compatibility composition)입니다. 이는 호환성 변형을 통합하므로 전각 문자는 해당하는 일반 문자로 축소되고, 기본 문자와 결합 시퀀스는 단일 코드 포인트가 있는 경우 단일 코드 포인트로 조합됩니다. 그 다음 소문자 변환은 라틴 스크립트에서 불일치의 원인이 되는 대소문자를 제거합니다.

import (
	"strings"

	"golang.org/x/text/unicode/norm"
)

func normalize(s string) string {
	return strings.ToLower(norm.NFKC.String(s))
}

토크나이저의 맨 위에서 이 작업을 한 번 수행하면 모든 후속 단계에서 정리된 텍스트를 보게 됩니다. 인덱싱과 쿼리 모두 동일한 토크나이저를 호출하므로, 양쪽 모두 동일한 정규화가 무료로 적용되고 양측이 일관성을 유지하게 됩니다.

$all을 사용한 토큰 저장 및 쿼리

각 게시물 문서는 제목에 대한 토크나이저의 출력을 담고 있는 title_tokens 배열을 가집니다. 인덱싱 시점에 토큰은 한 번 계산되어 게시물과 함께 기록됩니다:

doc := bson.M{
	"slug":         post.Slug,
	"lang":         post.Lang,
	"title":        post.Title,
	"title_tokens": Tokenize(post.Title),
}

title_tokens에 대한 다중 키 인덱스를 사용하면 데이터베이스가 배열의 모든 요소에 대해 일치시킬 수 있습니다. 검색은 들어오는 쿼리를 동일한 토크나이저를 통해 실행하고 토큰 배열에 모든 쿼리 토큰이 포함된 문서를 요청합니다:

func SearchFilter(query string) bson.M {
	tokens := Tokenize(query)
	if len(tokens) == 0 {
		return bson.M{}
	}
	return bson.M{
		"title_tokens": bson.M{"$all": tokens},
	}
}

$all 연산자는 모든 쿼리 토큰이 문서에 존재해야 하므로 토큰 간에 AND 연산을 수행합니다. CJK 쿼리의 경우, 이것이 부분 일치를 자연스럽게 느끼게 하는 요소입니다. "보증금"에 대한 검색은 바이그램 "보증"과 "증금"이 되며, 해당 하위 문자열을 포함하는 모든 제목은 토큰 배열에 두 바이그램을 모두 가지고 있으므로 일치합니다. "보증"은 포함하지만 "증금"은 포함하지 않는 제목은 일치하지 않는데, 이는 사용자가 더 긴 연속된 단어를 요청했기 때문에 원하는 동작입니다.

알아두어야 할 한 가지 예외적인 경우가 있습니다. 바이그램 중복은 원본 텍스트에서 순서가 맞지 않게 나타나는 토큰 시퀀스에 대한 일치를 생성할 수 있습니다. 왜냐하면 $all은 인접성이 아닌 존재 여부를 확인하기 때문입니다. 실제로 짧은 제목 검색의 경우 이는 드물고 무해합니다. 엄격한 인접성이 필요한 경우 위치를 저장하고 확인해야 하는데, 이는 제목 검색이 정당화하는 것보다 더 많은 인덱스와 쿼리 비용을 초래합니다.

트레이드오프: 인덱스 크기와 한 글자 쿼리

바이그램에는 비용이 듭니다. 첫 번째 비용은 인덱스 크기입니다. n개 문자로 된 CJK 제목은 n-1개의 토큰을 생성하며, 이 토큰들은 모두 멀티키 인덱스에 저장됩니다. 같은 제목에 대해 한두 개의 토큰을 생성할 수 있는 공백 토크나이저와 비교하면, 바이그램 인덱스는 몇 배 더 큽니다. 수천 개의 게시물에 대한 제목 검색에서는 절대적인 수치가 작습니다. 수백만 개의 문서에 대한 전체 본문 텍스트의 경우, 이것이 지배적인 비용이 될 것이며, 바이그램을 사용하기 전에 더 신중하게 생각해야 할 것입니다.

두 번째 비용은 한 글자 쿼리입니다. 단일 CJK 문자는 바이그램을 형성할 수 없으므로, 토크나이저는 이를 단독 토큰으로 내보내는 것으로 대체합니다. 이는 단일 문자도 인덱싱된 경우에만 작동하는데, 여기서는 bigrams 헬퍼의 동일한 한 글자 대체(fallback)를 통해 인덱싱됩니다. 하지만 단일 문자는 약한 쿼리입니다. 이는 많은 수의 문서와 일치하고 순위가 낮게 매겨지므로, 기술적으로는 행을 반환하더라도 결과는 거의 쓸모가 없습니다. 바이그램 검색은 두 글자 이상의 쿼리를 위해 만들어졌으며, 짧은 쿼리에서 가장 취약합니다.

두 비용 모두 제목 검색에 바이그램 사용을 피해야 할 이유는 아닙니다. 이들은 이 기술이 저렴하게 유지되는 경계를 알아야 할 이유입니다.

형태소 분석기가 더 나은 선택일 때

바이그램의 대안은 형태소 분석기입니다. 이는 실제로 언어를 이해하고 텍스트를 실제 단어로 분리하는 토크나이저입니다. 한국어의 경우, 이는 "전세보증금"이 복합어임을 알고 독자가 이해할 수 있는 부분으로 분리할 수 있는 도구를 의미합니다. 일본어의 경우, 이는 띄어쓰기 없이 한 단어가 어디서 끝나고 다음 단어가 어디서 시작하는지 인식하는 것을 의미합니다.

형태소 분석기는 모든 중복되는 쌍 대신 실제 단어를 내보내므로 더 깨끗하고 의미 있는 토큰과 더 작은 인덱스를 생성합니다. 비용 또한 현실적입니다. 각 언어는 자체 분석기와 자체 사전을 필요로 하며, 사전은 크고 언어 사용이 변화함에 따라 업데이트가 필요하며, 분석은 슬라이딩 윈도우 방식보다 문서당 부하가 더 큽니다. 이러한 방식으로 9개 언어를 지원한다는 것은 각각 고유한 특성과 실패 모드를 가진 여러 개의 개별 분석기를 통합하고 유지 관리하는 것을 의미합니다.

아래 표는 이러한 장단점을 한눈에 보여줍니다.

이 블로그의 경우 선택은 명확했습니다. 제목 검색은 작고 관대한 영역입니다. 사용자는 몇 글자를 입력하고 일치하는 게시물을 기대하며, 언어학적 분석을 하지는 않습니다. 바이그램은 언어 중립적인 단일 규칙, 언어별 사전 불필요, 9개 언어에 대해 동시에 최신 상태를 유지할 분석기가 없다는 점에서 이를 만족시킵니다. 만약 검색 영역이 기사 본문에 대한 순위가 매겨진 전문 검색으로 확장되어 단순성보다 토큰 품질과 인덱스 크기가 더 중요해진다면, CJK 언어를 위한 형태소 분석기는 그 비용의 가치를 할 것입니다. 문제의 크기에 맞는 토크나이저를 선택해야 하며, 제목 검색에는 바이그램이 적합한 크기입니다.