[알고리즘] 허프만 코딩

공부한 날짜: 2021. 11. 09

 

1. 고정길이 코드와 접두어 코드 

-고정길이 코드(fixed length code): 모든 코드의 길이가 똑같은 값을 갖는 코드 체계 

장점은 다루기 쉽다(연산에 편의성이 있다) 

-가변길이 코드: 코드의 길이에 변동이 있음

장점은 저장공간의 절약을 할 수 있다는 것

-접두어코드(Prefix Code): 가변 길이 코드의 한 종류로, 무접두어 코드와 동일어. 

코드 집합의 어느 코드도 다른 코드의 접두어가 되지 않는 코드.

 

2. 허프만 코딩 

:기호의 빈도와 이진트리 개념이 핵심

 

 

+기호의 빈도는 길이가 짧은 접두어 코드를 빈도가 높은 기호에 부여하기 위해 사용한다 -> 저장공간을 아낄 수 있다 

+이진트리는 접두어코드를 표현하는데 사용한다.

+왼쪽 자식 노드는 0, 오른쪽 자식 노드는 1을 나타내고,

+모든기호는 잎노드에만 기록,

+기호의 접두어 코드 : 루트 노드에서부터 잎 노드까지 이르는 경로

 

-압축 과정

ㄱ. 해 선택: 빈도 가장 작은 노드들끼리 연결한다

ㄴ. 실행 가능성 검사: 기호를 가진 노드가 잎 노드인지 확인 

ㄷ. 해 검사: 트리가 최종 트리인지 확인 

 

-압축해제 

ㄱ. 허프만 트리와 압축 해제된 데이터를 담을 버퍼를 준비한다. 루트노드부터 잎노드까지 순회한다

ㄴ. 압축 데이터에 아직 읽지 않은 부분이 남아있으면 잎 노드까지 순회한다

ㄷ. 읽어낸 비트가

0 -> 현재 노드의 왼쪽 자식노드

1-> 오른쪽 자식 노드로 이동.

현재 노드가 잎 노드이면 저장되어 있는 기호를 버퍼에 추가하고 

다시 루트 노드로 이동 

<=> 비트를 읽을 때마다 잎 노드를 만니기 전가지 허프만 트리의 왼쪽/오른쪽으로 노드를 순회하라