[[분류:알고리즘]] [목차] == 개요 == 허프만 코드(Huffman's Code)는 허프만 알고리즘에 의해 생성된 최적 이진코드를 말한다. 허프만 알고리즘(Huffman's Algorithm)은 허프만 코드에 해당하는 이진트리를 구축하는 [[그리디 알고리즘]]이다. == 최적 이진코드 == 최적 이진코드(Optimal Binary Code)는 주어진 파일에 있는 문자들을 이진코드로 표현할 때 필요한 비트의 수가 최소가 되는 이진트리를 구축하는 [[최적화 문제]]의 일종이다. 주어진 문자열을 위한 최적 이진트리를 구축하기 위해서는 전치 코드(Prefix Code)로 구현해야 한다. 전치 코드란 길이가 변하는 가변 길이 이진코드의 특수한 형태로서, 한 문자의 코드워드가 다른 문자의 코드워드의 앞부분이 될 수는 없다. 예를 들어, 'a'라는 문자의 코드워드가 '01'이라면, 'b'라는 문자의 코드워드는 011이 될수는 없다. 01이 011의 앞부분과 겹치기 때문이다. 전치코드로 이진트리를 만들면 가변 길이 이진코드를 디코딩(파싱)할 때 뒷부분을 미리 봐야 할 필요가 없다는 장점이 있다. 전치코드는 리프노드가 코드문자이고, 내부노드는 이진수의 방향을 표현하는 이진트리로 표현 가능하다. == 허프만 알고리즘 == 허프만 알고리즘은 허프만 코드를 구축하기 위한 [[그리디 알고리즘]]이다. 주어진 데이터 파일 내의 문자의 개수가 n이라고 할 때, 이 데이터 파일을 이진코드를 인코딩(압축)하기 위한 최적의 이진트리 T를 구축한다. 허프만 알고리즘은 각 문자가 나타나는 빈도 수에 따라 [[우선순위 큐]]를 사용하여 다음과 같이 생성할 수 있다. {{{#!syntax python class HuffNode:     def __init__ (self, symbol, freq):         self.symbol = symbol         self.freq = freq         self.left = None         self.right = None def huffman (n, PQ):     for _ in range(n - 1):         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] }}} 위의 소스 코드 구현에 대한 상세한 설명은 [[https://youtu.be/IDxnHM01fZY|이 영상]][* [[https://youtu.be/IDxnHM01fZY|허프만 코드와 허프만 알고리즘 강의 영상]]]에서 볼 수 있다.