[알고리즘] 그리디 알고리즘 - 허프만 압축

이전 글에서 그리디 알고리즘에 대한 개념과 그에 대한 대표적인 예시를 다뤘습니다.

 

오늘은 그에 이어서 허프만 압축에 대해서 다뤄보겠습니다.

 

 

 

   허프만 압축

우리는 파일을 작성한 후에 저장하거나 전송할 때 크기를 압축하고, 필요할 떄 원래의 파일로 변환할 수 있으면 메모리 공간을 효율적으로 사용할 수 있으며 파일 전송 시간을 단축할 수 있을 것입니다.

 

이러한 파일의 크기를 줄이는 방법을 파일 압축이라고 하며 파일 압축의 방법 중 한 가지인 허프만 압축을 소개합니다.

 

허프만 압축은 파일에 빈번히 나타나는 문자에는 짧은 이진 코드를 할당하고, 드물게 나타나는 문자에는 긴 이진 코드를 할당하는 방식으로 진행됩니다.

 

허프만 압축 방법으로 변환시킨 문자 코드들 사이에는 접두부 특성이 존재합니다.

 

접두부 특성이란?

 

접두부 특성이란 각 문자에 할당된 이진 코드는 어떤 다른 문자에 할당된 이진 코드의 접두부가 되지 않는 특성을 말합니다.

 

예를 들어 문자 'a'에 할당된 코드를 '101'이라고 해봅시다. 그렇게 된다면 'a'를 제외한 모든 다른 문자의 코드는 '101'로 시작되지 않으며 '1'이나 '10'이 아니게 됩니다.

 

접두부 특성을 갖고있게 된다면, 각 이진코드 사이에 구분할 기호가 필요 없다는 것입니다.

 

 

그럼 우리는 각 문자에 대한 허프만 코드를 생성하고, 허프만 압축을 진행하는 방법을 알아봅시다.

 

어떤 문서의 각 문자의 빈도수가 아래와 같다고 해봅시다.

 

우리는 각 문자와 빈도수를 저장하는 노드를 만들고, 해당 노드를 담을 수 있는 우선순위 큐에 넣어줍니다. 우선순위 큐는 빈도수가 가장 낮은 노드를 우선적으로 내보냅니다.

 

가장 먼저는 노드 2개를 pop합니다. 빈도수가 낮은 노드부터 나오게 되니 90인 T와 120인 G가 나오게 됩니다.

 

이렇게 뽑아낸 두 개의 노드로 트리를 생성합니다. T와 G는 자식 노드가 되고, 해당 자식을 갖는 부모 노드를 생성하게 되는데, 그 노드는 자식 노드 2개의 빈도수를 합한 빈도수를 갖는 노드로 만들어줍니다.

 

즉, 아래와 같은 형태로 트리가 생성되게 됩니다. 여기서 만드는 트리의 자식 노드의 왼쪽이 작은 빈도수를 갖게 만들어줍니다.

 

이제 210 노드를 다시 큐에 넣어줍니다.

 

 

이제 또 2개를 꺼내주고 트리를 생성합니다.

 

위와 같은 트리가 생성되고, 가장 최상단의 노드를 다시 큐에 넣어줍니다.

 

 

이제 다시 두 노드를 pop한 후 트리를 만들어줍니다. 이제 최종적인 트리가 완성되겠군요!!

 

이제 우리는 최종 트리를 얻었습니다. 그럼 이제 각 문자에 이진코드를 부여하는 방법을 알아봅시다.

 

 

트리를 보면 리프노드에만 우리가 큐에 넣은 문자들이 있음을 알 수 있습니다. 따라서 우리는 리프노드로 갈 때까지 이진 코드를 한 비트씩 부여합니다.

 

루트 노드를 시작으로 왼쪽으로 간다면 0을 붙여주고, 오른쪽으로 갈 때는 1을 붙여주는 방식으로 진행합니다.

 

그러면 아래와 같은 코드를 각 문자는 갖게 됩니다.

 

자, 이제 각 문자별로 부여된 이진 코드로 나타나진 코드를 복호화해봅시다.

 

 

이러한 문자열을 허프만 코드를 토대로 복호화해보기 위해, 이진코드별로 쪼개보겠습니다.

 

 

이런 식으로 쪼갤 수 있습니다. 구분자 없이도 알아낼 수 있는 이유는 접두부 특정 덕분입니다.

이제 각 이진코드에 해당하는 문자로 치환하면 아래와 같습니다.

 

   의사코드

해당 알고리즘을 의사코드로 확인해봅시다.

/**
  * @param 입력 파일의 n개의 문자에 대한 각각의 빈도수
  * @return 허프만 트리
  */
  huffmanCoding(){
  	각 문자에 해당하는 노드를 만들고, 그 노드의 빈도수를 노드에 저장함.
    노드의 빈도수에 대해서 우선순위 큐를 만든다.
    
    while(Q.size() >= 2){
    	빈도수가 가장 작은 2개의 노드를 큐에서 제거한다.
        새 노드 N을 만들어서 A와 B를 N의 자식으로 만든다.
        N의 빈도수를 (A의 빈도수) + (B의 빈도수)로 세팅한다.
        노드 N을 큐에 삽입한다.
    }
    
    return Q;
}

 

 

---

오늘은 허프만 압축에 대해서 알아봤습니다. 감사합니다.