허프만 코드 - 자주 나오는 것에 짧은 이름을 준다

노트에 자주 나오는 낱말을 기호 하나로 정해 두는 요령이 있다. 그걸 기계가 하려면 무엇을 정해야 하는지 본다.

모두에게 같은 길이를 주는 건 낭비다

아스키는 모든 글자에 정확히 같은 크기를 준다. e도 한 바이트, z도 한 바이트다.

그런데 실제 영어 글에서 e는 수백 번 나오고 z는 한두 번 나온다. 수백 번 나오는 것과 한 번 나오는 것에 같은 길이를 주고 있는 것이다. 노트를 적는 학생이라면 절대 이렇게 안 한다.

여기서 압축의 둘째 아이디어가 나온다.

자주 나오는 것에 짧은 이름을, 드물게 나오는 것에 긴 이름을 준다.

앞 글에서 본 반복 지우기와는 원리가 아예 다르다. 저쪽은 “같은 게 또 나왔다”를 봤고, 이쪽은 **“이건 유난히 자주 나온다”**를 본다. 반복이 하나도 없는 데이터에서도 이건 통한다.

짧게 주면 어디서 끊을지 모른다

발상은 쉬운데 곧장 벽에 부딪힌다. 예를 들어 이렇게 이름을 나눠 준다고 하자.

이제 01이라는 비트가 왔다. 이건 C인가, 아니면 A 다음에 B인가. 둘 다로 읽히니 답이 없다.

길이가 다 같을 때는 이런 고민이 없었다. 8비트씩 끊으면 그만이었으니까. 길이를 제각각으로 만드는 순간 **“어디까지가 한 글자인가”**라는 문제가 따라온다.

한 가지 해법은 글자 사이에 구분 기호를 넣는 것이다. 하지만 그 기호도 자리를 차지하니 줄이려던 만큼을 도로 뱉는다. 더 나은 방법이 있다.

아무도 남의 앞머리가 아니면 된다

01이 헷갈렸던 이유를 정확히 짚어 보자. A의 이름 0이 C의 이름 01의 앞머리와 같았기 때문이다. 읽는 쪽이 0을 보는 순간 “여기서 끊을까, 더 볼까”를 결정할 수 없다.

그러면 규칙은 하나로 정해진다.

어떤 이름도 다른 이름의 앞머리가 되지 않게 한다.

이 조건을 지키는 이름표를 접두어 코드라고 부른다. 이렇게 만들어 두면 읽는 쪽은 비트를 하나씩 받으면서 지금까지 받은 것이 어떤 이름과 일치하는 순간 바로 끊으면 된다. 그 이름이 다른 무언가의 앞머리일 리가 없으니 더 볼 필요가 없다. 구분 기호가 필요 없어지는 것이다.

이 조건을 저절로 만족시키는 그림이 있다. 갈림길이 둘씩 있는 나무를 그리고, 글자를 전부 잎에만 매다는 것이다. 왼쪽으로 내려가면 0, 오른쪽이면 1로 읽으면 뿌리에서 잎까지의 경로가 곧 그 글자의 이름이 된다.

잎에만 글자가 있으니 어떤 글자도 다른 글자로 가는 길 위에 있지 않다. 접두어 조건이 그림의 모양만으로 지켜진다. 그리고 자주 나오는 글자를 얕은 자리에 매달면 그 글자의 이름이 짧아진다.

나무를 아래에서 위로 짓는다

남은 질문은 하나다. 어떤 글자를 얕게 두고 어떤 글자를 깊게 둘지를 어떻게 정하나.

허프만이 찾아낸 답은 놀랍도록 단순하다. 가장 드문 둘을 골라 묶고, 그 묶음을 하나의 새 항목으로 쳐서 다시 반복한다. 위에서 아래로 내려가며 나누는 게 아니라 아래에서 위로 붙여 올라간다.

글자 다섯 개가 이런 빈도로 나온다고 하자.

가장 드문 둘은 D(10)와 E(5)다. 둘을 묶으면 15짜리 묶음이 된다. 이제 남은 것은 A(45), B(25), C(15), 그리고 방금 만든 묶음(15)이다. 다시 가장 드문 둘은 C와 그 묶음이니 둘을 묶어 30을 만든다. 같은 짓을 하나가 남을 때까지 되풀이하면 나무가 완성된다.

결과로 나온 이름은 이렇다.

전부 100글자를 적는 데 드는 비트를 세어 보면 200비트다. 다섯 종류를 같은 길이로 적으려면 글자당 3비트가 필요하니 300비트인데, 3분의 1이 사라졌다.

치우침이 클수록 많이 준다

이 방법이 얼마나 이득인지는 빈도가 얼마나 치우쳤느냐가 정한다.

• 아주 치우친 경우 - 한 글자가 90%를 차지하면 그 글자에 1비트를 주는 것만으로 거의 다 줄어든다
• 완전히 고른 경우 - 다섯 글자가 각각 20%씩이면 짧게 줄 만한 후보가 없다. 이름 길이가 죄다 비슷해지고 이득이 거의 사라진다

치우침이 없으면 이 방식은 할 일이 없다. 앞 글에서 “줄어드는 이유는 반복 아니면 치우침”이라고 한 것의 뒷면이 이거다. 치우침이 곧 이 방법의 연료다.

이름표도 같이 보내야 한다

여기 놓치기 쉬운 대가가 있다. 짧게 적은 비트만 보내면 받는 쪽은 아무것도 못 읽는다. 어떤 글자가 어떤 이름을 받았는지도 같이 보내야 한다.

노트로 치면 기호를 정해 둔 페이지를 같이 넘겨줘야 하는 것과 같다. 나만 아는 기호로 줄여 놓고 노트만 빌려주면 상대는 못 읽는다.

이 이름표가 차지하는 자리는 공짜가 아니다. 그래서 아주 작은 데이터에서는 손해가 난다. 100바이트짜리를 줄여서 60바이트를 만들어도 이름표가 80바이트면 결과는 더 커진다.

실제 형식들은 이 값을 깎으려고 여러 요령을 쓴다. 이름표 자체를 규칙으로 압축해 담기도 하고, 흔한 데이터의 빈도를 미리 정해 둔 표를 쓰기도 한다. 그래도 “표를 같이 보내야 한다”는 성질 자체는 사라지지 않는다.

반복 지우기와는 겹치지 않는다

여기서 두 아이디어의 관계를 못 박아 둘 값이 있다. 둘은 경쟁하는 방법이 아니라 서로 다른 낭비를 본다.

ABCABCABCABC를 보자. 세 글자의 빈도가 정확히 같으니 짧은 이름 주기로는 한 톨도 못 줄인다. 그런데 ABC가 네 번 반복되니 가리키기로는 훅 준다.

거꾸로 AAAAABBAABABAB 같은 데이터는 긴 반복 덩어리가 없어도 A가 압도적으로 잦다. 짧은 이름 주기가 여기서 힘을 쓴다.

서로 못 잡는 자리가 정확히 반대라는 걸 알면 다음 글이 저절로 예고된다. 둘을 겹치면 어떻게 되겠는가.

실무에서: 혼자 쓰이는 일은 드물다

허프만 코드를 단독 압축기로 쓰는 경우는 요즘 거의 없다. 대신 거의 모든 압축 형식의 마지막 단계로 들어가 있다.

• gzip·zip·PNG - 반복을 가리킨 결과에 다시 허프만을 씌운다. 다음 글의 주제다
• JPEG - 손실 단계를 거친 뒤 남은 값들을 허프만으로 마무리한다
• HTTP/2 헤더 압축 - 자주 쓰이는 헤더 이름과 값에 짧은 코드를 준다

이름을 몰라도 이미 여러분의 코드가 이걸 지나가고 있다는 뜻이다. 그리고 이 원리를 알면 실무에서 흔히 하는 착각 하나가 정리된다.

“필드 이름을 짧게 줄이면 응답이 작아지겠지”라는 판단이 그것이다. userName을 un으로 바꾸는 식이다. 그런데 그 응답에 압축이 걸려 있다면 긴 이름은 어차피 짧은 코드를 받거나 앞의 반복을 가리키는 것으로 바뀐다. 읽기만 나빠지고 크기는 기대만큼 안 준다.

압축이 켜져 있는 자리에서는 사람이 손으로 하는 절약이 대체로 헛수고다. 이 판단은 이 시리즈의 마지막 편에서 표로 정리한다.

정리

• 모든 글자에 같은 길이를 주는 건 낭비다. 자주 나오는 것에 짧은 이름을 주면 줄어든다.
• 길이를 다르게 하면 어디서 끊을지가 문제가 되는데, 어떤 이름도 남의 앞머리가 아니게 만들면 해결된다.
• 그 조건은 글자를 나무의 잎에만 매다는 것으로 저절로 지켜진다. 뿌리에서 잎까지의 길이 곧 이름이다.
• 나무는 가장 드문 둘을 계속 묶어 올라가며 짓는다. 이렇게 만든 것이 최적이라는 건 증명되어 있다.
• 치우침이 클수록 많이 준다. 빈도가 고르면 이 방법은 할 일이 없다.
• 이름표를 같이 보내야 하므로 작은 데이터에서는 손해가 날 수 있다.
• 반복 가리키기와 못 잡는 자리가 정확히 반대다.

다음 글은 그 둘을 겹친다. 세상에서 가장 널리 쓰이는 압축이 정확히 이 조합이다.