[Algorithm] 허프만 압축

💡허프만 압축 아이디어

• 파일에 빈번히 나타나는 문자 -> 짧은 이진코드 할당
• 드물게 나타나는 문자 -> 긴 이진코드 할당

 

💡접두부 특성 (prefixx property)

• 허프만 압축방법으로 변환시킨 문자 코드들 사이에 존재
• 각문자에 할당된 이진 코드는 어떤 다른 문자에 할당된 이진코드의 접두부가 되지 않는다를 의미
• 접두부 특성의 장점은 코드와 코드 사이를 구분할 특별한 코드가 필요 없다는 것!

 

💡그래서, 허프만 압축은 뭘까?

• 입력파일에 대해 각문자의 출현 빈도수에 기반을 둔 이진트리를 만들어서, 각 문자에 이진코드를 할당
• 이러한 이진코드를 허프만 코드라고 한다.

 

 

💡의사코드

• 입력 : 입력 파일의 n개의 문자에 대한 각각의 빈도 수
• 출력 : 허프만 트리

1. 각 문자당 노드를 만들고, 그 문자의 빈도수를 노드에 저장
2. n개의 노드의 빈도수에 대해 우선순위 큐 Q를 만든다.
3. while(Q에 있는 노드 수 >=2){
4. 	빈도수가 가장 작은 2개의 노드 (A,B)를 Q에서 제거
5. 	새 노드 N을 만들고, A와 B를 N의 자식 노드로 만든다.
6. 	N의 빈도수 = A의 빈도수 + B의 빈도수
7. 	노드 N을 Q에 삽입한다.
}
8. return //허프만 트리의 루트를 리턴

 

💡예제 실습

• 할당된 코드들을 보면, 가장 빈도수가 높은 'A'가 가장 짧은 코드를 가지고, 따라서 루트의 자식이 되어 있고, 빈도수가 낮은 문자는 루트에서 멀리 떨어지게되어 긴 코드를 가진다.
• 접두부 특성을 가지고 있다.
• 파일 압축률 
  • 압축된 파일의 크기의 bit 수 : sum(문자의 빈도수 x 비트 수) = 1,620
  • 아스키 코드로 된 파일 크기 bit 수 : sum(문자의 빈도수) x 8 = 7,440
  • 21.8% -> 약 1/5 크기로 압축됨

 

 

⏰시간복잡도

• Line 1 : n개의 노드를 만들고, 각 빈도수를 노드에 저장하므로 O(n)시간
• Line2 : 우선순위 큐 만들기 -> 힙 자료구조 사용 : O(n) 시간
• Line3~7 : 최소 빈도수를 가진 노드 2개를 Q에서 제거하는 힙의 삭제 연산과 새 노드를 Q에 삽입하는 연산을 수행 O(log n) (각 층의 수만큼!)
  • while 루프는 (n-1)번 반복 : 루프가 1번 수행될 때마다 Q에서 2개의 노드를 제거하고 1개를 Q에 추가하기 떄문에
  • (n-1)xO(logn) : O(nlogn)
• Line 8 : 트리의 루트를 리턴하는 것이므로 O(1) 시간
• O(n) + O(n) + O(nlogn) + O(1) = O(nlogn)

 

 

➰응용

• 팩스, 대용량 데이터 저장, 멀티미디어, MP3 압축 등에 활용
• 정보 이론 분야에서 엔트로피를 계산하는데 활용, 이는 자료의 불특정성을 분석하고 예측하는데 이용됨.

---

Reference

서울과학기술대학교 컴퓨터공학과 알고리즘 수업