검색 엔진은 어떻게 대소문자 구분 없이 검색할까?

"같은 문자"란 무엇인가?

검색 엔진을 만들다 보면 "같은 문자"라는 개념이 생각보다 단순하지 않다는 사실을 깨닫게 된다.

사용자가 `cafe`를 검색했을 때 `café`가 포함된 문서도 찾아야 할까? 대부분의 경우 그래야 한다. `ＡＢＣ`(전각 문자)를 검색했을 때 `ABC`(반각 문자)가 포함된 문서도 나와야 할까? 당연히 그래야 한다. 그렇다면 `①`을 검색했을 때 `1`이 포함된 문서는? `fi`(fi ligature)를 검색했을 때 `fi`가 포함된 문서는?

여기서 전각(full-width) 문자란 한글이나 한자처럼 가로폭을 넓게 차지하는 문자 칸에 맞춰 넓게 만든 영숫자·기호를 말하고, 반각(half-width) 문자란 우리가 일상적으로 쓰는 일반 영숫자(`ABC`, `123`)를 말한다. 일본어·한국어 입력 환경에서 전각 모드로 영문을 입력하면 `Ａ`처럼 넓은 형태로 저장되는데, 눈으로 보기에는 `A`와 거의 같지만 유니코드상 완전히 다른 코드 포인트다.

이 질문들에 답하려면 유니코드 정규화(Unicode Normalization)를 이해해야 한다. 이 글에서는 유니코드 정규화의 네 가지 형태(NFC, NFD, NFKC, NFKD)를 설명하고, 검색 엔진에서 NFKC를 선택하는 것이 왜 합리적인지, 그리고 NFKC만으로는 부족한 부분을 어떻게 보완하는지를 다룬다.

유니코드 기초

(1) 코드 포인트

유니코드는 세상의 모든 문자에 고유한 숫자를 부여한다. 이 숫자를 코드 포인트(code point)라고 부른다. `U+` 접두사와 16진수로 표기한다.

문제는 같은 글자인데 다른 코드포인트를 가지는 경우가 있다.

`é`라는 글자를 유니코드로 표현하는 방법은 두 가지다.

화면에는 둘 다 `é`로 표시된다. 그러나 바이트 수준에서는 완전히 다른 데이터다. 바이트 비교로는 이 둘을 같다고 판단할 수 없다.

이것이 정규화(normalization)가 필요한 이유다.

(2) 그래핌 클러스터: 사용자가 보는 "한 글자"

코드 포인트와 사용자가 인식하는 "한 글자"는 같지 않다. 유니코드에서는 사용자가 인식하는 최소 문자 단위를 확장 그래핌 클러스터(extended grapheme cluster)라고 정의한다. UAX #29에서의 정의는 다음과 같다.

"An extended grapheme cluster is the same as a legacy grapheme cluster, with the addition of some other characters. ... A legacy grapheme cluster is a base (such as A or カ) followed by zero or more continuing characters"

하나의 코드 포인트가 한 글자인 경우가 대부분이지만, 여러 코드 포인트가 하나의 글자를 구성하는 경우도 빈번하다.

검색 엔진에서 이것이 중요한 이유는 텍스트 자르기, 하이라이팅, 문자 수 계산 때문이다. 검색 결과에서 매칭된 부분을 하이라이팅할 때 그래핌 클러스터 중간을 자르면 깨진 문자가 표시된다. 텍스트 처리는 반드시 그래핌 클러스터 단위로 해야 안전하다.

유니코드 정규화

유니코드 정규화에는 네 가지 형태가 있다. 두 가지 축의 조합으로 이해하면 된다.

• 정규(Canonical) vs 호환(Compatibility)
• 분해(Decomposition) vs 합성(Composition)

NFC/NFD는 정규 동치만 처리하므로 ligature(`fi`), 전각 문자(`Ａ`), 원문자(`②`) 등은 그대로 유지된다. NFKC/NFKD는 이런 호환 문자들까지 통일한다.

(1) NFC

정규 분해를 수행한 뒤, 다시 재합성하여 가장 압축된 정규 형태를 만든다.

e (U+0065) + ́ (U+0301)  →  é (U+00E9)

NFC는 W3C가 웹 콘텐츠에 권장하는 기본 정규화 형태다.

The W3C Character Model for the World Wide Web 1.0: Normalization and other W3C Specifications (such as XML 1.0 5th Edition) recommend using Normalization Form C for all content

대부분의 텍스트 데이터는 이미 NFC로 저장되어 있을 가능성이 높다. NFC는 원본 텍스트의 의미를 가장 잘 보존하면서도, 동일한 문자의 서로 다른 정규 표현을 하나로 통일한다.

(2) NFD

합성 문자를 기본 문자와 결합 문자(combining character)로 분해한다.

é (U+00E9)  →  e (U+0065) + ́ (U+0301)

NFD 자체를 최종 형태로 사용하는 경우는 드물지만, 악센트 제거(accent stripping) 같은 내부 처리의 중간 단계로 유용하다. NFD로 분해한 뒤 결합 문자를 제거하면 악센트 없는 기본 문자만 남길 수 있다.

(3) NFKC

호환 분해를 수행한 뒤, 정규 합성을 적용한다. 수학적으로 표현하면 NFKC(text) = NFC(NFKD(text))이다.

호환 분해란, 정규 동치(canonical equivalence)뿐 아니라 호환 동치(compatibility equivalence)까지 고려하여 분해하는 것이다. 의미적으로 유사하지만 시각적으로 다른 문자들을 하나로 통일한다.

fi (ligature)  →  fi
Ａ (전각 A)    →  A (반각 A)
② (원문자 2)   →  2

NFKC는 NFC보다 공격적으로 문자를 통일한다. 검색 엔진에서 가장 많이 사용되는 정규화 형태다.

NFKD

가장 완전한 분해를 수행한다. NFKC의 합성 전 단계에 해당한다.

fi (ligature) →  fi
é (U+00E9)   →  e (U+0065) + ́ (U+0301)

NFKD는 호환 분해와 정규 분해를 모두 적용하므로, 결합 문자가 분리된 상태로 남는다.

NFKC/NFKD 적용 시 주의점

NFKC/NFKD는 강력하지만, UAX #15는 맹목적인 적용을 경고한다.

UAX #15

"Normalization Forms KC and KD must not be blindly applied to arbitrary text. Because they erase many formatting distinctions, they will prevent round-trip conversion to and from many legacy character sets, and unless supplanted by formatting markup, they may remove distinctions that are important to the semantics of the text."

"It is best to think of these Normalization Forms as being like uppercase or lowercase mappings: useful in certain contexts for identifying core meanings, but also performing modifications to the text that may not always be appropriate."

호환 동치(compatibility equivalence)의 정의 자체가 이를 잘 보여준다.

"Compatibility equivalence is a weaker type of equivalence between characters or sequences of characters which represent the same abstract character, but which may have distinct visual appearances or behaviors."

구체적으로 어떤 변환이 일어나는지, 카테고리별로 살펴보자.

원문자/괄호문자 → 숫자/문자

원문자와 일반 문자의 구분이 사라진다.

위첨자/아래첨자 → 일반 숫자/문자

분수 → 숫자+슬래시

문자열 길이가 변하기 때문에, 오프셋 기반 인덱싱을 하는 경우 원본 텍스트와의 위치 매핑에 주의해야 한다. `1½`이 `11⁄2`로 변환되면서 혼동이 생길 수도 있다.

로마 숫자 → 알파벳

단일 코드 포인트 로마 숫자가 여러 개의 알파벳으로 분해된다.

일본어 합자/단위 문자

일본어에서 특히 많은 호환 문자가 존재한다. 단위, 연호, 회사 표기 등이 한 글자로 인코딩되어 있는데, NFKC는 이를 모두 풀어쓴다.

ligature 분해

ligature는 두 개 이상의 문자가 합쳐진 글자의 모양이며, 일반 텍스트에서는 분리된 형태와 동일하게 취급하는 것이 합리적이다.

전각 구두점 → 반각 구두점

보안 관점에서 전각 구두점의 정규화는 중요하다. 입력 검증(validation)을 전각 문자로 우회하는 공격을 방지하려면, 검증 전에 NFKC 정규화를 적용해야 한다.

검색 엔진은 NFKC 사용이 고려될 수 있다

앞서 살펴본 것처럼 NFKC는 상당히 공격적인 정규화다. `E=mc²`가 `E=mc2`가 되고, `½`이 `1⁄2`가 된다. 그럼에도 검색 엔진에서 NFKC를 정규화 방식으로 고려할 이유가 있다.

(1) 일부 어플리케이션은 Recall이 Precision보다 중요하다

검색의 품질은 재현율(recall)과 정밀도(precision)로 평가될 수 있다.통합 검색처럼 재현율과 정밀도 둘 다 중요한 도메인도 있지만, 재현율이 훨씬 중요한 검색 도메인도 존재한다.

• Recall 실패: 사용자가 원하는 문서를 못 찾는 것
• Precision 저하: 의도하지 않은 문서가 함께 나오는 것

사용자가 `cafe`를 검색했을 때 `café`가 포함된 문서가 누락되면 사용자는 "검색이 안 된다"고 느낀다. 반면 `②`를 검색했을 때 `2`가 포함된 문서가 함께 나오더라도, 원하는 결과가 포함되어 있기만 하면 크게 불편하지 않다.
특히 메일·메시지 검색처럼 날짜순 정렬이 기본인 검색에서는, 원하는 결과가 목록에 포함되기만 하면 된다. 랭킹 품질보다 누락 여부가 훨씬 중요하다.

(2) 실제 불편 빈도는 낮다

NFKC의 공격적인 정규화가 실제로 사용자에게 불편을 주는 빈도를 생각해 보자.

• `②`를 검색했는데 `2`가 포함된 문서도 나오는 상황이 실제로 얼마나 자주 문제가 되는가?
• 위첨자 `²`를 정확히 구분해서 검색해야 하는 사용자가 얼마나 되는가?

대부분의 사용자에게 이런 구분은 중요하지 않다. 특수 문자 정규화로 인한 불편은 드문 현상이며, 반대로 정규화를 하지 않아서 검색이 안 되는 불편은 훨씬 빈번하다.

(3) 유지 보수 비용

NFKC 대신 "필요한 것만 골라서" 정규화하는 방식을 생각해 볼 수 있다. 예를 들어 전각→반각 변환은 하되, 위첨자→일반 문자 변환은 하지 않는 식이다. 그러나 이 접근은 유지보수가 매우 어렵다.

• 직접 유니코드 매핑을 작성하면, 유니코드 버전이 올라갈 때마다 새로운 문자에 대한 매핑을 추가해야 한다
• 정규화 옵션 조합이 늘어날수록 매핑 복잡도가 기하급수적으로 증가한다
• 표준 라이브러리가 이미 유니코드 표준에 맞춰 NFKC를 구현하고 있다

실무에서 가장 널리 쓰이는 검색 엔진인 Elasticsearch도 기본 정규화로 `nfkc_cf`(NFKC + Case Folding)를 사용한다.

NFKC를 넘어서: 검색 엔진에 필요한 추가 정규화

NFKC가 많은 문제를 해결하지만, 검색 엔진에서는 NFKC만으로 부족한 영역이 있다.

(1) 대소문자 변환 (Case Folding)

사용자가 `Hello`를 검색하면 `hello`, `HELLO`가 포함된 문서도 찾아야 한다. NFKC는 대소문자 변환을 하지 않으므로, 별도의 Case Folding이 필요하다.

단순히 알파벳 대소문자 변환뿐만 아니라 언어별로 유의해야 할 사항이 있다. 예를 들어 독일어 `ß` → `ss` 변환 처럼 문자열 길이가 변하거나 그리스어 대문자 시그마 `Σ` 처럼 소문자가 두 개인 경우가 있다.

(2) 악센트/발음 구별 부호 제거 (Accent Folding)

`cafe`로 `café`를 찾으려면 악센트를 제거해야 한다. NFKC는 악센트를 보존하므로, 악센트 제거는 별도로 처리해야 한다.

보통 다음의 방식으로 악센트를 제거한다.

1. NFD (또는 NFKD)로 분해: `é` → `e` + `́` (U+0065 + U+0301)
2. Combining Diacritical Marks(U+0300–U+036F) 범위의 코드 포인트를 제거: `e`만 남음
3. NFC로 재합성

언어에 따라 악센트 여부에 따라 아예 별개의 문자로 취급되는 경우도 있으므로 언어에 따라 악센트 제거를 선택적으로 적용하거나, 제외할 문자를 설정할 수 있어야 한다.

(3) 가타카나 <-> 히라가나 변환

일본어 검색에서는 `カタカナ`(가타카나)와 `かたかな`(히라가나)를 동일하게 취급해야 하는 경우가 많다. 유니코드 정규화(NFKC 포함)로는 가타카나와 히라가나 간 변환이 불가하다. 별도의 변환 로직이 필요하다.

다행히 히라가나와 가타카나의 코드 포인트 차이가 0x60으로 일정하기 때문에, 단순 산술 연산으로 변환할 수 있다.

カ (U+30AB) - 0x60 = か (U+304B)

참고로, 반각 가타카나 → 전각 가타카나 변환은 NFKC가 처리한다.

ｶ (반각, U+FF76) → カ (전각, U+30AB)

탁점(dakuten) 처리에도 주의가 필요하다. NFKC는 반각 가타카나 + 반각 탁점의 조합을 전각 탁음 가타카나로 합성하지만, 비표준적인 조합(예: 전각 가타카나 + 반각 탁점)은 분리된 채로 남을 수 있다.

정규화 파이프라인

검색 엔진에서 텍스트 정규화를 적용하는 순서는 결과에 영향을 준다. 다음은 실제 검색엔진에서 사용할 수 있는 파이프라인 예시.

원본 텍스트
  │
  ▼
① Accent/Diacritic 제거 (NFKD → accent 제거 → NFC)
  │
  ▼
② NFKC 적용 (①을 적용하지 않는 경우. NFKC = NFC(NFKD))
  │
  ▼
③ Case Folding (대문자 → 소문자)
  │
  ▼
④ 스크립트별 정규화 (가타카나 → 히라가나 등)
  │
  ▼
정규화된 텍스트

Accent 제거는 NFKC 이전에 해야 한다. 그 이유는 NFKC의 동작 원리에 있다.

NFKC = NFC(NFKD(text))이다. NFKD 단계에서 `é`(U+00E9)가 `e`(U+0065) + `́`(U+0301)로 분해되지만, NFC 단계에서 다시 `é`(U+00E9)로 합성된다. 즉 NFKC 적용 후에는 악센트가 합성된 상태이므로, 이후에 악센트를 제거하려면 다시 NFD로 분해해야 한다.

Accent 제거가 필요한 경우, 처음부터 NFKD로 분해 → accent 제거 → NFC 합성 순서로 처리하면 한 번의 분해/합성으로 끝난다. NFKD를 사용하므로 호환 분해도 함께 수행되어, 별도의 NFKC 적용이 불필요하다.

Accent 제거가 필요 없는 경우에는 ②에서 NFKC만 적용하면 된다.

인덱싱과 쿼리 정규화

정규화는 인덱싱 시점과 검색 시점 모두에 적용해야 한다.

• 인덱싱 시점: 문서를 인덱스에 저장할 때 정규화 적용. 정규화된 형태로 인덱스에 저장됨
• 검색 시점: 사용자 쿼리에 동일한 정규화 적용. 정규화된 쿼리로 인덱스를 검색

두 시점에 동일한 정규화 파이프라인을 적용해야 한다. 인덱싱 시에는 NFKC를 적용하고 검색 시에는 NFC만 적용하면, 전각 문자로 입력한 쿼리가 반각 문자로 인덱싱된 문서를 찾지 못한다.

Elasticsearch 사례

실무 참고를 위해, Elasticsearch가 제공하는 유니코드 정규화 관련 도구를 살펴보자.

ICU Normalization Token Filter

ICU 플러그인이 제공하는 토큰 필터로, 다음 정규화 형태를 지원한다.

기본값이 `nfkc_cf`라는 점이 주목할 만하다. Elasticsearch는 검색 엔진의 기본 정규화로 NFKC에 Case Folding까지 결합한 형태를 선택했다.

`unicode_set_filter` 파라미터를 사용하면 특정 문자를 정규화 대상에서 제외할 수 있다. 예를 들어 독일어 `ß`를 `ss`로 변환하고 싶지 않다면 `"unicode_set_filter": "[^ß]"`로 설정한다.

ICU Folding Token Filter

UTR#30(Character Foldings)에 기반하여 다음을 한 번에 처리한다.

• Unicode normalization (NFKC)
• Case folding
• Accent/diacritic 제거
• 추가 folding (width folding, kana folding 등)

마찬가지로 `unicode_set_filter`로 특정 문자를 folding에서 제외할 수 있다.

UTR#30이란?
검색 엔진을 위한 문자 folding을 정의한 기술 보고서다.
case folding, diacritic 제거, width folding, kana folding, 위첨자/아래첨자 folding 등 25가지 이상의 folding 연산을 정의한다.

Proposed Draft 상태에서 철회(withdrawn)되었지만, Lucene/Elasticsearch가 구현체로 채택하여 실질적인 표준 역할을 하고 있다.

검색 엔진을 직접 구현한다면 UTR#30의 folding 목록을 참고하여 어떤 정규화가 필요한지 판단하는 것이 도움이 된다.

마무리

검색 엔진에서 precision과 recall은 둘 다 중요하다. 다만 NFKC의 공격적인 정규화로 인해 잃는 precision보다, 정규화를 하지 않아서 놓치는 recall의 손실이 훨씬 크다. `②`를 검색했을 때 `2`가 함께 나오는 정도의 precision 저하는 감수할 수 있지만, `café`를 `cafe`로 검색했을 때 아예 결과가 나오지 않는 것은 치명적이다.

다만 그 한계를 인지해야 한다. NFKC만으로는 대소문자 통일, 악센트 제거, 히라가나 변환이 안 된다. 필요에 따라 추가 정규화를 조합하되, 적용 순서에 주의해야 한다.

Reference

• UAX #15: Unicode Normalization Forms
• UAX #29: Unicode Text Segmentation
• UTR #30: Character Foldings (Draft)
• ICU Normalization Documentation