허프만 코드(Huffman Code)
허프만 코드는 무손실 데이터 압축에 널리 사용되는 최적 접두어 코드(optimal prefix code)의 한 종류로 정의됩니다.
이러한 코드를 찾거나 구현하는 과정은 허프만 코딩(Huffman coding)이라는 알고리즘을 통해 이루어집니다. 이 알고리즘은 MIT에서 박사(Sc.D.) 과정에 있던 데이비드 A. 허프만(David A. Huffman)이 개발했으며, 1952년 발표한 논문 「A Method for the Construction of Minimum-Redundancy Codes(최소 중복 코드의 구성 방법)」에서 처음 소개되었습니다.
허프만 알고리즘의 출력 결과는 파일 내 문자와 같은 원본 기호(source symbol)를 인코딩하기 위한 가변 길이 코드표 형태로 나타낼 수 있습니다. 이 알고리즘은 원본 기호가 가질 수 있는 각 값에 대한 추정 확률 또는 발생 빈도(가중치)를 바탕으로 코드표를 생성합니다. 다른 엔트로피 인코딩 방식과 마찬가지로, 자주 등장하는 기호일수록 드물게 등장하는 기호보다 더 적은 비트로 표현됩니다. 허프만 방식은 가중치가 미리 정렬되어 있다면 입력 가중치의 개수에 비례하는 선형 시간 안에 코드를 찾을 수 있을 만큼 효율적으로 구현할 수 있습니다.
엔트로피(Entropy)
정보 이론에서 샤논의 원천 부호화 정리(source coding theorem, 무잡음 부호화 정리라고도 함)는 데이터 압축이 가질 수 있는 한계와 샤논 엔트로피의 실질적인 의미를 규명합니다.
원천 부호화 정리에 따르면, 독립적이고 동일하게 분포된(i.i.d.) 확률 변수 데이터 스트림의 길이가 무한대로 간다는 조건에서, 정보 손실이 사실상 확실해지지 않는 한 코드율(기호당 평균 비트 수)을 원본의 샤논 엔트로피보다 낮게 만들며 데이터를 압축하는 것은 불가능합니다. 반면, 손실 확률을 무시할 수 있을 정도로 낮추면서 코드율을 샤논 엔트로피에 임의로 가깝게 만드는 것은 가능합니다.
정보 엔트로피(information entropy)란 데이터의 확률적 원천(stochastic source)이 정보를 생산하는 평균적인 비율로 정의됩니다.
확률 변수의 엔트로피 계산하기
확률 변수에 담긴 정보량 역시 계산할 수 있습니다.
예를 들어 확률 분포 p를 가진 확률 변수 X에 대한 정보를 계산하고 싶다면, 이를 함수 H()로 표기하여 H(X)와 같이 나타낼 수 있습니다.
사실상 확률 변수에 대한 정보를 계산하는 것은 해당 확률 변수의 사건들에 대한 확률 분포의 정보를 계산하는 것과 같습니다.
확률 변수에 대한 정보 계산은 "정보 엔트로피(information entropy)", "샤논 엔트로피(Shannon entropy)", 또는 단순히 "엔트로피(entropy)"라는 이름으로 불립니다.
이는 물리학의 엔트로피 개념과 유추 관계에 있는데, 두 개념 모두 '불확실성'이라는 측면과 관련이 있기 때문입니다.
엔트로피의 직관적인 의미는 확률 변수의 확률 분포에서 추출된 하나의 사건을 표현하거나 전송하는 데 필요한 평균 비트 수로 정의된다는 점입니다.
분포의 샤논 엔트로피는 해당 분포에서 추출된 사건이 담고 있는 기대 정보량(expected amount of information)으로 정의됩니다.
또한 분포 P에서 추출한 기호를 인코딩하는 데 필요한 평균 비트 수의 하한선(lower bound)을 제공합니다.
K개의 이산 상태 k를 가진 확률 변수 X의 엔트로피는 다음과 같이 계산할 수 있습니다.
H(X) = -sum(each k in K p(k) * log(p(k)))
즉, 각 사건의 확률에 그 확률의 로그값을 곱한 값들을 모두 더한 뒤 음수를 취한 값입니다.
정보의 경우와 마찬가지로 log() 함수는 밑(base)이 2인 로그를 사용하며 단위는 비트(bit)입니다. 필요에 따라 자연로그(natural logarithm)를 대신 사용할 수도 있습니다.
최저 엔트로피는 확률이 1.0인 단일 사건, 즉 결과가 확실한 경우만을 가진 확률 변수에서 계산됩니다. 반면 최대 엔트로피는 모든 사건이 동일한 확률로 발생할 때 나타납니다.