gzip 과 나란히
fixed-Huffman 압축기는 gzip -9 에 대해 약 2 배의 여지를 남겼고, 그 구멍을 메우는 것이 dynamic Huffman 이다. 양쪽이 미리 합의하는 부호표 대신 각 블록의 실제 심볼 빈도에 맞춘 표를 만들어 전송한다. 그것은 순수 Mere 로 Huffman 트리를 짜는 것을 뜻한다 —— node pool, 빈도가 가장 낮은 두 노드를 반복해 병합하고, 각 잎의 깊이를 부호 길이로 읽는다 —— 부호를 canonical 하게 만들고, 그다음 부호 길이의 표 자체를 블록 헤더로 run-length 부호화한다. 부호가 형식의 15 비트 상한을 넘는 드문 입력에는 stored 블록의 fallback 을 둔다. 결과는 참조 도구와 대등하다 —— 실제 텍스트에서 몇 % 차, 반복이 많은 입력에서는 gzip -9 를 앞선다. 형식을 읽는 데서 시작한 아크가, 모두가 비교하는 기준 도구만큼 잘 쓰는 것으로 끝난다.
압축기는 동작했고 구멍을 남겼다. fixed Huffman 은 gzip -9 의 약 2 배 크기를 냈다. 그 2 배는 매칭의 비효율도 출력의 버그도 아니다 —— 그것이야말로 dynamic Huffman 의 존재 이유 전부다. 고정된 부호표는 무엇에나 그런대로 맞도록 미리 고른 타협이고, dynamic 한 표는 눈앞의 블록에 맞춰진다. 실제로 자주 나타나는 심볼에 짧은 부호를 배정하고, 고유의 표를 전송하는 비용은 절약으로 몇 배로 되돌아온다. 구멍을 메운다는 것은 그 표를 구성하는 기계를 순수 Mere 로 짜는 것이며, 그리고 언어에는 구성에 필요한 것이 모두 갖춰져 있었다.
node pool 에서 Huffman 트리를
최적의 prefix 부호를 짜는 것은 고전의 Huffman 알고리즘이다. 각 심볼을 빈도로 가중한 잎으로 보고, 가장 가벼운 두 노드를 취해 그 합을 무게로 하는 새 부모 밑에 병합하고, 노드가 하나 남았을 때 각 잎의 깊이가 그 부호 길이가 된다. 나는 트리를 병렬 vector 로 구현했다 —— 빈도 · 왼쪽 자식 · 오른쪽 자식 · 잎의 심볼을 갖는 node pool —— 병합이 내부 노드를 만들 때마다 늘리고, 아직 병합 후보인 노드를 alive 플래그로 표시한다. 매번 가장 가벼운 둘을 찾는 것은 선형 주사다. 프로덕션 encoder 는 heap 을 쓰지만 이것은 쓰지 않는다. 알파벳이 작기 때문이다 —— 286 개의 리터럴／길이 심볼, 30 개의 거리 심볼 —— 그리고 상수 배보다 명료함이 중요했다. 완성된 트리의 깊이 우선 순회가 부호 길이를 읽어내고, 심볼이 0 개와 1 개인 퇴화 케이스는 각각의 단락을 가진다.
부호를 canonical 하게, 그리고 부호화를 부호화하다
부호 길이는 아직 부호가 아니다. DEFLATE 는 canonical Huffman 부호를 요구한다. 각 심볼에 배정한 길이 만으로 양쪽이 같은 규칙으로 실제 비트열을 도출한다 —— 각 길이를 공유하는 부호가 몇 개인지 세고, 각 길이의 첫 부호를 계산하고, 심볼 순으로 나눠 준다. 이것은 decoder 가 거꾸로 돌린 도출과 같고, 명세에서 옮기니 inflater 가 그대로 받아들이는 부호가 나왔다. decode 쪽에 대응물이 없는 부분은 부호 길이의 표 자체를 블록 헤더로 압축해야 한다는 점이다 —— 반복과 0 의 연속을 위한 고유의 세 특수 심볼을 갖는 작은 run-length 방식으로, 그 빈도가 두 번째의 더 작은 Huffman 부호를 구동하고, 그 길이가 헤더에 먼저 들어 간다. 압축기가 자신의 부호표를 압축한다는 이 재귀적 구조는 명세에서는 거창하게 읽히지만 부품을 이름 붙이면 말끔히 떨어진다.
fallback, 그리고 숫자
canonical 부호에는 단단한 상한이 있다. DEFLATE 는 부호당 최대 15 비트만 배정하고, 병적으로 치우친 빈도 분포는 그보다 긴 것을 낳을 수 있다. 프로덕션 encoder 는 재분배하는 길이 제한 패스를 돌린다. 이것은 더 단순하고 올바른 길을 택해, 부호가 15 비트를 넘는 것이 있는지 확인하고, 있으면 블록을 비압축으로 낸다 —— stored 블록, 항상 유효, 그래서 어떤 입력도 잘못된 출력을 낳을 수 없다. 현실적인 데이터에서 상한에 가까워지는 일은 없지만, 전형적인 입력에서만 올바른 압축기는 올바르지 않다. fallback 을 두고 숫자는 아크가 겨냥한 곳에 닿았다. fixed Huffman 이 114 바이트로 만든 중복 많은 산문 파일이 102 바이트가 되었고, gzip -9 의 113 에 대비된다. 저중복 파일은 fixed 를 훨씬 밑돌고 gzip 을 근소하게 밑돌 았다. 실제 20 킬로바이트 README 는 gzip -9 의 3 % 이내에 들었다. 반복이 많은 입력에서 encoder 는 이제 참조 도구를 명확히 앞서고, 모든 것이 여전히 system 의 gunzip 과 언어 자신의 inflater 를 바이트 단위로 round-trip 한다.
아크는 여기서 닫힌다. 세 편 전, gzip 형식을 읽을 수 있는 해제기로 시작해, 그것을 쓸 수 있는 압축기로 넓어지고, 같은 핵심 위에 세워진 진짜 이미지 형식에 이르고, 그리고 압축기가 모두가 벤치마크하는 도구와 대등한 출력을 내는 것으로 끝난다 —— 모두 순수 Mere 로, 모두 system 유틸리티와 바이트 호환으로, 그리고 압축 작업 자체를 위해서는 언어를 한 번도 바꾸지 않고. 성숙한 언어가 이렇게 재어 어떻게 보이는가 하면, 실제 형식의 쌓임과 대등한 압축기가 평범한 프로그램으로 그 언어로 쓰이고, 컴파일러는 한 번도 움직이지 않아도 된다는 것이다.