압축기를 쓰다

해제기는 형식을 읽었다. 다음의 자연스러운 물음은 언어가 그것을 쓸 수 있는가다. 압축 스트림의 읽기와 쓰기는 대칭인 작업이 아니다 —— 복호는 기계적이고 선택의 여지가 없는 명세를 따를 뿐이지만, 부호화는 모든 판단이 깃드는 곳이다 —— 그러나 둘은 형태를 공유한다. inflater 가 분해한 모든 구조를 deflater 는 다시 조립해야 한다. 같은 블록, 같은 부호표, 같은 비트 단위의 채워 넣기. 해제기 다음에 압축기를 쓰는 일은 새 건축이라기보다 이미 서 있는 무언가의 거울상을 세우는 작업에 가까웠다.

bit writer 는 bit reader 를 거꾸로 돌린 것

inflater 의 핵심은 bit reader 였다. 바이트 커서와 작은 버퍼를 두고, DEFLATE 가 채우는 순서에 맞춰 바이트 경계를 넘어 최하위 비트부터 나눠 준다. deflater 에는 그 엄밀한 역이 필요하다 —— 값과 폭을 받아 같은 순서로 그 비트를 출력 스트림에 밀어 넣고, 8 비트가 쌓일 때마다 바이트를 flush 하고, 마지막 하나는 0 으로 채우는 bit writer 다. 둘은 너무나 서로의 거울상이라 두 번째를 쓰는 일은 첫 번째를 읽고 대입의 방향을 모두 뒤집는 작업이 거의 전부였다. 이름 붙일 만한 유일한 비대칭은, Huffman 부호는 최상위 비트부터 내보내야 하는데 extra 비트는 최하위부터 내보낸다는 점이다. 그래서 writer 는 각 부호를 미리 뒤집는다 —— reader 가 반대 방향으로 부호를 소비했기에 필요로 하지 않았던, 그 비트 반전이다.

greedy 한 매칭

reader 는 스트림 안에서 찾은 후방 참조를 그저 따르면 됐지만, writer 는 그것을 발명해야 한다. 이것이 압축기의 진짜 일이다. 각 위치에서 window 를 뒤로 훑어 여기서 반복되는 가장 긴 바이트 열을 찾고, 그것이 3 바이트 이상이면 리터럴 대신 길이／거리 쌍을 내보낸다. 구현은 소박한 window 주사다 —— 32 킬로바이트 상한까지 뒤로 걸으며 각 후보에서 매칭 길이를 재고 가장 긴 것을 남긴다. 진짜 압축기는 재주사를 피하려고 hash chain 을 쓰지만 이것은 쓰지 않는다. 정직한 greedy 매칭으로, 네이티브에서는 충분히 빠르고 인터프리터에서는 느리다. 바로 이 트레이드오프를 probe 는 숨기지 말고 드러내야 한다. 매칭한 길이와 거리는 reader 가 복호에 쓴 것과 같은 base + extra 비트 부호화표를 거꾸로 돌려 통과시킨다.

fixed Huffman, 그리고 그것이 남기는 구멍

첫 판은 fixed-Huffman 표를 썼다 —— 양쪽이 이미 합의한 명세 내장의 부호 길이라 트리에 관해 아무것도 전송하지 않아도 된다. 이것은 가장 단순한 올바른 부호화기이고 제대로 동작한다. 중복이 많은 18 킬로바이트 텍스트 파일이 0.06 초에 138 바이트로 압축되었고, system 의 gunzip 도 지난 편의 inflater 도 일치하는 체크섬과 함께 바이트 단위로 복원했다. 그러나 같은 입력에 대해 gzip -9 는 66 바이트를 냈다. 이 차이는 버그가 아니다 —— 그것이야말로 dynamic Huffman 의 존재 이유로, 고정된 표를 쓰는 대신 각 블록의 실제 심볼 빈도에 맞춘 부호표를 만든다. fixed Huffman 에 greedy 매칭을 더하면 대략 2 배의 여지를 남기고, 그 구멍을 정확히 이름 붙이는 일 —— 출력의 결함이 아니라 부호화기의 완성도의 구멍 —— 이 다음 한 걸음을 준비했다.

애초에 압축기를 쓸 수 있었던 것은 필요한 것이 모두 다른 이유로 먼저 갖춰져 있었기 때문이다. bitwise 연산자, 바이너리 안전한 파일 읽기와 쓰기, 이전 probe 에서 만든 체크섬. 바이트에서 압축 바이트로, 그리고 되돌리는 루프를 닫는 데 언어에 새로 더할 것은 하나도 없었다. 부호화기는 컴파일러를 한 줄도 바꾸지 않고 컴파일이 되었고 유효한 gzip 을 냈다 —— 해제기와 압축기, 둘 다 순수 Mere 로, system tool 과도 서로와도 상호 운용된다. 남은 구멍은 압축률에 관한 것이지 정확성이 아니었고, 그리고 그것은 메우는 법을 아는 구멍이었다.