#A09_허프만 압축 코딩(그리디 알고리즘)

☆ 기본 압축의 개념(주어진 파일의 크기를 줄이는 방법)

- 파일의 각 문자가 8 bit 아스키 (ASCII) 코드로 저장되면, 그 파일의 bit 수는 8x(파일의 문자 수)

-> 파일의 각 문자는 일반적으로 고정된 크기의 코드로 표현하는 것

 

- 고정된 크기의 코드로 구성된 파일을 저장하거나 전송

-> 파일의 크기를 줄이고, 필요시 원래의 파일로 변환할 수 있으면, 메모리 공간을 효율적으로 사용할 수 있고, 파일 전송 시간을 단축

 

 

 

 

 

★ 허프만 압축

 - 빈번히 나타나는 문자에는 짧은 이진 코드를 할당하고, 드물게 나타나는 문자에는 긴 이진 코드를 할당

 - 출현 빈도수 (문자가 파일에 나타나는 횟수)에 기반을 둔 이진트리를 만들어서, 각 문자에 이진 코드를 할당

 -> 이러한 이진 코드를 '허프만 코드'라고 한다!!!

 

 

ㅇ 접두부 특성(prefix property)

- 각 문자에 할당된 이진 코드는 어떤 다른 문자에 할당된 이진 코드의 접두부(prefix)가 되지 않는다는 것을 의미

  (ex. 문자 ‘a’에 할당된 코드가 ‘101’이라면, 모든 다른 문자의 코드는 ‘101’로 시작되지 않으며 또한 ‘1’이나 ‘10’도 아니다.)

- 장점 : 코드와 코드 사이를 구분할 특별한 코드가 필요 없다.

 

 

 

 

 

 

 

★ 허프만 코드 알고리즘

 

 

 

 

☆ 우선순위 큐(Priority Queue)

- 우선순위를 가진 항목들을 저장하는 큐

- 우선순위가 높은 데이터가 먼저 나가게 됨

- 힙(Hepp)을 이용한 구현

  -> 완전 이진트리

  -> 우선순위 큐를 위해 만들어진 자료구조

우선순위 큐를 위해 만들어진 자료구조

 

 

 

 

☆ 힙(Heep)

 - 더미

 - 완전이진트리

 - 최대 힙, 최소 힙

 

ㅇ 최대 힙(max heap) : 부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전 이진 트리

ㅇ 최소 힙(min heap) : 부모 노드의 키값이 자식 노드의 키값보다 작거나 같은 완전 이진 트리

 

 

☆ 힙의 구현 : 배열을 이용하여 구현

- 완전이진트리 -> 각 노드에 번호를 붙임 -> 배열의 인덱스

 

 

 

 

ㅇ 삽입 연산

 

-> 항상 맨 끝에 저장 후 비교하여 위치를 바꿔줌!!!

 

 

 

ㅇ 삭제 연산

 

 

-> 무조건 가장 아래에 있는 것이 위로 올라가서 비교하여 위치를 바꿔줌

 

 

 

 

★ 허프만 알고리즘 수행 과정

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ㅇ 허프만 코드 생성과정

 

 

 

★ 시간복잡도

 

 

 

★ 응용

- 팩스(FAX), 대용량 데이터 저장, 멀티미디어 (Multimedia), MP3 압축 등에 활용

- 정보 이론 (Information Theory) 분야에서 엔트로피 (Entropy)를 계산하는데 활용