> 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는 주로 역사적·교육적 용도로 쓰입니다. 그럼에도 불구하고 압축 알고리즘의 기본 개념을 이해하는 데 매우 유용합니다.