압축 코드

우리가 이미지와 같은 정보를 디지털로 표현한다는 것은 작은 조각들로 나누는 것과 같습니다 그렇게 해서 그 이미지를 일련의 컬러 기호들로 나타내어 보낼 수 있게 하는데 각 색깔은 어떠한 코드를 사용하여 고유한 숫자로 표현될 수 있습니다 다음 상황을 생각해 봅시다 Alice와 Bob은 메시지를 이진기호로 주고 받을 수 있습니다 (모스 부호) 그들은 고객들에게 1비트당 1원씩 받고 그들의 시스템을 이용하게 합니다 그리고 어떤 단골 손님은 1,000개 기호 길이의 메시지를 보내고 싶어한다고 합시다 그 메시지의 뜻은 아무도 모릅니다 보통 이 메시지가 표준 2비트 코드로 보내진다면 2000비트에 대하여 가격이 정해집니다 하지만, Alice와 Bob는 이미 이 손님에 대해서 분석을 했고 각각의 기호가 나올 확률이 다 다르다고 판단했습니다 그들은 이 확률을 이용하여 전달하는 크기를 압축시켜서 이익을 얻을 수 있을까요? 최적의 코딩 전략은 무엇일까요? 데이비드 허프만은 1952년에 그러한 최적의 전략을 소개 했는데 그것은 상향식 이진트리를 만들어 사용하는 방법입니다 처음에, 트리의 바닥에 모든 기호들을 나열하는데 그것을 노드라고 부릅니다 그 다음에 가장 확률이 낮은 두개의 노드를 찾아서 이 경우에는 B와 C입니다 그들을 하나로 합칩니다 그리고 확률도 같이 더하여 합칩니다 그 후 다시 가장 확률이 낮은 두 노드로 같은 과정을 반복합니다 그렇게 하여 트리의 가장 위에 하나의 노드가 남을 때까지 계속 합니다 마지막으로, 이 트리의 노드들간의 각 연결선에 순서에 맞추어 0 또는 1로 적습니다 이제 각 기호에 대한 코드는 트리의 가장 위에서 그 기호로 내려가는 경로입니다 기호 A의 경우에는 연결선이 하나인데 코드는 1입니다 이것이 허프만 코딩이라고 알려진 것입니다 그리고 다음과 같은 형태의 예에서는 허프만 코딩보다 더 압축시킬 수는 없습니다 한번 해볼까요? 예를 들어, 기호 D에 대한 코드를 줄여서 0으로 하기로 한다면 메시지 011은 아마도 DAA가 되거나 혹 B가 될 수도 있습니다 이것을 사용하려면 빈칸 기호가 필요하고 그것 때문에 전송 크기가 다시 커지게 되어 압축 효율이 줄어들게 됩니다 이 방법이 메시지를 얼마나 압축하는지 아까 그 2000비트를 가지고 비교해봅시다 한 문자당 평균 몇개의 비트가 있는지 계산하면 됩니다 각 코드의 길이를 발생 확률과 곱하고 모두 다 더하면 평균적으로 한 기호 당 1.75 비트가 나옵니다 이것은 허프만 코딩으로 메시지를 2,000 비트에서 1,750비트로 압축시킬수 있다는 것을 의미합니다 클로드 섀넌은 정보 압축의 한계는 항상 원래 메시지의 엔트로피(혼란도) 가 될거라고 처음으로 주장하였습니다 원래 메시지의 엔트로피 혹은 불확실성이 통계구조를 알게되어 감소하게되면 압축능력은 증가합니다 (모스 코드) 반면, 예측 불가능성때문에 엔트로피(혼란도)가 증가하면 압축능력이 감소 됩니다 (모스코드) 만약 엔트로피보다 더 압축하고 싶다면 메시지에 있는 정보를 버려야 할 것입니다