허프만 압축

파일 압축

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

파일의 각 문자는 일반적으로 위와 같이 고정된 크기의 코드로 표현

고정된 크기의 코드로 구성된 파일을 저장하거나 전송할 때 파일의 크기를 줄이고, 필요시 원래의 파일로 변환할 수 있으면, 메모리 공간을 효율적으로 사용할 수 있고, 파일 전송 시간을 단축

허프만 압축

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

즉 문자의 빈도수에 기반을 둔 이진 트리를 만들어서, 각 문자에 이진 코드 할당

이렇게 만들어진 이진 코드 = 허프만 코드

허프만 압축 방법으로 변환시킨 문자 코드들 사이에는 접두부 특성(prefix property)이 존재

🔎 접두부 특성 (prefix property) 🔍

각 문자에 할당된 이진 코드는 어떤 다른 문자에 할당된 이진 코드의 접두부가 되지 X

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

▶ 장점

코드와 코드 사이를 구분할 특별한 코드가 필요 X (1010#111# 에서 '#' 같은 구분자가 필요 X)

 

---

 

입력 파일이 주어지면 그 파일에서 각 문자의 빈도수를 구해서 우선순위 Q 생성

ex) 빈도수 - T:90, C:270, G:120, A:450

참고) 알기 쉬운 알고리즘

 

Q에 남아있는 노드가 1개가 될 때까지 아래의 코드 실행

 

빈도수가 가장 낮은 2개의 노드(T, G)를 Q에서 제거하여 새 노드를 만들고 T와 G를 새로 만든 노드의 자식으로 만듦 (자식으로 만들 때 빈도수가 낮은 노드는 왼쪽 자식으로, 높은 노드는 오른쪽 자식으로 두자고 정함 - 반대도 가능. 다만 섞어서 쓰면 X. 어떤 때는 낮은걸 왼쪽 자식으로, 어떤 때는 높은걸 왼쪽 자식으로.. 이렇게 하면 안 된다는 뜻)

새로 만든 노드의 빈도수 = T의 빈도수 + G의 빈도수

새로 만든 노드를 Q에 삽입

참고) 알기 쉬운 알고리즘

 

...

 

최종적으로 아래와 같이 단 하나의 노드가 Q에 남게 됨

참고) 알기 쉬운 알고리즘

 

이파리(단말) 노드에만 문자가 존재

루트로부터 왼쪽으로 내려가면 '0'을, 오른쪽으로 내려가면 '1'을 부여

∴ 각 이파리에 도달할 때까지의 이진수를 추출 → 문자의 이진 코드

A : '0', T : '100', G : '101', C : '11'

각 문자에 할당된 이진 코드를 보면 빈도수가 높은 문자가 짧은 코드를 가지고, 빈도수가 낮은 문자가 긴 코드를 가지게 됨

참고) 알기 쉬운 알고리즘

 

위에서 얻은 허프만 코드로 압축된 문자 복호화

10110010001110101010100

▶ 101 / 100 / 100 / 0 / 11 / 101 / 0 / 101 / 0 / 100

▶ G T T A C G A G A T

 

 

import heapq

class Entry:
    def __init__(self, freq, value, l, r, code):
        self.frequency = freq   # 빈도 수
        self.word = value       # 글자 자체 (a, b, c, ...)(이파리의 문자)
        self.left = l           # 왼쪽 자식
        self.right = r          # 오른쪽 자식
        self.code = code        # 허프만 코드
      
    # 객체를 빈도수로 비교하기 위해
    # 내 빈도수가 다른 객체의 빈도수보다 작은 걸 리턴
    def __lt__(self, other):    
        return self.frequency < other.frequency
    
    def get_key(self):
        return self.frequency
        
    def get_value(self):
    	return self.word
    
    def get_code(self):
        return self.code
    
    def get_left(self):
        return self.left
    
    def get_right(self):
        return self.right
    
    def set_code(self, code):
        self.code = code
        

def create_huffman_tree(a):
    while len(a) > 1:       # 힙에 1개의 노드만 남을 때까지 반복
        e1 = heapq.heappop(a)   # 힙에서 최소 빈도수 가진 노드 제거하여 e1이 참조
        e2 = heapq.heappop(a)   # 힙에서 최소 빈도수 가진 노드 제거하여 e2가 참조
        n = Entry(e1.get_key() + e2.get_key(),      # e1과 e2의 빈도수의 합
                  e1.get_value() + e2.get_value(),	# string 이어붙이기
                  e1, e2, '')	# e1, e2가 각각 새 노드의 왼쪽, 오른쪽 자식
        heapq.heappush(a, n)    # 새 노드를 힙에 삽입
    return heapq.heappop(a)     # 1개 남은 노드(루트 노드)를 힙에서 제거하며 리턴


# 허프만압축을 통해 문자별 부여되는 이진코드
def update_code(node, dict = None):
    if dict is None:
        dict = {}
        
    if node.get_left() is not None:     # 왼쪽으로 내려가면 0을 붙이면서
        node.get_left().set_code(node.get_code() + '0')
        update_code(node.get_left(), dict)
        
    if node.get_right() is not None:	# 오른쪽으로 내려가면 1을 붙이면서
        node.get_right().set_code(node.get_code() + '1')
        update_code(node.get_right(), dict)
        
    if len(node.get_value()) == 1:		# 이파리이면(문자 1개만 있음), 허프만 코드 출력
    	#print(node.get_value(), ':', node.get_code(), '  ', end='')
        dict[node.get_value()] = node.get_code()
        
    return dict


# 힙 출력
def print_heap(a):
    for i in range(len(a)):
        print(f"[{a[i].get_key()}, {a[i].get_value()}] ", end="")
    print()


# 실행
if __name__ == "__main__":
    data = [Entry(60, 'a', None, None, None),
            Entry(20, 'b', None, None, None),
            Entry(30, 'c', None, None, None),
            Entry(35, 'd', None, None, None),
            Entry(40, 'e', None, None, None),
            Entry(99, 'f', None, None, None)]
    
    heapq.heapify(data)     # data를 heap으로 변환
    
    print('최소 힙:')
    print_heap(data)
    
    print('허프만 코드:')
    tree = create_huffman_tree(data)
    dict = update_code(tree)
    print(dict)

 

실행 결과