허프만 부호
고정 길이 부호
절약
엔트로피

기호 횟수 부호 비트 전체 비트

허프만 부호화에 대한 자세한 정보

허프만 부호 빌더

영어에서 e처럼 흔한 글자가 z처럼 드문 글자와 똑같은 비트 수를 차지해야 할까요? 허프만 부호화는 자주 나오는 기호에 짧은 부호를, 드문 기호에 긴 부호를 주며, 그것도 가장 좋은 방식으로 해냅니다. 텍스트를 입력하거나 예시를 골라 허프만 트리를 한 단계씩 만들어 보세요. 가장 가벼운 두 트리가 새 노드 아래로 묶이는 일이 되풀이되어 마침내 트리 하나만 남습니다. 그러면 맨 위에서 시작하는 모든 경로가 각각 하나의 부호를 이루며, 부호화된 비트 속에서 각 기호를 따라갈 수 있습니다. 텍스트를 입력하거나 예시를 고르세요. 모든 기호는 횟수를 단 잎 하나로 시작합니다. 구축 과정을 단계별로 진행하세요. 각 단계에서는 가장 가벼운 두 트리를 둘의 합을 가중치로 하는 새 노드 아래에 묶으며, 트리가 하나만 남을 때까지 계속합니다. 그러면 맨 위에서 잎까지의 경로가 그 기호의 부호가 됩니다. 왼쪽은 0, 오른쪽은 1입니다. 잎, 표의 행, 비트의 한 부분을 클릭해 기호 하나를 따라가고, 합계를 고정 길이 부호 및 엔트로피와 비교해 보세요.

작동 원리

  1. 텍스트를 입력하거나 붙여 넣거나, ABRACADABRA나 MISSISSIPPI RIVER 같은 예시를 고르세요.
  2. ‘다음 단계’로 구축 과정을 한 단계씩 진행하거나 ‘재생’을 누르세요. 각 단계에서 가장 가벼운 두 트리가 둘의 합을 가중치로 하는 노드 아래로 묶입니다.
  3. 트리가 완성되면 잎, 표의 행, 비트의 한 부분을 클릭해 기호 하나를 따라가고, 타일에서 합계를 비교하세요.

트리를 만드는 방법

각 기호가 몇 번 나오는지 세고, 각 기호를 횟수를 가중치로 하는 잎 하나짜리 트리로 만듭니다. 그런 다음 간단한 단계 하나를 되풀이합니다. 가중치가 가장 작은 두 트리를 골라, 둘의 합을 가중치로 하는 새 노드 아래에 매다는 것입니다. 단계마다 트리가 하나씩 줄어들므로, 기호가 n개이면 n − 1단계 뒤에 트리 하나가 남습니다. 드문 기호는 먼저 묶여 깊은 곳에 자리하고, 흔한 기호는 늦게 묶여 맨 위 가까이에 자리합니다.

부호 읽기

맨 위에서 아래로 내려갑니다. 왼쪽으로 한 걸음 가면 0, 오른쪽으로 한 걸음 가면 1이 붙습니다. 잎까지의 경로가 그 기호의 부호입니다. 기호는 잎에만 있으므로 어떤 부호도 다른 부호의 앞부분이 되지 않습니다. 그래서 비트열을 구분 기호 없이 복호화할 수 있습니다. 비트를 따라 트리를 내려가다가 잎에 닿을 때마다 그 기호를 적고 다시 맨 위에서 시작하면 됩니다. ABRACADABRA의 경우 허프만 부호는 23비트가 필요하고, 글자당 3비트인 고정 길이 부호는 33비트가 필요합니다.

자주 묻는 질문

허프만 부호가 가장 좋은 이유는 무엇인가요?

각 기호에 정수 개의 비트로 된 고유한 비트열을 주는 모든 부호 가운데, 주어진 횟수에 대해 합계가 이보다 짧은 부호는 없습니다. 증명은 구성 과정을 따라갑니다. 최적 부호에서는 가장 드문 두 기호를 언제나 가장 깊은 층의 형제로 만들 수 있고, 둘을 묶으면 같은 종류의 더 작은 문제가 남습니다. 전체 비트 수는 트리의 모든 내부 노드의 가중치를 더한 값과 같습니다.

접두 부호란 무엇인가요?

0, 10, 110, 111처럼 어떤 부호어도 다른 부호어의 앞부분이 되지 않는 부호입니다. 이 성질 덕분에 복호기는 부호어가 어디서 끝나는지 늘 알 수 있으므로, 구분 기호 없이 비트열을 읽을 수 있습니다. 모든 허프만 부호는 접두 부호입니다. 기호가 트리의 잎에만 있기 때문입니다.

허프만 트리는 하나뿐인가요?

꼭 그렇지는 않습니다. 두 트리의 가중치가 같으면 어느 쪽을 먼저 골라도 되고, 왼쪽과 오른쪽을 바꿀 수도 있습니다. 선택이 다르면 부호도 달라지지만, 전체 비트 수는 언제나 같습니다. 이 빌더는 가중치가 같을 때 항상 같은 방식으로 고르므로, 같은 텍스트에서는 항상 같은 트리가 나옵니다.

허프만 부호는 엔트로피에 얼마나 가까워지나요?

평균 부호 길이는 엔트로피 이상이며, 엔트로피보다 큰 정도는 1비트 미만입니다. ‘절반씩 줄어드는 횟수’ 예시처럼 모든 확률이 2분의 1의 거듭제곱이면 엔트로피와 정확히 같습니다. 산술 부호화와 현대의 범위 부호화기는 정수 비트의 한계를 피해 더 가까이 다가갑니다.

제 텍스트가 어딘가로 전송되나요?

아니요. 트리와 부호는 브라우저에서 계산되며, 텍스트는 이 브라우저의 로컬 저장소에 남습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

편집기로 이동