[DS] Huffman Coding Tree (허프만 코딩 트리)

# Huffman Coding Tree

- 데이터 문자의 출현 빈도에 따라 가변 길이의 부호를 사용하는 압축 알고리즘

  > 출현 빈도가 높은 문자가 짧은 부호로 변환됨으로써 전체 문장의 데이터 비트 수는 줄어들게 됨

- 장점: 공간의 효율성을 높일 수 있음

- 단점: 문장을 구성하는 문자의 빈도 횟수가 비슷하다면 크게 효율적이지 못함

- 문장 예시: "time and tide wait for no man"

① 각 문자의 출현 빈도를 출현 빈도 테이블로 나타냄

1.1 문자의 출현 빈도

② 각 문자를 출현 빈도에 따라 정렬함

1.2 오름차순으로 정렬

 

③ 각 문자와 출현 빈도를 계층적 자료구조 트리의 단말노드로 지정한 후 출현 빈도가 낮은 것부터 2개씩 짝짓는 과정을 합이 증가하는 순서로 반복

  > 허프만 코딩트리를 사용하여 각 문자를 가변 길이 코드로 변환

  > 트리의 최상위 루트에서 단말 노드까지 각 경로에 0또는 1의 부호를 부여

     → 일반적으로 왼쪽 자식노드를 0, 오른쪽 자식노드를 1로 지정

  > 위와 같은 방법으로 각 문자에 허프만 코드를 부여할 수 있음

  > ex) 10101010110 : not / 0110011100100011 : time

  > 규칙 

     - 경우의 수는 여러개 나올 수 있음

     - 2개씩 짝 짓는 과정은 항상 합이 증가되는 방향으로 이루어져야 함

1.3 허프만 코딩 트리

 

④ 문자의 출현 빈도와 비트 수

- 허프만 코딩 이전 예시 문장을 표현하기 위한 공간: 29 char → 29 bytes → 232 bits 필요

- 허프만 코딩 이후: Sum(Freq*bits) = 100 bits

  > 허프만 코딩 이전보다 57%의 공간을 절약할 수 있음

1.4 문자의 출현 빈도와 비트 수

 

 

# Huffman Coding Tree in C

- 소스코드: https://gist.github.com/fpdjsns/b82d2ba881ab011f0fe001bb395fa282

--> 여기 참고해서 트리 공부한 후에 나도 구현해보기 !! 내용은 쉬운 듯 한데 막상 구현하면 어려울듯..ㅎㅎ