10장 압축 ② 허프만

자주 나오는 글자에 짧은 부호 쉽게

지금까지 본 대사는 글자마다 같은 길이였습니다. 2바이트 글자표라면 「の」도 「鬱」도 16비트입니다. 그런데 일본어 대본에서 「の」는 수천 번 나오고 어려운 한자는 몇 번 나오지 않습니다. 자주 나오는 글자에 짧은 부호를, 드문 글자에 긴 부호를 주면 전체가 짧아집니다. 모스 부호가 영어에서 가장 흔한 E를 점 하나(·)로 적는 것과 같은 생각입니다.

1952년 데이비드 허프만(David A. Huffman)은 글자마다 나온 횟수를 알 때 평균 길이가 가장 짧은 부호를 만드는 방법을 내놓았습니다. 이것이 허프만 부호입니다. 9장의 LZSS가 "앞에 나온 것을 다시 쓰기"로 줄인다면, 허프만 부호는 "글자마다 비트 수를 다르게 하기"로 줄입니다. 둘을 함께 쓰는 형식(ZIP의 DEFLATE 등)도 많습니다.

어떤 부호도 다른 부호의 앞부분이 아니다 쉽게

길이가 제각각인 부호를 빈틈없이 이어 붙이면 어디서 한 글자가 끝나는지 표시가 없습니다. 그래도 읽을 수 있으려면 조건이 하나 필요합니다. 어떤 부호도 다른 부호의 앞부분이 되면 안 됩니다. 이런 부호를 접두 부호(prefix code)라고 합니다.

왼쪽은 앞부분이 겹쳐 01을 두 가지로 읽을 수 있고, 오른쪽은 한 가지로만 읽힙니다.

접두 부호라면 앞에서부터 비트를 하나씩 붙여 가다가 부호표에 있는 꼴이 되는 순간 그것이 한 글자입니다. 더 긴 부호가 그 꼴로 시작할 수 없으니 기다릴 필요도, 되돌아갈 필요도 없습니다. 허프만 부호는 언제나 접두 부호입니다. 그 이유는 다음 절에서 만드는 트리의 모양에 있습니다.

가장 적은 둘을 묶어 트리 만들기 쉽게

허프만의 방법은 글자들을 트리로 묶는 것입니다. 트리는 맨 위의 한 점에서 갈림길이 아래로 두 갈래씩 뻗어 나가는 모양의 자료 구조입니다. 갈림길이나 끝 하나하나를 노드, 맨 위에서 시작하는 노드를 루트, 더 갈라지지 않는 끝 노드를 리프라고 합니다. 허프만 부호에서는 글자가 모두 리프에 있습니다.

만드는 순서는 단순합니다.

글자마다 나온 횟수를 셉니다. 이 횟수를 무게라고 합니다.
가장 가벼운 둘을 골라 하나로 묶습니다. 묶음의 무게는 둘의 합입니다.
하나만 남을 때까지 2를 되풀이합니다. 남은 하나가 루트입니다.
루트에서 글자까지 내려가며 한쪽 가지에 0, 다른 쪽에 1을 적습니다. 지나온 숫자를 이은 것이 그 글자의 부호입니다.

글자는 모두 리프에 있고, 한 리프로 가는 길이 다른 리프로 가는 길의 중간에서 끝나는 일은 없습니다. 그래서 어떤 부호도 다른 부호의 앞부분이 될 수 없습니다. 가벼운 것부터 묶었으니 드문 글자는 깊은 곳(긴 부호)에, 흔한 글자는 루트 가까이(짧은 부호)에 놓입니다.

문장

문장: 「간장 공장 공장장」

① 글자 세기와 부호

글자마다 나온 횟수와 부호
글자	횟수	부호	비트 수
간	1	`110`	1 × 3 = 3
장	4	`0`	4 × 1 = 4
␣	2	`111`	2 × 3 = 6
공	2	`10`	2 × 2 = 4

② 가장 가벼운 둘을 묶어 트리 만들기

위에서 내려가며 왼쪽 가지는 0, 오른쪽 가지는 1입니다. 루트에서 글자까지 지나는 숫자를 이으면 그 글자의 부호입니다.

③ 부호를 이어 붙인 비트열

110간0장111␣10공0장111␣10공0장0장

9글자가 17비트입니다. 글자마다 2바이트(16비트)로 적으면 144비트입니다.

④ 비트열을 한 비트씩 읽어 되돌리기

풀어 낸 글:

더 깊이최소라는 뜻, 같은 무게일 때, 부호 길이만 저장하는 정규 허프만 부호

무엇이 가장 짧은가

허프만 부호는 "글자마다 정수 개의 비트를 주는 접두 부호" 가운데 전체 길이(횟수 × 부호 길이의 합)가 가장 짧습니다. 위 예에서 「장」 넷에 1비트, 「공」·빈칸 둘씩에 2·3비트, 「간」 하나에 3비트를 주어 17비트가 됩니다. 이보다 짧은 접두 부호는 없습니다. 다만 글자마다 정수 개의 비트를 주는 방식 안에서의 최소입니다. LZSS처럼 앞에 나온 문자열을 다시 쓰거나, 산술 부호처럼 글자 하나에 1.3비트 같은 정수가 아닌 길이를 줄 수 있는 방식은 더 짧아질 수 있습니다.

같은 무게일 때

무게가 같은 것이 여럿이면 어느 둘을 고르느냐에 따라 트리 모양과 부호가 달라지지만, 전체 길이는 같습니다. 그러니 압축기와 해제기가 같은 트리를 쓰기만 하면 됩니다. 위 도구는 횟수가 같으면 글자를 묶음보다 먼저, 글자끼리는 먼저 나온 글자를, 묶음끼리는 먼저 만든 묶음을 고르고, 먼저 고른 쪽에 0을 줍니다.

트리 대신 부호 길이만 저장하기

해제기는 트리를 알아야 하므로 압축 자료와 함께 트리도 어딘가에 있어야 합니다. 트리 모양을 통째로 저장하는 대신 글자마다 부호 길이만 저장하는 방법이 정규 허프만 부호(canonical Huffman code)입니다. 길이만 같으면 부호가 무엇이든 전체 길이는 같으므로, 부호를 정해진 규칙으로 다시 만들어 씁니다(RFC 1951 3.2.2).

글자를 부호 길이가 짧은 순으로, 길이가 같으면 글자 순서대로 줄 세웁니다.
가장 짧은 길이의 첫 부호는 모두 0입니다.
다음 글자의 부호는 앞 부호에 1을 더한 값입니다.
길이가 한 칸 늘어나는 곳에서는 1을 더한 뒤 끝에 0을 하나 붙입니다.

RFC의 예에서 A–H의 길이가 (3, 3, 3, 3, 3, 2, 4, 4)이면, 가장 짧은 F가 00, 길이가 3으로 늘어나는 A는 00 + 1 = 01에 0을 붙인 010, 그 뒤로 B 011, C 100, D 101, E 110, 다시 길이가 늘어나는 G 1110, H 1111입니다. 이 가이드의 허프만 코드도 이 예로 테스트합니다.

이렇게 하면 해제기에 필요한 것은 "길이마다 부호가 몇 개인가"와 글자 순서뿐입니다. 길이마다 첫 부호를 계산해 두고, 읽은 비트가 그 길이의 범위 안에 들면 몇 번째 글자인지 바로 셉니다. 노드마다 두 칸씩 쓰는 트리 표보다 훨씬 작게 저장할 수 있어서 롬 자리가 빠듯할 때 유리합니다. ZIP·PNG가 쓰는 DEFLATE도 이 방식입니다.

글자가 수백·수천 개인 게임에서는 부호 길이가 20비트 가까이 길어질 수 있습니다. 해제 루틴이 다룰 수 있는 최대 길이를 정해 두고, 그보다 긴 부호가 나오지 않도록 트리를 고쳐 만드는 형식도 있습니다(DEFLATE는 15비트).

비트열을 한 비트씩 읽기 쉽게

허프만 부호로 적은 자료는 바이트 경계를 무시하고 비트가 줄줄이 이어집니다. 그래서 읽는 쪽은 "지금 몇 번째 바이트의 몇 번째 비트"를 기억하는 비트 위치를 들고 다닙니다. 한 바이트 안에서 어느 비트부터 읽는지도 정해져 있어야 합니다. 맨 위 비트(비트 7)부터 읽는 형식도, 맨 아래 비트(비트 0)부터 읽는 형식도 있습니다.

제절초 일본판 대본의 비트 위치 126(0부터 셈)부터. 바이트마다 아래 비트부터 읽습니다.

읽는 과정은 위 도구의 ④와 같습니다. 루트에서 시작해 비트가 0이면 한쪽, 1이면 다른 쪽 가지로 내려가고, 리프에 닿으면 글자 하나를 내놓고 루트로 돌아갑니다. 글자 하나를 읽는 데 부호 길이만큼 반복하므로, 긴 부호는 읽는 데도 오래 걸립니다.

비트열 안의 위치를 가리키는 값도 비트 단위가 됩니다. 대본에서 다른 장면으로 점프하는 제어 코드라면 점프할 곳이 "기준점에서 몇 번째 비트"로 적힙니다. 번역해서 글자 수가 바뀌면 모든 점프 위치를 비트 단위로 다시 계산해야 합니다.

롬에 트리를 저장하는 방법과 찾는 법 쉽게

게임은 트리를 롬에 표로 넣어 둡니다. 가장 흔한 꼴은 노드마다 "0일 때 갈 곳"과 "1일 때 갈 곳"을 적은 표입니다. 갈 곳이 다른 노드인지 리프(글자)인지는 값의 한 비트로 구별합니다. 제절초 일본판은 "1일 때 표"와 "0일 때 표"를 따로 두고, 노드의 위치(오프셋)로 두 표를 같이 찾아봅니다.

더 깊이두 표로 트리를 따라가는 실제 모습

제절초 일본판에서 「の」(01001)를 읽는 길. 값의 맨 위 비트가 1이면 리프입니다.

처음 읽은 $05B4는 맨 위 비트가 꺼져 있으니 노드입니다. 값은 노드 번호이고 칸 하나가 2바이트라서, 2를 곱한 $0B68이 다음에 볼 오프셋입니다. 마지막의 $862E는 맨 위 비트가 켜져 있으므로 리프이고, 아래 13비트 $062E(1582)가 폰트의 「の」 번호입니다.

롬에서 허프만 자료를 찾는 단서는 이렇습니다.

화면에 나온 대사를 8장의 방법(글자표 만들기, 연속된 번호 찾기)으로 아무리 찾아도 나오지 않습니다.
대사를 찍는 코드를 거슬러 올라가면 LSR·ROL로 한 비트씩 밀어내고, 8번마다 다음 바이트를 읽고, 그 비트로 두 표 가운데 하나를 고르는 반복문이 나옵니다. 이 반복문이 끝나는 곳에서 나오는 값이 글자 번호입니다.
반복문이 읽는 표는 2바이트 값이 수천 개 이어지고, 그 가운데 절반쯤은 맨 위 비트가 켜져 있습니다(리프). 리프의 아래 비트를 모으면 글자 번호가 겹치지 않고 하나씩 나옵니다.
대본 위치를 담은 WRAM 변수 옆에 "바이트 안의 비트 번호"(0–7)를 담은 변수가 하나 더 있습니다. 제절초는 $52–$54가 위치, $55가 비트 번호입니다.

실제 패치에서 실제 패치에서

제절초 일본판: 대본 전체가 허프만 비트열

제절초 일본판은 대본 전체를 허프만 부호로 이어 붙인 비트열 하나로 넣었습니다. 기준점은 $15:E401(파일 0xAE401)이고, 바이트마다 아래 비트부터 읽습니다. 크기는 약 246만 비트, 바이트로 30만 바이트쯤입니다. 기호는 $000–$FFF가 글자(폰트 번호), $1000–$1046이 제어 코드입니다. 리프에는 이 밖에 $1176이 하나 있는데, 대본 전체를 처음부터 읽어 보면 글자나 제어 코드로는 한 번도 나오지 않고 선택지 코드 {1A}의 첫 인자(보기 수와 표시 조건을 묶은 값)로 한 번 쓰입니다. 인자도 같은 허프만 부호로 적혀 있기 때문입니다.

트리는 위 「더 깊이」의 두 표이고 루트는 오프셋 $0B6C입니다. 이 트리를 끝까지 따라가 세어 보면 리프가 1,464개, 갈림길인 노드가 1,463개입니다(두 갈래 트리에서 리프는 언제나 갈림길 노드보다 하나 많습니다). 표마다 갈림길 노드 수만큼 1,463칸, 2,926바이트입니다. 부호 길이는 5비트에서 19비트까지이고, 가장 짧은 5비트 부호는 아홉 개입니다. 줄바꿈 제어 코드 {00}과 글자 여덟 개(마침표 「。」, 쉼표 「、」, 「の」, 「い」, 「た」, 「っ」, 말줄임표(…), 여는 낫표 「「」)입니다.

대본의 첫 문장 「夏の夕暮。」와 줄바꿈은 제어 코드 넷 뒤, 비트 위치 126(0부터 셈)부터 61비트에 들어 있습니다.

1000100000000010夏 · 16비트
01001の · 5비트
1111101010101000夕 · 16비트
00110111101111暮 · 14비트
10010。 · 5비트
11001{00} · 5비트

점프 인자는 기호가 아니라 기준점에서 센 24비트 비트 위치가 비트열 안에 그대로 들어 있습니다. 읽은 뒤 $02:C0A1에서 LoROM 주소로 바꿉니다. 시나리오 시작 주소 표($02:A627)도 비트 위치이고, 세이브 파일의 "어디까지 읽었나"도 바이트 주소에 바이트 안의 비트 번호를 더해 적습니다.

한글판 v1.0: 압축 대신 기호마다 2바이트

한글판 v1.0은 허프만 비트열을 버리고 기호마다 2바이트(큰 자리 먼저)로 적은 대본을 새로 넣었습니다. 읽는 루틴은 $02:C156을 "허프만 트리 따라가기"에서 "2바이트 읽기"로 바꿨고, $02:C087·$02:C106에서 비트 위치를 주소로 바꾸던 계산을 건너뜁니다. 점프 인자도 비트 위치 대신 3바이트 LoROM 주소(작은 자리 먼저)가 됐습니다. 같은 첫 문장 「여름의 해질녘.」과 줄바꿈은 기호 9개, 18바이트(144비트)입니다.

일본판과 한글판 v1.0의 대본 비교
	일본판	한글판 v1.0
기호 하나	5–19비트(허프만 부호)	16비트
첫 문장과 줄바꿈	6기호 61비트	9기호 144비트
대본 전체	약 246만 비트(약 30만 바이트)	694,995바이트
점프 위치	기준점부터 비트 수(24비트)	LoROM 주소(3바이트)
놓인 곳	$15:E401–(1MB 롬 안)	$20:8000–(늘린 둘째 1MB)

허프만 비트열을 그대로 쓰려면 한국어 대본의 글자 횟수로 트리를 새로 만들고, 트리 표 두 개를 새 글자 수에 맞게 다시 넣고, 모든 점프 위치를 비트 단위로 다시 계산해야 합니다. 2바이트 대본은 이 일이 모두 필요 없고, 덤프·삽입 도구도 바이트 단위로 단순해집니다. 대가는 크기입니다. 69만 바이트는 일본판 대본 자리(약 30만 바이트)에 들어가지 않아 v1.0은 롬을 2MB로 늘리고 대본을 $20:8000부터 두었습니다. 롬을 늘릴 때 따져야 할 것은 11장에서 봅니다. 비워진 일본판 대본 자리($15:E401–)는 나중에 v1.1·v1.2가 새 코드와 표를 넣는 빈 공간이 됐습니다.

직접 해 보기 직접 해 보기

kr-patch-toolkit에는 허프만 명령이 없습니다. 한 게임에만 쓰이는 형식은 툴킷이 아니라 그 게임의 패치 소스에 두기 때문입니다. 제절초 패치 소스의 tools/script.py가 일본판 비트열을 읽습니다. 그 폴더에서 Python을 열고 일본판 롬으로 첫 문장을 읽어 봅니다.

>>> import script
>>> rom = open('otogirisou-j.sfc', 'rb').read()
>>> r = script.JPReader(rom, 126)
>>> [hex(r.sym()) for _ in range(6)]
['0x152', '0x62e', '0x50a', '0x5f6', '0x5c7', '0x1000']
>>> r.pos
187
>>> rom[0xAE410:0xAE418].hex(' ')
'63 04 90 fc aa 60 ef d3'

기호 여섯 개가 夏($152), の($62E), 夕, 暮, 。, 줄바꿈입니다. 위치가 126에서 187로 61비트 나아갔습니다. JPReader.sym()은 위 그림처럼 비트 하나를 읽을 때마다 두 표 가운데 하나에서 16비트 값을 읽고, 맨 위 비트가 켜진 값이 나오면 멈춥니다. 다른 게임의 허프만 대본도 트리를 두 표로 저장하는 형식이라면 비트 순서, 표 위치, 리프 표시 비트, 루트 네 가지를 바꿔 이 코드로 읽어 볼 수 있습니다.