허프만 코드와 접두어 없는 표현
작은 빈도를 합쳐 코드 트리를 만들고 가중 평균 길이와 복호를 계산합니다.
자주 쓰는 문자를 짧은 비트열로 표현하면 전체 길이를 줄일 수 있습니다. 그러나 A=0,B=01처럼 한 코드가 다른 코드의 앞부분이면 연속 비트열을 어디서 끊을지 애매합니다. 이 절은 트리 순회, 경우의 수를 연결하는 선택 심화이며 먼저 트리의 잎과 경로를 익힙니다.
코드 트리의 잎에 문자 놓기
이진트리에서 왼쪽 간선 0, 오른쪽 간선 1을 약속하고 루트에서 문자 잎까지의 비트를 코드로 삼습니다. 문자들이 잎에만 있으므로 어느 문자 코드도 다른 코드의 접두어가 아닙니다. 비트를 따라 잎에 도달하면 문자를 출력하고 루트로 돌아가 다음 비트를 읽을 수 있습니다.
빈도 A=8,B=4,C=2,D=2를 사용합니다. 허프만 알고리즘은 가장 작은 두 빈도 C,D를 합쳐 4를 만들고, 새 4와 B의 4를 합쳐 8, 마지막 두 8을 합쳐 16을 만듭니다. 같은 빈도의 선택·좌우 배치가 달라지면 코드 비트는 달라질 수 있지만 이 예제의 길이와 총비용은 같습니다.
작은 빈도를 합친 내부 정점은 문자가 아닙니다
현재 최소인 C와 D를 묶는다. 남은 두 노드를 묶는다. 각 단계의 값과 전환 이유를 비교합니다.
이산수학 · 연결과 계산
작은 빈도를 합친 내부 정점은 문자가 아닙니다
빈도 C=2,D=2를 4로 합치고 B=4와 8로 합친 뒤 A=8과 합쳐 루트 빈도 16을 얻습니다.
- 간선 옆 숫자: 코드 비트
왼쪽 0·오른쪽 1을 따라 A=0,B=10,C=110,D=111입니다. 잎만 문자이고 내부 숫자는 하위 빈도 합입니다. 동점 선택은 다른 최적 코드도 만들 수 있습니다.
이 예의 조건
- 본문과 전체 도표의 예를 따라 2와 2 합병부터 루트 합병까지 진행합니다.
| 관찰·상황 | 값·보충 정보 | 변화·이유 |
|---|---|---|
| 2와 2 합병 현재 최소인 C와 D를 묶는다. |
|
|
| 4와 4 합병 B와 새 노드를 묶는다. |
|
|
| 루트 합병 남은 두 노드를 묶는다. |
|
|
작은 빈도를 합친 내부 정점은 문자가 아닙니다
현재 최소인 C와 D를 묶는다. 남은 두 노드를 묶는다. 각 단계의 값과 전환 이유를 비교합니다.
이산수학 · 연결과 계산
작은 빈도를 합친 내부 정점은 문자가 아닙니다
빈도 C=2,D=2를 4로 합치고 B=4와 8로 합친 뒤 A=8과 합쳐 루트 빈도 16을 얻습니다.
- 간선 옆 숫자: 코드 비트
왼쪽 0·오른쪽 1을 따라 A=0,B=10,C=110,D=111입니다. 잎만 문자이고 내부 숫자는 하위 빈도 합입니다. 동점 선택은 다른 최적 코드도 만들 수 있습니다.
이 예의 조건
- 본문과 전체 도표의 예를 따라 2와 2 합병부터 루트 합병까지 진행합니다.
| 관찰·상황 | 값·보충 정보 | 변화·이유 |
|---|---|---|
| 2와 2 합병 현재 최소인 C와 D를 묶는다. |
|
|
| 4와 4 합병 B와 새 노드를 묶는다. |
|
|
| 루트 합병 남은 두 노드를 묶는다. |
|
|
한 배치에서는 A=0,B=10,C=110,D=111입니다. 총 비트 수는 8·1+4·2+2·3+2·3=28, 문자당 평균은 28/16=1.75비트입니다. 네 문자를 고정 2비트로 표현하면 32비트라 본문 비트 수는 4비트 줄었습니다. 실제 파일 크기에는 코드표·트리·패딩 같은 부가정보도 포함되므로 압축률을 이 숫자만으로 단정하지 않습니다.
인코딩과 복호를 왕복한다
'ABCD'는 0|10|110|111, 즉 010110111입니다. 복호할 때 첫 0에서 A를 읽고 루트로 돌아갑니다. 다음 10에서 B, 다음 110에서 C, 다음 111에서 D를 얻습니다. 잎에 못 도달한 상태로 비트열이 끝나면 정상 메시지라고 처리하면 안 됩니다.
허프만은 정해진 문자 빈도에 대한 이진 접두어 코드의 가중 길이를 최소화합니다. 문맥을 함께 압축하는 모든 압축 방식보다 항상 좋다는 뜻은 아닙니다. 한 종류 문자만 있는 경우 빈 코드와 길이 정보의 처리 등 별도 형식 약속도 필요합니다.
스스로 풀어보기
문제 1. 위 코드에서 'DABA'를 인코딩하고 총 길이를 구하세요.
풀이: 111|0|10|0을 이어 1110100이며 길이는 3+1+2+1=7입니다. 문자 사이의 구분자는 설명용이고 실제 비트열에는 저장하지 않습니다.
문제 2. A=0,B=01,C=11은 접두어 없는 코드인가요? 어떤 코드가 조건을 깨나요?
풀이: 아닙니다. A의 0이 B의 01의 접두어입니다. 문자에 도달해도 더 읽어 B가 될 가능성이 있어 즉시 복호 규칙을 사용할 수 없습니다. 코드마다 비트가 서로 다르다는 조건보다 접두어 조건이 더 강합니다.
문제 3. 빈도 X=5,Y=2,Z=1에 대한 허프만 트리를 직접 만드세요. 가능한 코드 하나, 메시지 전체의 비트 수와 평균 길이를 구하고 고정 2비트 코드와 비교하세요.
힌트: 현재 가장 작은 두 빈도를 합병한 뒤, 새 부모의 합을 다른 빈도와 다시 비교합니다. 잎의 빈도에 깊이를 곱합니다.
풀이: Z=1과 Y=2를 먼저 합쳐 부모 3을 만듭니다. 현재 두 값 3과 X=5를 합쳐 루트 8을 만듭니다. 루트 왼쪽에 X, 오른쪽에 합병 노드를 놓고 그 노드 왼쪽에 Y, 오른쪽에 Z를 놓으면 X=0,Y=10,Z=11입니다. 접두어가 되는 잎 코드는 없습니다. X의 길이는 1, Y와 Z의 길이는 2라서 전체 길이는 5×1+2×2+1×2=11비트, 평균은 11/8=1.375비트입니다. 고정 2비트 코드는 8×2=16비트이므로 본문 데이터는 5비트 줄어듭니다. 코드표의 전송 비용은 이 비교에 포함하지 않았습니다. 합병 비용 3+8=11도 가중 길이와 같아 검산할 수 있습니다. 좌우를 바꾼 다른 비트 코드도 길이가 같으면 정답입니다.
중간 합의 빈도가 원래 빈도 합과 같은지 매 단계 확인하세요. 평균 길이의 계산은 기댓값으로 연결됩니다.