허프만 코드
허프만 코드는 무손실 데이터 압축에 일반적으로 사용되는 특정 유형의 최적 접두사 코드로 정의됩니다.
이러한 코드를 찾거나 구현하는 프로세스는 David A. Huffman이 Sc.D.에 있을 때 개발한 알고리즘인 Huffman 코딩을 통해 진행됩니다. MIT 학생이며 1952년 논문 "A Method for the Construction of Minimum Redundancy Codes"에 게재되었습니다.
Huffman 알고리즘의 출력은 소스 기호(예:파일의 문자)를 인코딩하기 위한 가변 길이 코드 테이블로 표시될 수 있습니다. 알고리즘은 소스 심볼의 가능한 각 값에 대해 추정된 확률 또는 발생 빈도(가중치)로부터 이 테이블을 생성합니다. 다른 엔트로피 인코딩 방법에서와 같이 더 일반적인 심볼은 일반적으로 덜 일반적인 심볼보다 적은 비트를 구현하여 표현됩니다. Huffman 방법을 효율적으로 구현할 수 있으며 이러한 가중치를 정렬하면 입력 가중치의 수에 선형적인 시간에 코드를 찾을 수 있습니다.
엔트로피
정보 이론에서 Shannon의 소스 코딩 정리(또는 무잡음 코딩 정리)는 가능한 데이터 압축의 한계와 Shannon 엔트로피의 작동 의미를 설정할 수 있습니다.
소스 코딩 정리는 (한계에서, 독립적이고 동일하게 분포된 랜덤 변수(i.i.d.) 데이터 스트림의 길이가 무한대가 되기 때문에) 코드율(평균 비트당 비트 수)는 소스의 Shannon 엔트로피보다 작지만 정보가 손실될 것이라는 사실이 거의 확실하지 않습니다. 그러나 무시할 수 있는 손실 확률로 Shannon 엔트로피에 임의로 가까운 코드율을 얻을 수 있습니다.
정보 엔트로피는 정보가 확률적 데이터 소스에 의해 생성되는 평균 비율로 정의됩니다.
임의 변수에 대한 엔트로피 계산
확률 변수에 얼마나 많은 정보가 있는지 계산할 수도 있습니다.
예를 들어 확률 분포가 p인 확률 변수 X에 대한 정보를 계산하려는 경우 함수 H()로 작성할 수 있습니다. 예:H(X)
실제로 확률 변수에 대한 정보를 계산하는 것은 확률 변수에 대한 사건의 확률 분포에 대한 정보를 계산하는 것과 유사합니다.
확률 변수에 대한 정보를 계산하는 것은 "정보 엔트로피", "섀넌 엔트로피" 또는 간단히 "엔트로피"로 표시됩니다.
이는 둘 다 용어 불확실성과 관련되어 있다는 점에서 유추에 의한 물리학의 엔트로피 개념과 관련이 있습니다.
엔트로피에 대한 직관은 엔트로피가 확률 변수에 대한 확률 분포에서 가져온 이벤트를 나타내거나 전송하는 데 필요한 평균 비트 수로 정의된다는 것입니다.
분포의 Shannon 엔트로피는 해당 분포에서 가져온 이벤트의 예상 정보량으로 정의됩니다.
분포 P에서 가져온 기호를 인코딩하는 데 평균적으로 필요한 비트 수에 대한 하한을 제공합니다.
엔트로피는 다음과 같이 K 불연속 상태에서 k가 있는 확률 변수 X에 대해 계산할 수 있습니다.
H(X) = -sum(each k in K p(k) * log(p(k)))
이는 각 사건의 확률의 합에 각 사건의 확률의 로그를 곱한 음수를 의미합니다.
정보와 마찬가지로 log() 함수는 base-2를 구현하고 단위는 비트입니다. 대신 자연 로그를 구현할 수 있습니다.
가장 낮은 엔트로피는 확률이 1.0인 단일 이벤트가 있는 확률 변수에 대해 계산됩니다. 확률 변수에 대한 가장 큰 엔트로피는 모든 이벤트가 동일한 가능성으로 수행되는 경우 가능합니다.