허프만 부호화 계산기

빈도가 가장 작은 두 마디를 계속 합쳐 올라갑니다. 글자마다 빈도를 적은 잎을 만들고, 가장 작은 둘을 골라 합치기를 마디가 하나 남을 때까지 되풀이한 뒤, 뿌리에서 잎까지 내려가며 왼쪽은 0, 오른쪽은 1을 붙이면 그것이 부호입니다. 자주 나오는 글자일수록 나중에 합쳐져 뿌리에 가까워지므로 짧은 부호를 받습니다.

틀린 것이 아닙니다. 빈도가 같은 마디가 둘 이상일 때 어느 것을 먼저 합칠지는 정해져 있지 않아 같은 입력에도 부호표가 여러 벌 나옵니다. 다만 어느 것을 고르든 평균 부호길이는 언제나 같으며, 그것이 허프만이 최적이라는 뜻입니다. 이 도구는 결과가 재현되도록 «빈도가 같으면 먼저 만들어진 마디 먼저»로 정해 두었습니다.

어떤 부호도 다른 부호의 앞부분이 되지 않기 때문입니다. 이를 접두부호라 하며, 글자를 트리의 잎에만 두면 저절로 그렇게 됩니다. 그래서 0과 1을 왼쪽부터 읽어 내려가다 잎에 닿는 순간이 곧 한 글자가 끝난 자리입니다. 구분자를 따로 넣을 필요가 없습니다.

없습니다. 섀넌의 소스 부호화 정리에 따라 기호 하나를 평균 H비트보다 적게 담는 무손실 부호는 존재하지 않습니다. 허프만은 H ≤ L < H+1을 보장하는데, 위쪽 1비트의 여유는 부호 길이가 정수여야 해서 생깁니다. 확률이 ½·¼·⅛처럼 2의 거듭제곱이면 낭비 없이 딱 H와 같아집니다.

씁니다. 다만 대개 다른 방식과 함께 씁니다. ZIP과 gzip의 Deflate는 반복되는 부분을 먼저 줄인 뒤 그 결과에 허프만을 적용하고, JPEG과 MP3도 마지막 단계에서 허프만을 씁니다. 허프만 혼자서는 글자 하나하나를 따로 보므로, 앞뒤가 이어지는 실제 자료에서는 다른 방식과 겹쳐 쓰는 편이 훨씬 잘 줄어듭니다.

전송되지 않습니다. 계산은 전부 브라우저 안에서 이뤄지고, 입력값은 이 브라우저의 localStorage에만 남습니다.