| 기호 | 횟수 | 부호 | 비트 | 전체 비트 |
|---|
허프만 부호 빌더
영어에서 e처럼 흔한 글자가 z처럼 드문 글자와 똑같은 비트 수를 차지해야 할까요? 허프만 부호화는 자주 나오는 기호에 짧은 부호를, 드문 기호에 긴 부호를 주며, 그것도 가장 좋은 방식으로 해냅니다. 텍스트를 입력하거나 예시를 골라 허프만 트리를 한 단계씩 만들어 보세요. 가장 가벼운 두 트리가 새 노드 아래로 묶이는 일이 되풀이되어 마침내 트리 하나만 남습니다. 그러면 맨 위에서 시작하는 모든 경로가 각각 하나의 부호를 이루며, 부호화된 비트 속에서 각 기호를 따라갈 수 있습니다. 텍스트를 입력하거나 예시를 고르세요. 모든 기호는 횟수를 단 잎 하나로 시작합니다. 구축 과정을 단계별로 진행하세요. 각 단계에서는 가장 가벼운 두 트리를 둘의 합을 가중치로 하는 새 노드 아래에 묶으며, 트리가 하나만 남을 때까지 계속합니다. 그러면 맨 위에서 잎까지의 경로가 그 기호의 부호가 됩니다. 왼쪽은 0, 오른쪽은 1입니다. 잎, 표의 행, 비트의 한 부분을 클릭해 기호 하나를 따라가고, 합계를 고정 길이 부호 및 엔트로피와 비교해 보세요.
작동 원리
- 텍스트를 입력하거나 붙여 넣거나, ABRACADABRA나 MISSISSIPPI RIVER 같은 예시를 고르세요.
- ‘다음 단계’로 구축 과정을 한 단계씩 진행하거나 ‘재생’을 누르세요. 각 단계에서 가장 가벼운 두 트리가 둘의 합을 가중치로 하는 노드 아래로 묶입니다.
- 트리가 완성되면 잎, 표의 행, 비트의 한 부분을 클릭해 기호 하나를 따라가고, 타일에서 합계를 비교하세요.
트리를 만드는 방법
각 기호가 몇 번 나오는지 세고, 각 기호를 횟수를 가중치로 하는 잎 하나짜리 트리로 만듭니다. 그런 다음 간단한 단계 하나를 되풀이합니다. 가중치가 가장 작은 두 트리를 골라, 둘의 합을 가중치로 하는 새 노드 아래에 매다는 것입니다. 단계마다 트리가 하나씩 줄어들므로, 기호가 n개이면 n − 1단계 뒤에 트리 하나가 남습니다. 드문 기호는 먼저 묶여 깊은 곳에 자리하고, 흔한 기호는 늦게 묶여 맨 위 가까이에 자리합니다.
부호 읽기
맨 위에서 아래로 내려갑니다. 왼쪽으로 한 걸음 가면 0, 오른쪽으로 한 걸음 가면 1이 붙습니다. 잎까지의 경로가 그 기호의 부호입니다. 기호는 잎에만 있으므로 어떤 부호도 다른 부호의 앞부분이 되지 않습니다. 그래서 비트열을 구분 기호 없이 복호화할 수 있습니다. 비트를 따라 트리를 내려가다가 잎에 닿을 때마다 그 기호를 적고 다시 맨 위에서 시작하면 됩니다. ABRACADABRA의 경우 허프만 부호는 23비트가 필요하고, 글자당 3비트인 고정 길이 부호는 33비트가 필요합니다.
자주 묻는 질문
허프만 부호가 가장 좋은 이유는 무엇인가요?
각 기호에 정수 개의 비트로 된 고유한 비트열을 주는 모든 부호 가운데, 주어진 횟수에 대해 합계가 이보다 짧은 부호는 없습니다. 증명은 구성 과정을 따라갑니다. 최적 부호에서는 가장 드문 두 기호를 언제나 가장 깊은 층의 형제로 만들 수 있고, 둘을 묶으면 같은 종류의 더 작은 문제가 남습니다. 전체 비트 수는 트리의 모든 내부 노드의 가중치를 더한 값과 같습니다.
접두 부호란 무엇인가요?
0, 10, 110, 111처럼 어떤 부호어도 다른 부호어의 앞부분이 되지 않는 부호입니다. 이 성질 덕분에 복호기는 부호어가 어디서 끝나는지 늘 알 수 있으므로, 구분 기호 없이 비트열을 읽을 수 있습니다. 모든 허프만 부호는 접두 부호입니다. 기호가 트리의 잎에만 있기 때문입니다.
허프만 트리는 하나뿐인가요?
꼭 그렇지는 않습니다. 두 트리의 가중치가 같으면 어느 쪽을 먼저 골라도 되고, 왼쪽과 오른쪽을 바꿀 수도 있습니다. 선택이 다르면 부호도 달라지지만, 전체 비트 수는 언제나 같습니다. 이 빌더는 가중치가 같을 때 항상 같은 방식으로 고르므로, 같은 텍스트에서는 항상 같은 트리가 나옵니다.
허프만 부호는 엔트로피에 얼마나 가까워지나요?
평균 부호 길이는 엔트로피 이상이며, 엔트로피보다 큰 정도는 1비트 미만입니다. ‘절반씩 줄어드는 횟수’ 예시처럼 모든 확률이 2분의 1의 거듭제곱이면 엔트로피와 정확히 같습니다. 산술 부호화와 현대의 범위 부호화기는 정수 비트의 한계를 피해 더 가까이 다가갑니다.
제 텍스트가 어딘가로 전송되나요?
아니요. 트리와 부호는 브라우저에서 계산되며, 텍스트는 이 브라우저의 로컬 저장소에 남습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동