메아리 저널

유니코드 정규화 알고리즘 간략한 정리

내 기억이 녹슬지 않았다는 걸 증명하기 위해 (그리고 나중에 까먹었을 때 다시 기억하기 쉽도록) 여기에 대강 정리해 놓는다. 좀 더 그럴듯한 설명은 UAX #15을 참고하시길 바란다.

유니코드 정규화 알고리즘

유니코드 정규화 알고리즘은 유니코드로 쓰여진 문자열을 적절한 방법으로 변환하는 알고리즘이다. 이런 알고리즘은 유니코드의 특성 때문에 필요한데,

  • 유니코드에는 미리 합쳐진(precomposed) 문자와 따로 결합하는(combining) 문자가 공존하고 있다. 한글 자모 영역(말하자면 ㄱㅏᆼ)과 한글 음절 영역(말하자면 )을 생각하면 간단할 것이다.
  • 이들 문자열을 정규화 없이 그대로 비교하거나 처리할 경우 자잘한 버그부터 시작해서 보안 문제로까지 연결될 수 있다.

정규화 알고리즘은 최대한 풀어 쓰는 분해 알고리즘과 최대한 합쳐 쓰는 결합 알고리즘으로 나뉘며, 각각의 알고리즘은 기존 인코딩들과의 이런 저런 호환성을 위해 사용되는 호환 매핑을 따로 가지고 있다. 따라서 총 네 가지의 알고리즘—NFC(결합), NFKC(호환 결합), NFD(분해), NFKD(호환 분해)—이 존재한다. 호환 매핑과 일반 매핑 사이의 차이는 테이블 빼고는 별로 없다고 봐도 좋으니 그냥 대강 살아도 된다.

유니코드 문자 데이터베이스

유니코드 문자 데이터베이스(UCD)는 문자들에 대한 정보, 예를 들어서 문자가 어떤 종류이고 다른 문자랑 어떻게 달라 붙는다거나 오른쪽에서 왼쪽으로 흘러 간다거나 하는 것들을 기계적으로 서술한 것이다.

유니코드 정규화 알고리즘은 UCD를 이런 저런 용도로 많이 활용한다. 현재 최신 버전은 http://www.unicode.org/Public/UNIDATA/에 있으며, 다음과 같은 파일들이 필요하다.

  • UnicodeData.txt는 각 문자에 대한 기본적인 정보를 담고 있다. 각 필드는 세미콜론으로 구분되어 있으며, 세번째 칸에 있는 Canonical_Combining_Class 필드와, 다섯번째 칸에 있는 Decomposition_TypeDecomposition_Mapping 필드가 실제로 필요한 것이다.
  • CompositionExclusions.txt는 결합 알고리즘에서 제외되는 매핑들의 목록을 담고 있다. 원래 결합 매핑과 분해 매핑은 서로 역변환 관계에 있지만, 이런 저런 이유로 결합 매핑에 포함되지 않아야 하는 것들이 있기 때문이다. (참고로 이 목록에는 UCD에서 따로 계산할 수 있다는 이유로 주석 처리된 목록이 꽤 있는데, DerivedNormalizationProps.txt에는 이런 경우도 모두 처리한 목록이 있다.)

언제나 그렇지만 UCD로부터 실제로 프로그램에 사용할 수 있는 형태로 데이터를 가공하는 것은 각자의 몫이다. 다행히도 UCD는 이런 의미에서는 비교적 친절하게 만들어진 편이다.

분해 알고리즘

NFC/NFKC는 NFD/NFKD로부터 나온 결과를 후처리하는 방식으로 구현된다. 그러니 분해 알고리즘을 먼저 설명하는 것이 나을 듯 하다.

알고리즘을 설명하기 전에 유니코드 문자의 결합 클래스(combining class) 속성에 대한 이해가 필요하다. 결합 클래스는 쉽게 말하면 어떤 문자가 다른 문자에 달라 붙는지, 그리고 달라 붙는다면 얼마나 먼저 달라 붙는지 순서를 정해 주는 역할을 한다. 결합 클래스는 0부터 255까지의 숫자이며, 0은 결합하지 않는 문자이고 나머지 숫자는 작을수록 빨리 결합함을 의미한다.

만약 우리가 적절한 문자열을 분해 알고리즘으로 돌린다면 각 문자들의 결합 클래스는 다음과 같이 나올 것이다.

0 0 10 100 100 101 200 0 40 0 80 90 0 0
^ \__________________/ \__/ \_____/ ^ ^

위의 경우 결합 클래스가 0인 문자는 여섯 개이며, 따라서 렌더링 엔진은 이를 여섯 개의 문자 및 결합하는 이것 저것들로 출력해 낼 것이다. UAX #15에서는 이런 결합 클래스가 0인 문자들을 starter라고 통칭하고 있다.

NFD/NFKD는 먼저 각 문자들을 모조리 분해 매핑에 집어 넣어서 최대한 재귀적으로 확장시킨다. (왜 쓸데 없이 미리 재귀적으로 분해시켜 두지 않는지에 대해서는 뒤에서 설명한다.) 이 분해 매핑은 위에서 언급한 Decomposition_Mapping 필드에 해당하는데, 이 필드가 있다고 해도 Decomposition_Type 필드가 나타나면 호환 매핑이기 때문에 NFD에서는 무시해야 한다.

이제 이렇게 확장된 문자열을 결합 클래스 순서대로 정렬을 한다. UAX #15에서는 이 순서를 canonical ordering이라고 기술하고 열심히 설명을 하는데, 위에서 봤겠지만 이 순서라는 게 그냥 말 그대로 두 starter 사이에서 결합 클래스의 오름차순으로 정렬하라는 얘기다. 다만 결합 클래스가 같은 문자가 둘 이상이라면, 그 문자들의 상대적인 위치는 정렬 후에도 바뀌면 안 된다. 왜냐하면 결합 클래스는 보통 결합 문자가 어느 위치에 붙는지를 서술하기 때문에, 결합 문자가 붙는 순서가 달라지면 다른 문자가 될 가능성이 많기 때문이다. (만약 항상 다른 결합 문자보다 나중에 붙어야 하는 문자가 있다면 그 문자는 더 큰 결합 클래스를 받게 된다.)

세 줄 요약.

  1. 각 문자들을 분해 매핑에 집어 넣어서 재귀적으로 확장시킨다. NFKD의 경우 호환 매핑도 고려한다.
  2. 각 문자들을 결합 클래스가 0인 비결합 문자들을 중심으로 나눈다.
  3. 서로 나눠진 부분에서 결합 클래스의 오름차순으로 문자를 정렬한다. 다만 같은 결합 클래스의 경우 상대적인 순서는 유지되어야 한다. 다른 말로 하면 버블 정렬 같은 안정 정렬(stable sort)을 써야 한다는 소리다.

결합 알고리즘

NFC/NFKC는 일단 NFD/NFKD로 변환된 문자열을 최대한 다시 합치는 과정으로 구성된다. 미리 분해 알고리즘으로 처리를 해 뒀다는 얘기는 결합을 고려할 때 체크해야 할 갯수가 기하급수적이 아니라 산술급수적으로만 증가한다는 얘기가 되겠다. (분해 알고리즘이 미리 정렬을 하기 때문에…)

NFC/NFKC의 결합 과정은 똑같다. 즉, 호환 매핑은 고려에 들어 가지도 않는다. 좀 이상해 보이기는 하지만 유니코드 입장에서는 하위 호환성이 중요하지 상위 호환성이 중요한 건 아니기 때문에 그다지 신경을 많이 쓰지 않아서 그런 것 같다. 그리고 호환 매핑은 별 희한한 것들이 다 있어서 실제로 역변환을 구현하기도 힘들기도 하다.

뭐 하여간, 결합 알고리즘은 다음 그림으로 아주 쉽게 설명할 수 있다. (UAX #15가 유일하게 명쾌하게 해설한 부분이다.)

위에는 분해 전의 문자열이 표시되어 있고, 아래에는 분해 후의 문자열이 표시되어 있다. 분해 후의 문자열에는 결합을 위해 체크해야 하는 문자 쌍들이 화살표로 연결되어 있다.

설명을 쉽게 하기 위해서 대문자는 비결합 문자(결합 클래스가 0), 소문자는 결합 문자라고 하자. 분해 알고리즘을 거친 문자열 AbcDefgHIj에서 체크해야 할 문자 쌍들은 순서대로 Ab, Ac, De, Df, …, HI, Ij 순서가 되겠다. 즉, 비결합 문자와 그 뒤에 따라 붙는 결합 문자들끼리 먼저 시도해 보고, 만약 그 비결합 문자 바로 뒤에 비결합 문자가 나온다면 그것도 결합을 시도해 보는 것이다. (두번째 경우, 두 비결합 문자는 항상 붙어 있어야 한다. 왜 그런지는 별도의 문서에 잘 설명되어 있다.)

결합을 시도했을 때 결합이 가능하면 비결합 문자는 목록에서 사라지고 결합 문자는 합쳐진 문자로 치환된다. 그리고 다음 문자를 계속 체크해 나간다. (합쳐진 새 결합 문자부터 시작하는 것이 아니다.) 위의 예시에서 Ac가 새로운 결합 문자 X로 치환될 수 있다면, 문자열은 XbDefgHIj로 바뀌지만 Ab가 이미 실패했기 때문에 Xb는 건너 뛰고 De를 체크하게 된다. (XD는 중간에 b가 끼어 있으므로 체크하지 않는다.)

결합 매핑은 호환 매핑을 포함하지 않는다고 했는데, 사실 일반 분해 매핑은 거의 대부분 두 글자라서 이런 결합이 가능하다. (분해 매핑이 재귀적으로 확장한 결과가 아닌 이유가 바로 이것이다.) 다만 어쩌다가 한 글자라거나(singleton) 하는 특수한 경우가 있는데 이런 경우는 물론 결합 매핑에서 빼야 하고, 그 중 일부는 목록이 주어져 있다.

세 줄 요약.

  1. 일단 NFD/NFKD를 거쳐서 모조리 분해한다.
  2. 가능한 모든 비결합 문자와 뒤에 따르는 결합 문자, 그리고 그 뒤에 오는 첫번째 비결합 문자에 대해서 위치 순서대로 결합을 시도한다. 결합이 성공하면 뒤의 문자는 지우고 앞의 문자를 결합된 문자로 바꾼다. 결합이 성공하더라도 이미 이전에 실패한 결합은 다시 시도하지 않는다.
  3. 결합을 시도할 때는 일반 분해 매핑의 역변환만을 사용한다. 물론 예외는 있다.

제대로 쓴건진 모르겠는데 일단 내가 알고 있는 건 이게 끝이다. 다만, 한글 처리에 대해서 주의할 점은, 한글 음절 영역은 워낙 미리 결합된 문자가 많아서 따로 UCD에 내용이 들어 있는 게 아니라 별도의 알고리즘을 사용할 필요가 있다는 점. (같은 이유로 한글 영역은 유니코드 처리에 있어서 알고리즘 단에서 처리해야 하는 부분이 꽤 많다.)

이 글은 본래 http://mearie.org/journal/2008/04/brief-note-on-unicode-normalization-algorithm에 썼던 것을 옮겨 온 것입니다.


(rev 797ba6fb3720)