[알고리즘] 허프만 알고리즘

이진코드 binary code

데이터 파일을 이진코드로 인코딩하여 저장.
길이가 고정된 fixed-length 이진코드와 길이가 변하는 variable-length 이진코드가 있다.
가장 많이 사용되는 문자의 비트가 가장 짧도록 설정해주면 압축 효율이 올라간다.

사용하는 문자가 {a, b, c}인 경우
왼쪽이 fixed 오른쪽이 variabe이다.

최적 이진코드 문제 optimal binary code

주어진 파일에 있는 문자들을 이진코드로 표현할 때 필요한 비트의 개수가 최소가 되는 이진코드?
전치 코드 prefix code
: 길이가 변하는 이진코드의 특수한 형태. 한 문자의 코드워드가 다른문자의 코드워드 앞부분이 될 수 없음 (01이 'a'라면 011은 'b'가 될 수 없음)
-> 모든 전치코드는 리프노드가 코드문자인 이진트리로 표현가능하다.
code1은 비효율적(fixed: 자주 나오는 문자를 우대하지 않음)

허프만 알고리즘 Huffman's Algorithm

허프만 코드에 해당하는 최적의 이진트리를 구축하는 그리디 알고리즘

허프만 코드 : 허프만 알고리즘에 의해 생성된 최적의 이진코드

수도코드로 나타내면 아래와 같다.

허프만 알고리즘 구현

n : 문자 개수
PQ : 빈도수가 낮은 노드 선리턴 (우선순위큐)

for i in [1..n-1]:
	remove(PQ, p)
    remove(PQ, q)
    r = 새 노드
    r->left = p #p를 왼쪽노드로 설정
    r->right = q #q를 오른쪽노드로 설정
    r->빈도 = p->빈도 + q->빈도
    insert(PQ, r)
remove(PQ, r) #모든 노드가 제거되면 r리턴 
return r

인오더, 프리오더, 포스트오더

class HuffNode:        #문자  빈도수
    def __init__(self, symbol, freq):
        self.symbol = symbol
        self.freq = freq
        self.left = None
        self.right = None

    def preorder(self):
        print(self.freq, end=' ')
        if self.left is not None:
            self.left.preorder()
        if self.right is not None:
            self.right.preorder()

    def inorder(self):
        if self.left is not None:
            self.left.inorder()
        print(self.freq, end=' ')
        if self.right is not None:
            self.right.inorder()

def huffman(n, PQ):
    for _ in range(n - 1): #0~n-2
        p = PQ.get()[1]
        q = PQ.get()[1]
        r = HuffNode(' ', p.freq + q.freq) #새노드 생성, 중간노드는 문자 필요 없음-> 공백
        r.left = p
        r.right = q
        PQ.put((r.freq, r))
    return PQ.get()[1] #마지막노드

codes = ['b', 'e', 'c', 'a', 'd', 'f']
freq = [5, 10, 12, 16, 17, 25]

from queue import PriorityQueue

PQ = PriorityQueue()
for i in range(len(codes)):
    node = HuffNode(codes[i], freq[i])
    PQ.put((node.freq, node))

root = huffman(len(codes), PQ)

print('preorder :', end='')
root.preorder()
print('\ninorder :', end='')
root.inorder()

-> encoding, decoding을 하는 연습을 해보는게 좋다(함수로 만들어보기)