Huffman Coding

Huffman Coding은 글자의 빈도수를 기반으로 text를 2진수의 조합으로 변환하는 알고리즘입니다.

 

글자의 출현 빈도수가 높을수록 작은 2진수를, 글자수의 빈도가 낮을수록 높은 2진수를 부여합니다.

 

그렇게되면 기존의 Text를 2진수로 무손실 압축을 할 수가 있습니다(정보의 손실X)

 

이때 글자간의 분간을 위해서 끝자리를 0으로 고정합니다(또는 마지막 문자는 끝자리를 1로 만듭니다)

과거 Huffman이 고안하여 Huffman Coding이라고 하며,

 

원본을 알기 위해선 Coding 된 Text와 함께 Huffman Tree가 필요합니다.

 

위 예시로 작성된 Huffman Tree

Huffman Tree의 생성 알고리즘은

1. 문자의 총 출현 빈도를 가지고, 가장 높은 빈도수의 문자부터 Top Node의 Left Node에 추가해줍니다.

2. Right Node로 이동하여 1번을 반복합니다.

3. Unique Text의 개수만큼 Node가 할당되었으면 알고리즘 종료

 

이제 왼편으로 가면 0, 오르편으로 가면 1이 추가된다고 하면

 

빈도가 높으면 0 그 다음은 10, 그다음은 110 과 같은 2진수로 Encoding을 할 수 있는 Huffman Tree가 구축됩니다.

 

(10진수로 생각하면 처음은 0, 두번째는 0+2, 다음은 0+2+4... 0+2+...2^(n+1)의 값을 갖게됩니다)

 

최근 Python과 같은 언어에서는 Dictonary나 Json을 사용하면 쉽게 구현이 가능할 수 있지만,

 

Huffman Tree를 구축하고, 구축된 Tree를 이용하여 Huffman Coding을 하는 Python Code입니다.

import random

#Huffman Tree의 기본 Node.
#left,right node와 해당 Node의 count, char, coding_num 정보를 가지고있습니다.
class binary_node:
    def __init__(self, left, count, char, coding_num, right):
        self.left = left
        self.count = count
        self.char = char
        self.coding_num = coding_num
        self.right = right
   
class huffman_tree:
    def __init__(self, text):
        self.ori_text = text
        self.node_list = []        
        self.node_list_copy = []
        self.text_array = list(set(text))
        self.text_count = [0]*len(self.text_array)
        for i in range(len(self.text_array)):
            for j in range(len(text)):
                if self.text_array[i]==text[j]:
                    self.text_count[i] = self.text_count[i] +1 
        self.text_count_copy = self.text_count.copy()
        self.top_node = binary_node(None, sum(self.text_count), None, None, None)
        
    #leaf Node를 입력된 Text를 기반으로 생성합니다.
    def make_leaf_tree(self, char_array = None, char_count = None):         
        if (char_array is None) or (char_count is None):
            char_array = self.text_array
            char_count = self.text_count
        for i in range(len(char_array)):
            self.node_list = self.node_list + [binary_node(None,char_count[i],char_array[i],None,None)]
        self.node_list_copy = self.node_list.copy()
        return self.node_list.copy()
    
    #huffman Tree의 규칙에 따라 가장 큰 빈도수의 문자를 가진 Node를 left Node로
    #그 다음 right Node로 이동 후 동일한 과정을 반복합니다.
    def make_hf_tree(self,start_node = None,tot_count = None,char_count = None,coding_num = 1):                
        if char_count is None:
            char_count = max(self.text_count_copy)        
        if start_node is None:
            start_node = self.top_node
        if tot_count is None:
            tot_count = sum(self.text_count_copy)
        for i in range(len(self.node_list_copy)):
            if self.node_list_copy[i].count == char_count:
                self.node_list_copy[i].coding_num = coding_num
                coding_num = coding_num +1
                start_node.left = self.node_list_copy[i]
                del(self.node_list_copy[i])                
                del(self.text_count_copy[i])                                                
                tot_count = tot_count - char_count
                if tot_count <=0:
                    return True
                char_count = max(self.text_count_copy)                
                start_node.right = binary_node(None, tot_count, None, None, None)
                self.make_hf_tree(start_node.right,start_node.right.count,char_count,coding_num)
                break                    
    
    #huffman Tree를 출력
    def show_tree(self, test = 999):
        if test == 999:
            test = self.top_node 
        print(test.count, test.char, bin(test.coding_num) if test.coding_num is not None else test.coding_num)    
        self.show_tree(test.left) if test.left != None else None            
        self.show_tree(test.right) if test.right != None else None
            
    #huffman Tree를 기반으로 입력된 알파벳 or 문자의 coding num를 반환합니다.
    def coding_num(self, text, node = 999):
        result = 0
        if node == 999:
            node = self.top_node         
        if node != None:
            if text == node.char:
                result = pow(2,node.coding_num+1)-2
                return result         
        if node.left != None:
            result = self.coding_num(text, node.left) + result
        if node.right != None:
            result = self.coding_num(text, node.right) + result
        return result
    
    #입력된 text를 huffman tree를 기반으로 Encoding 하여 반환
    def coding_text(self, text = 999):
        if text == 999:
            text = self.ori_text
        coding_text = ""
        for i in range(len(text)):                                    
            coding_text = coding_text + str(bin(self.coding_num(text[i])))[2:]
        return coding_text


text = "eeemdaaksdaaa"
        
test = huffman_tree(text)                    
test.make_leaf_tree()
test.make_hf_tree()
test.show_tree()
test.coding_text()
Out[1]: '110110110111110111010101111011111101110101010'