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

1. 호프만 부호화

  ㅇ 출현 빈도수에 따라, 코드 길이를 다르게 대응
     - 빈도수가 높은 심볼에는, 짧은 코드를 대응
     - 빈도수가 낮은 심볼에는, 긴 코드를 대응 

  ㅇ 결국, 필요한 전체 공간을 최소화시키는 가변길이 부호화 방식 임

  ㅇ 또한, 전체적인 데이터 길이가 짧아지므로 데이터 압축 기법이기도 함


2. 호프만 부호화 특징

  ㅇ 무손실 압축에 사용되는 엔트로피 부호화의 일종
     - 평균코드길이가 소스의 엔트로피에 근접함

  ㅇ 심볼의 출현빈도에 따라 다른 길이의 코드(부호어)를 부여함
     - 적게 출현하는 심볼일수록 더 긴 코드, 자주 발생할수록 더 짧은 코드를 할당

  ㅇ 심볼의 출현빈도에 따라 접두사코드(prefix code)를 만들어내는 알고리즘
     - 주어진 빈도에 따라 항상 최적의 접두사코드를 만들어내나,
       사전에 각 심볼의 발생확률을 미리알고 모델링되어 있어야 함

  ㅇ 단점
     - 코드 길이가 가변이 되므로 수신측에서의 복호화 방식이 복잡해짐
     - 전송 오류가 발생되면 다음 데이타까지 영향을 받게 됨

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


3. 호프만 부호화 알고리즘
 
  ㅇ 감축(축소) 단계
     - 심볼 발생 확률이 큰 것부터 작은 것으로 확률 크기순으로 열거 
     - r개 심볼들의 확률들을 부분적으로 더해가며 다시 확률 크기순으로 열거
     - 마지막까지 계속

  ㅇ 확장 단계
     - 감축단계의 마지막으로 남아있던 r개 심볼에 코드알파벳을 할당하며 부호어 생성

  ㅇ 例)