Huffman Code, Huffman Coding   호프만 코드, 호프만 부호, 호프만 부호화, 호프만 코딩

1. 호프만 부호화

  ㅇ 출현 빈도(확률)에 따라, 코드 길이를 다르게 대응하는, 가변길이 부호화 (VLC) 방식
     - 자주 나타나는 심볼 → 짧은 코드를 대응
     - 드물게 나타나는 심볼 → 긴 코드를 대응

  ㅇ 따라서, 필요한 전체 데이터 길이(저장 공간, 전송 비트 수)가 짧아지므로, 
     - 데이터 압축 기법이기도 함

  ※ 1952년 D.A. Huffman(1925~1999)가 제안
     - 논문 : `A method for the construction of minimum-redundancy codes`


2. 호프만 부호화 특징

  ㅇ 부호 유형	:  무손실 압축용 엔트로피 부호화의 일종

  ㅇ 평균 코드 길이  :  소스의 엔트로피에 근접

  ㅇ 코드 구조  :  접두사 코드 (Prefix Code)
     — (접두사 코드 : 어떤 부호도 다른 부호의 접두어가 되지 않음)
        . 단, 주어진 빈도에 따라 항상 최적의 접두사코드를 만들어내나,
        . 사전에 각 심볼의 발생 확률을 미리알고 모델링되어 있어야 함
  
  ㅇ 최적성  :  주어진 확률모델(심볼별 발생 확률)이 알려져 있을 때, 항상 최적 코드 생성

  ㅇ 단점
     - 가변길이 부호화로 복호화가 다소 복잡
     - 전송 오류 시, 이후 데이터까지 영향 가능


3. 호프만 부호화 알고리즘

  ㅇ 감축(축소) 단계 (Reduction)
     - 각 심볼의 발생 확률(또는 빈도)을 계산
     - 심볼 발생 확률 크기순으로 열거 
     - 확률이 가장 작은 두 심볼을 선택하여 하나로 묶고, 그들의 확률을 더함
     - 새로 만들어진 노드를 포함하여, 다시 확률 크기순으로 정렬
     - 노드가 하나만 남을 때까지 반복.
     * 이 과정을 통해 호프만 트리 (Huffman Tree) 가 구성됨
 
  ㅇ 확장 단계 (Assignment)
     - 트리의 루트 노드(root)에서 시작
     - 왼쪽 가지에 0, 오른쪽 가지에 1 (또는 반대로도 가능) 부여
     - 리프 노드(leaf)까지 내려가며, 각 심볼에 대한 코드어(코드알파벳) 생성


4. 호프만 부호화 例)

    

  ㅇ 평균 코드 길이 = 0.4 x 1 + 0.2 x 2 + 0.2 x 3 + 0.1 x 4 + 0.1 x 4 = 2.2 비트/심볼
  ㅇ 엔트로피(≈ 2.12 비트)에 매우 근접 → 효율적 부호화
     - 엔트로피 식  :  {# H(X) = − \sum_i ​p_i ​\log_2 ​p_i ​#}
        . H(X) = - 0.4 log₂0.4 - 0.2 log₂0.2 x 2  - 0.1 log₂0.1 x 2 ≈ 2.12