> shannon | fano | entropy <
// Shannon-Fano – 데이터 압축을 위한 상향식 엔트로피 부호화
엔트로피 기반
정보 이론을 사용하여 효율적인 가변 길이 코드를 생성합니다.
탑다운 방식
비슷한 확률을 가진 심볼 그룹으로 재귀적으로 분할합니다.
역사적인 알고리즘
여러 현대 압축 알고리즘에 영향을 준 선구적인 방법입니다.
>> 기술 정보
Shannon-Fano 동작 원리:
Shannon-Fano 부호화는 심볼을 빈도 순으로 정렬한 뒤, 전체 확률이 최대한 비슷해지도록 두 그룹으로 재귀적으로 나눕니다. 각 분할마다 코드에 비트 하나가 추가됩니다(왼쪽 그룹에는 0, 오른쪽 그룹에는 1). 결과적으로 가변 길이의 프리픽스 코드 집합이 만들어집니다.
인코딩 예시:
텍스트: "AAABBCD" 빈도: A:3, B:2, C:1, D:1 분할: [A] | [B,C,D] 코드: A: 0 B: 10 C: 110 D: 111 인코딩 결과: 0 0 0 10 10 110 111
Shannon-Fano를 사용할 이유:
- >구현이 간단함
- >좋은 압축 비율
- >역사적 중요성
- >교육용으로 유용함
- >프리픽스 코드를 생성
>> 자주 묻는 질문
Shannon-Fano 부호화란 무엇인가요?
Shannon-Fano 부호화는 1940년대에 Claude Shannon과 Robert Fano가 개발한 엔트로피 부호화 기법입니다. 심볼의 확률에 기반한 가변 길이 코드를 사용하는 가장 초기의 알고리즘 중 하나입니다.
Shannon-Fano와 Huffman의 차이는?
두 알고리즘 모두 가변 길이 코드를 생성하지만, Huffman 부호는 최적이며 평균 코드 길이를 최소화합니다. Shannon-Fano는 더 단순하지만 코드가 약간 길어질 수 있습니다. Huffman은 트리를 아래에서 위로 구성하고, Shannon-Fano는 위에서 아래로 구성합니다.
심볼 분할은 어떻게 동작하나요?
심볼을 빈도 순으로 정렬한 뒤, 두 그룹의 전체 확률이 최대한 비슷해지도록 나눕니다. 이 과정을 각 그룹에 대해 재귀적으로 반복하여, 결국 각 그룹에 하나의 심볼만 남을 때까지 진행됩니다.
지금도 Shannon-Fano가 사용되나요?
실제 시스템에서는 최적성을 보장하는 Huffman 부호화가 대부분 사용되며, Shannon-Fano는 주로 역사적·교육적 용도로 쓰입니다. 그럼에도 불구하고 압축 알고리즘의 기본 개념을 이해하는 데 매우 유용합니다.
// 계산 예시
| Symbol | Freq | Code | Bits |
|---|---|---|---|
| A | 15 | 00 | 2 |
| B | 7 | 01 | 2 |
| C | 6 | 10 | 2 |
| D | 6 | 110 | 3 |
| E | 5 | 111 | 3 |
// 코드 예제
Frequencies A=15 B=7 C=6 D=6 E=5 (39 symbols)
1. Sort symbols by frequency (descending).
2. Split the list where the two halves' totals are closest:
{A,B}=22 | {C,D,E}=17 -> first bit 0 / 1
3. Recurse on each half until single symbols remain:
{A}|{B} -> 00, 01 {C}|{D,E} -> 10, 11.. then {D}|{E} -> 110, 111
Total 15*2 + 7*2 + 6*2 + 6*3 + 5*3 = 89 bits
Huffman on the same data: A=1 bit, others 3 bits -> 87 bits
>> 더 많은 질문
Q: Shannon-Fano는 Huffman과 어떻게 다른가요?
A: Shannon-Fano는 정렬된 기호 목록을 위에서 아래로, 빈도 합이 최대한 같은 두 부분으로 나눕니다. Huffman은 가장 드문 기호를 합쳐 아래에서 위로 트리를 만듭니다. Huffman은 최적임이 증명되었지만 Shannon-Fano는 항상 그렇지 않습니다.
Q: Shannon-Fano는 항상 최적인가요?
A: 아닙니다. 예에서는 Huffman의 87비트보다 많은 89비트가 필요합니다. 둘 다 접두어 없는 코드를 만들지만 Shannon-Fano의 분할 규칙은 불리한 분할을 고를 수 있습니다.
Q: Shannon-Fano는 어디에 쓰이나요?
A: 주로 역사적·교육적 방법입니다(Claude Shannon과 Robert Fano, 1948/49). ZIP의 IMPLODE 알고리즘에 변형이 있고 현대 압축기는 Huffman이나 산술 부호화를 씁니다.