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

(2019-12-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. 연속 길이 부호화
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
    1.   비디오
    2.   오디오
    3.   멀티미디어
    4.   방송
    5.   디스플레이
    6.   조명
    7.   정보이론/코딩
      1.   정보이론
      2.   코드이론
      3.   부호화
      4.   소스부호화
        1.   소스부호화 (기초)
          1.   1. 소스 부호화
              2. 고정 길이 부호
              3. 가변 길이 부호(엔트로피 부호화)
              4. 호프만 부호
              5. 산술 부호화
              6. LZW 부호화
              7. 연속 길이 부호화
        2.   영상 부호화
        3.   오디오 부호화
      5.   채널부호화
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
  8.   공업일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

 
        최근수정     요약목록     참고문헌