[압축 알고리즘] 허프만 부호화 (Huffman coding) + JAVA 구현

허프만 부호화 (Huffman coding) 허프만 부호화란 무손실 압축에 사용되는 엔트로피 코딩 중 하나이다. 이전 글에서 엔트로피 코딩의 목적은 데이터 심볼 당 평균 부호 길이가 엔트로피에 가까워지도록 부호를 할당하여 압축 효율을 높이는 것이라고 하였다. 허프만 부호화는 발생 빈도가 높은 (자주 나오는) 심볼에는 짧은 부호를 할당하고, 발생 빈도가 적은 심볼에는 비교적 긴 부호를 할당한다. 따라서 최대한으로 평균 부호길이가 압축되는 결과를 얻을 수 있다. 허프만 부호화 시 각각의 심볼에 접두 코드(Prefix code)를 할당한다. 접두 코드란 코드 집합에서 어떤 코드도 다른 코드의 접두사가 되지 않게 만들어진 코드이다. 예를 들어 {"0", "01"} 코드 집합의 경우 접두 코드가 아니다. "0"은..