Huffman Code

  • 압축 알고리즘 중 하나, 데이터를 더 적은 용량으로 만드는 것
  • 요점은, 자주 나오는 문자에는 짧은 비트를, 조금 나오는 문자에는 긴 비트를 할당
  • AABBAC라는 문자열의 경우 A – 3번 B – 2번 C – 1번이므로 A에는 0, B는 10, C는 11을 부여하면 문자열이 001010011로 바뀜
  • 원래 문자열은 6글자로 48bit가 사용되지만, 압축된 코드는 9bit로

[작동 방법]

  1. 빈도수 검사
  2. 빈도수가 작은 낮은 두 문자(또는 그룹) 선택
  3. 고른 두 개의 문자를 하나의 그룹으로 묶어 줌. 새로운 그룹의 빈도수는 묶은 두 그룹 빈도수 합. 묶을 때 한쪽엔 0 다른쪽엔 1을 배정하는데 이를 이진 트리의 Left, Right 자식으로 표현 해 줄 수 있음
  4. 남은 그룹이 2개 이상이면 다시 2번으로

ex) A : 3  , B : 4, C : 5, D: 4, E: 8

A(3), B(4) 의 빈도를 더한 7을 ID로 노드를 생성해 재귀적으로 이진 트리를 만들어줌

[최적 증명]

  1. 허프만코드 과정 중 빈도수가 가장 낮은 두 개의 그룹은 트리상의 레벨(자식 노드 가는 길이)이 가장 크다
  2. 허프만 코드 과정 중 빈도수가 가장 작은 두 문자를 합친 것과 합치기 전의 최적해는 같다.
    합치기 전 x,y 합친 후 z라 할때 f(x) * x level + f(y) * y level 이 합치기전 최적해 구하는 것이고
    (f(x)+f(y))*z level 이 합친 후 구하는 것인데 x level = y level 이고 z level = x level -1이므로
    (f(x)+f(y))(x -1) level = (f(x) +f(y)) * x level – (f(x) +f(y)) 인데 – 뒤 항은 상수이므로 합치기 전과 마찬가지 최적해를 구하면 됨
  3. 정리 1,2에 의해 허프만 코드는 최적의 방법임이 자명

 

It's only fair to share...Share on Facebook
Facebook
Share on Tumblr
Tumblr
Share on Google+
Google+
Tweet about this on Twitter
Twitter
Email this to someone
email
Musicals, Travel, Photo, Coding, English, Cat