허프만과 인코딩-디코딩 (Huffman Tree, Huffman-Compressor)

이번에 한 학생에게 허프만 알고리즘을 설명하면서 관련된 짧은 개념을 정리하고자 한다.

누군가에게는 소중한 읽을거리가 되기를 바란다.

 

허프만 부호화 코드는 널리 알려진 가변길이 무손실 압축 방법중 하나이다.

굳이 엔트로피 이야기라던지 멀리 갈 필요는 없다. (알면 정말 좋지만 오늘은 아껴두겠다.)

정말 간단한 논리로 움직인다.

 

---

 

1. 가변길이 VS 고정길이

 

허프만 코드는 가변길이(variable length)라고 한다. 사실 비트열을 나열하였을때 분석이 용이한 것은 고정길이(fix length)일 것이다.

혹시나 이해가 쉽지 않은 이들을 위해 해당 단락을 준비했다.

 

AABAAAB 

 

위와 같은 내용이 있다고 하자.

 

데이터열은 위와같이 문자가 될 수도 있고, 그림이나 신호들의 기호화된 모습으로 나타날 수 있다.

이러한 네이티브한 데이터를 RAW 데이터라 하고, 이를 컴퓨터가 이해할 수 있는 0과 1의 모습으로 변형하는 과정을 인코딩이라한다. 사실 인코딩은 0과 1의 값으로만 바뀌는 이야기는 아니다. (3진수를 쓰는 컴퓨터에서의 인코딩은 3진수로 바뀌는 것을 의미하지 0과 1로 바뀌는것을 인코딩이라고 무조건 명명하지는 않는다.) 인코딩은 대상이 이해할 수 있는 개념으로 바꿔주는것이라 생각하면 된다. 그리고 디코딩은 이렇게 쓰여진 인코딩정보만을 가지고 RAW 데이터로 복원해가는 과정이다.

 

데이터의 송수신 및 저장을 위해서는 다소 다양한 방법의 가공이 필요할 수 있다.

그리고 데이터를 저장하기 위해서는 반드시 압축을 사용해야만 한다.

 

해당내용을 압축하기 위해서는 다양한 방법이 필요할 수 있다.

내용을 어떤 방법을 쓰든지 보다 작은 파일로 만드는 기술을 압축이라 하고, 이때 한번 압축한 데이터를 100프로 완벽하게 다시 복원하는 것을 무손실, 약간 깨지거나 흐려지거나 완벽히 복원할 수 없는 것을 손실 압축이라 한다. 

 

간단한 설명

위 이미지는 예시이다.

예를 들어 문자표현을 위한 고정길이를 5개로 잡는다면, 위와같이 A라는 문자를 00000 으로 표기할 수도 있다.

반면에 가변길이에서는 A라는 문자를 0 하나로만 표기할 수도 있다.

문제는 다른 문자를 표기하는 방법이다.

B라는 문자를 고정길이에서는 A와 다른 값으로 어떤값이든 주면 된다.

 

가변길이 역시 어떤 값이든 주면 될까?

 

복호화 시점을 고려하여 가변길이는 다양한 방법으로 표현되고 있다.

허프만 코드에서는 앞비트에서부터 순차적으로 읽었을때, 동일하게 읽혀서 오해를 사는 코드는 추가될 수 없다.

말이 어려운데 간단하게 보면 이렇다.

 

A -> 0

으로 지정하였다. 따라서

B -> 0 (X)

올 수 없다. 왜냐면 A랑 겹치니까 구분이 안된다.

B -> 01 (X)

올 수 없다. 왜냐면 가변길이니까 첫문자 읽으면 A인지 B의 첫번째 문자일지 오해를 살 수 있다.

B -> 00 (X)

역시 올 수 없다. 왜냐면 A 가 두개인지 B 인지 확실한 구분이 안된다.

 

따라서 허프만 코드에서 순차적으로 비트열을 읽었을때, A인지 B일지 오해를 사는 코드는 없도록 짜야한다.

때문에 전이진트리를 이용하여 작성을 하며, 동시에 복호화를 위해 별도의 헤더를 만들어야 한다.

 

---

 

2. Huffman Tree

 

이미 허프만이라고만 쳐도 다양한 블로그나 심지어는 유투브에서도 해당 내용을 확인할 수가 있었다.

그만큼 많은 곳에서 활용이 되는 압축 방식이고 중요하다.

전문적으로 강의를 하는 사람은 아니며 말주변도 별로 없으므로 이부분은 재미로 봐주기를 바란다.

 

위 이야기처럼, 허프만은 고민을 했을 것이다.

높은 압축률과 함께 코드간 오해로 인해 파일손상이 생기지 않는 그런 압축방법을 고민했을 것이다.

 

당연한 이야기겠지만 압축률을 올리려면 파일의 크기를 줄여야 한다.

파일의 크기를 줄이기 위해서는 다양한 방법이 있겠지만, 가장 자주 발견되는 데이터를 제거하거나 가장 크기가 작은 비트열로 치환하는 것이 있을 수 있다. 허프만이 채택한 방법이 바로 이것이다.

 

말이 어려워서 혼란이 올 수 있다.

간단히 보자.

 

AAAAAAABAAAAACAAAAAA

 

위와 같은 데이터가 있다.

B 하나 C 하나 빼면 A 뿐이다.

너무 많다.

A 를 0 으로 B 를 10 으로 C 를 11 로 보자.

 

AAAAAAABAAAAACAAAAAA

0000000 10 00000 11 000000

 

이렇게 된다. 고정길이나 다른문자를 줄이는 것에 비해 인코딩 비트열이 적은 것을 알 수가 있다.

(시간이 있다면 직접 대입해 보는 것을 추천한다.)

뭐 압축률이 최고까지는 아니더라도 범용적으로 최적의 레벨까지 뽑아준다.

(최고가 될 수 없는 이유는 빈도수가 위처럼 다른 데이터가 아니라 거의 일정한 수준이라면 다른 방법이 더 나을 수 있기 때문.)

증명은 허프만 박사님께서 박사학위를 내면서 논문으로 제출하였으니 참고하고 싶다면 해도 좋다.

 

위와 같이 빈도수가 높은 문자를 추출하면서 동시에 앞서 문자와 혼선을 빚어내지는 않는 방법을 허프만트리(Huffman-Tree), 허프만 부호화 알고리즘(Huffman-Code Algorithm) 정도로 부를 수 있다.

 

priortyQueue PQ;

while (PQ.size() > 1) {
  Node p = PQ.remove();
  Node q = PQ.remove();
  Node newNode = new Node();
  newNode.left = p;
  newNode.right = q;
  newNode.frequency = p.frequency + q.frequency;
  PQ.insert(newNode);
}

Node root = PQ.remove();

간단히 표현하자면 위처럼 나타낼 수 있다.

최소 우선순위 큐(PQ)에 입력데이터의 문자별 빈도수가 포함된 Node 들이 세팅되어 있을 때, 

큐의 최솟값 두개를 자식노드로 가지는 새로운 노드를 PQ 에 입력함으로써 

문자 출현 빈도수별 최소경로를 비트열로서 얻을 수 있게 된다.

(세팅되어 있다는 가정하에 O(N logN)의 시간복잡도를 갖게 된다.)

 

위 알고리즘에서 우선순위 큐가 아니라면, 앞서 이야기한 바와 같이 비트열로 해석(인코딩)한 데이터를 다시 복호화할 때, 문자간 구분이 모호하여 잘못 해석할 여지가 생겨난다.

 

우선순위 큐는 자바와 C# 에서는 Comparable 같은 비교 인터페이스를 상속함으로써 간편하게 작성할 수 있다. STL 제공이 싫다, 나는 나만의 길을 가겠다 하면 큐를 상속받아 삽입-삭제 부분에 비교를 할 수도 있기는 하다.

 

어쨋든 허프만트리는 최종적으로 큐를 모두 비우게 되고, root 노드만을 반환하게 된다.

빈도수가 가장 많았던 노드는 우선순위큐에 의해 나중에 호출되므로 자식노드를 가질 수 없고 리프노드가 된다.

각 문자들은 중간 경로 노드가 되는 일이 없다. (당연하다지만 궁금하다면 왜일지 추적해보면 좋다.)

 

+ 추가

허프만 코드는 빈도수가 동일한 값에 대해서는 누가 먼저오고 나중오는 것에 큰 영향을 미치지 않는다.

 

 

---

 

3. 가변길이에서의 헤더파일

 

C++ 에서 구조체를 만들어 보았을 것이다.

굳이 C계열 언어를 다루지 않더라도 클래스를 자주 사용하는 사람이라면, 객체의 정의를 한다는 것을 알 수 있다.

다만, 우리가 사용하는 오브젝트가 int 라던지 string 처럼 MSDN 이나 oracle 같은 단체가 정의한 4byte, 2byte 같은 고정길이 일 수도 있고, 재정의된 가변길이 일 수 있음에 유의해야 한다.

 

하나의 파일을 구성하는 요소에는 필연적으로 헤더가 발생하게 된다.

PE 파일이나 화상파일(정지영상/동영상), 음성파일이나 심지어는 html 파일들도...

헤더는 해당 파일이 무엇이며 크기는 어느정도가 되고 내부 데이터는 어떤방식으로 쓰여졌는지 등 기본적으로 파일을 읽기 위한 정보를 기록한다. 뭐 일부에서는 이를 파일의 스펙이라고 말하기도 한다. (JPEG 의 스펙!, MPEG-4 의 스펙! 등)

 

허프만코드를 출력하는 많은 학생들 역시 파일쓰기는 아무래도 텍스트문서까지 였을 것이다.

영상파일의 헤더를 직접 열어보거나 네트워크 통신 프로토콜을 직접 설계하게 된다면, 헤더가 얼마나 중요한지 교수님께서 얼마나 좋은 것들을 알려주셨는지 감사하게 될 것이다.

 

특별히 정해진 방식은 없으나 헤더영역과 데이터영역을 구분지을 방법이 있어야 하며, 헤더에는 반드시 사용한 문자와 매핑된 가변길이의 문자코드가 함께 작성되어야 한다. 그래야 복호화가 가능하다. 정리하면 다음과 같다.

 

 - 헤더길이 (대게 프로토콜도 많이 쓴다)

 - 문자코드 (ex A의 비트열)

 - 매핑되는 가변길이 문자코드 (ex A와 매핑되는 치환코드 0)

 

 

---

4. 인코딩

 

허프만에서는 인코딩이 치환이라는 개념으로 볼 수 있다.

앞서 압축을 위한 허프만트리를 이용하여 전이진트리를 구현하여 문자별 빈도수에 따른 코드를 생성했고, 바로 위에서는 문자별 코드를 헤더에 정의함으로써 복호화하기위한 정보를 마련했다.

 

이젠 정말 데이터 파싱뿐이다.

(대충 이제부턴 정말 공부뿐이야 짤)

 

AAAAAAABAAAAACAAAAAA

0000000100000011000000

 

앞서 쓴 내용처럼, 허프만트리를 통해 구한 코드를 순차적으로 문자와 치환한다.

 

---

 

5. 디코딩

 

순 0과 1뿐인 데이터 조각을 디코딩 한다는 것은 쉽지가 않다.

그러니 헤더의 기본 정보를 알아야 하는 것이다.

 

헤더에서 정의한 가장 첫정보가 헤더길이 같은 헤더와 데이터간 경계에 대한 구분자였다면,

적정 길이를 읽어들여서 얼마나 더 읽어야 할지를 알아낼 수 있게 된다.

가변코드가 발생할때마다 현재위치를 기점으로 얼마나 읽어야 할지를 알려주는 방법이 있고, 허프만코드는 순차적으로 문자를 읽어갈때 서로 오해할 이진 데이터열이 없기에 굳이 얼마나 더 읽어야할지 알 필요가 없다. 헤더에서 정의된 문자코드를 보고 데이터열에서 순차적으로 치환해 나가면 된다. 다른방법도 있겠지만, 헤더만 잘 읽어두면 데이터 영역에서는 O(N)번만 순회함으로써 문제를 해결할 수 있게 된다.

 

 

 

읽을거리

http://dongseo.ac.kr/~dkkang/ImageProcessing2011Spring/ch14.pdf

불러오는 중입니다...