// Tunstall 코딩 – 가변 길이에서 고정 길이로의 최적 압축
가변 길이 시퀀스를 고정 길이 코드로 매핑합니다.
기호의 확률 분포를 사용해 사전을 구성합니다.
고정 길이 코드는 단순하고 빠른 디코딩을 가능하게 합니다.
Tunstall 코딩은 가변 길이 시퀀스로 구성된 사전을 만들고, 이를 고정 길이의 이진 코드에 매핑합니다. 단일 기호에서 시작하여, 가장 높은 확률을 가진 시퀀스를 반복적으로 선택하고, 알파벳의 모든 기호를 덧붙여 확장합니다. 이렇게 해서 더 높은 확률을 갖는 시퀀스가 자체 코드워드를 갖는, 가변→고정 길이의 최적 코드가 만들어집니다.
텍스트: 'aabaa', P(a)=0.8, P(b)=0.2 사전 구성 (3비트 코드): 초기: a, b 'a' 확장: aa, ab 'aa' 확장: aaa, aab 'ab' 확장: aba, abb 최종 사전 (8개 코드): aaa → 000 aab → 001 aba → 010 abb → 011 aa → 100 ab → 101 a → 110 b → 111 인코딩: 'aabaa' → 001 100 (aab + aa)
Tunstall 코딩은 입력은 가변 길이, 출력은 고정 길이인 엔트로피 코딩 방식입니다. Huffman(고정→가변)과 달리, Tunstall은 가변 길이 소스 시퀀스를 고정 길이 코드워드에 매핑하므로 일정한 비트레이트가 필요한 응용에 적합합니다.
Huffman: 고정 입력 → 가변 출력 (예: 'a' → '0', 'b' → '10'). Tunstall: 가변 입력 → 고정 출력 (예: 'aa' → '000', 'ab' → '001'). Tunstall은 하드웨어 및 동기화 측면에서 유리하지만, 일반적으로 압축 비율은 약간 낮습니다.
단일 기호에서 시작합니다. 반복적으로 1) 가장 높은 확률을 가진 시퀀스를 찾고, 2) 그것을 제거한 뒤 가능한 모든 1‑기호 확장을 추가하며, 3) 원하는 사전 크기(n비트 코드라면 2^n)에 도달할 때까지 계속합니다.
Tunstall 코딩은 음성 압축, 이미지 코딩 및 고정 출력 속도가 필요한 상황에서 사용됩니다. 특히 가변 길이 코드가 타이밍을 복잡하게 만드는 하드웨어 구현 및 실시간 시스템에서 유용합니다.