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

(2022-04-01)

허프만 코드, 허프만 부호, 허프만 부호화, 허프만 코딩


1. 호프만 부호화

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

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

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


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

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

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

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

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


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

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

  ㅇ 例)
      

소스부호화 (기초)
   1. 소스 부호화   2. 고정 길이 부호   3. 가변 길이 부호(엔트로피 부호화)   4. 호프만 부호   5. 산술 부호화   6. LZW 부호화   7. 연속 길이 부호화  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"