매일 9억 기가바이트 이상의 정보가 인터넷을 통해 이동하면서 연구원들은 데이터를 더 작은 패키지로 압축하는 새로운 방법을 끊임없이 찾고 있습니다. 최첨단 기술은 전송에서 정보를 의도적으로 "손실"하여 압축을 달성하는 손실 접근 방식에 중점을 둡니다. 예를 들어 Google은 최근 송신 컴퓨터가 이미지에서 세부 정보를 삭제하고 수신 컴퓨터가 누락된 부분을 추측하기 위해 인공 지능을 사용하는 손실 전략을 공개했습니다. Netflix조차도 손실 접근 방식을 사용하여 회사에서 사용자가 저해상도 장치에서 보고 있음을 감지할 때마다 비디오 품질을 낮춥니다.

이와는 대조적으로 전송이 더 작아지지만 물질이 희생되지 않는 무손실 전략에 대한 연구는 현재 거의 진행되지 않고 있습니다. 이유? 무손실 접근 방식은 이미 매우 효율적입니다. JPEG 이미지 표준에서 유비쿼터스 소프트웨어 유틸리티 PKZip에 이르기까지 모든 것을 지원합니다. 그리고 그것은 모두 단순히 힘든 기말 고사에서 벗어날 방법을 찾고 있던 대학원생 때문입니다.

XNUMX년 전, 로버트 파노(Robert Fano)라는 매사추세츠 공과대학(MIT) 교수는 정보 이론 수업에서 학생들에게 전통적인 기말 시험을 치르거나 데이터 압축을 위한 선도적인 알고리즘을 개선할 것인지 선택권을 주었습니다. Fano는 학생들에게 자신이 기존 알고리즘의 저자이거나 몇 년 동안 개선을 위해 노력했다고 알렸을 수도 있고 그렇지 않았을 수도 있습니다. 우리가 아는 것은 Fano가 그의 학생들에게 다음과 같은 도전을 제안했다는 것입니다.

문자, 숫자 및 구두점으로 구성된 메시지를 고려하십시오. 이러한 메시지를 인코딩하는 간단한 방법은 각 문자에 고유한 이진수를 할당하는 것입니다. 예를 들어, 컴퓨터는 문자 A를 01000001로, 느낌표를 00100001로 나타낼 수 있습니다. 그 결과 XNUMX자리 또는 비트마다 하나의 고유한 문자에 해당하는 파싱하기 쉬운 코드가 생성되지만 동일한 숫자가 동일하기 때문에 매우 비효율적입니다. 이진수는 공통 및 비공통 항목 모두에 사용됩니다. 더 나은 접근 방식은 모스 부호와 같은 것입니다. 자주 사용되는 문자 E는 단 하나의 점으로 표시되는 반면 덜 일반적인 Q는 더 길고 더 힘든 대시-대시-점-대시가 필요합니다.

그러나 모스 부호도 비효율적입니다. 물론 일부 코드는 짧고 다른 코드는 깁니다. 그러나 코드 길이가 다양하기 때문에 모스 부호의 메시지는 각 문자 전송 사이에 짧은 침묵 시간을 포함하지 않으면 이해할 수 없습니다. 사실, 비용이 많이 드는 일시 중지가 없었다면 수신자는 모스 메시지 dash dot-dash-dot dot-dot dash dot("trite")와 dash dot-dash-dot dot-dot-dash dot("true")을 구분할 방법이 없었을 것입니다. ).

Fano는 문제의 이 부분을 해결했습니다. 그는 전체 코드와 다른 코드의 시작 부분에 동일한 숫자 패턴을 사용하지 않는 한 비용이 많이 드는 공백 없이 다양한 길이의 코드를 사용할 수 있다는 것을 깨달았습니다. 예를 들어 문자 S가 특정 메시지에서 너무 흔해서 Fano가 매우 짧은 코드 01을 할당한 경우 해당 메시지의 다른 문자는 01로 시작하는 문자로 인코딩되지 않습니다. 010, 011 또는 0101과 같은 코드는 모두 금지됩니다. 그 결과 코딩된 메시지를 모호성 없이 왼쪽에서 오른쪽으로 읽을 수 있었습니다. 예를 들어 문자 S에 01, 문자 A에 000, 문자 M에 001, 문자 L에 1을 할당하면 갑자기 0100100011이라는 메시지가 L을 XNUMX로 나타내더라도 즉시 "작다"라는 단어로 번역될 수 있습니다. 숫자, S는 두 자리, 다른 문자는 각각 세 자리입니다.

실제로 코드를 결정하기 위해 Fano는 시각적 분기 끝에 필요한 각 문자를 배치하는 이진 트리를 구축했습니다. 그런 다음 각 문자의 코드는 위에서 아래로의 경로로 정의되었습니다. 경로가 왼쪽으로 분기되면 Fano는 0을 추가했습니다. 오른쪽 분기는 1을 얻었습니다. 트리 구조는 Fano가 바람직하지 않은 겹침을 쉽게 피할 수 있도록 했습니다. Fano가 트리에 문자를 배치하면 해당 분기가 종료되어 향후 코드가 같은 방식으로 시작할 수 없음을 의미합니다.

어떤 문자가 어디로 갈지 결정하기 위해 Fano는 최대 효율성을 위해 가능한 모든 패턴을 철저하게 테스트할 수 있었지만 그것은 비현실적이었습니다. 그래서 대신 그는 근사치를 개발했습니다. 모든 메시지에 대해 관련 문자를 빈도별로 정리한 다음 문자를 분기에 할당하여 주어진 분기 쌍의 왼쪽에 있는 문자가 메시지에서 거의 동일한 횟수로 사용되도록 했습니다. 오른쪽에 있는 글자. 이러한 방식으로 자주 사용되는 문자는 더 짧고 밀도가 낮은 가지로 끝납니다. 적은 수의 고주파 문자는 항상 더 많은 수의 저주파 문자와 균형을 이룹니다.

결과는 매우 효과적인 압축이었습니다. 그러나 그것은 근사치에 불과했습니다. 더 나은 압축 전략이 존재해야 했습니다. 그래서 Fano는 학생들에게 그것을 찾도록 도전했습니다.

Fano는 한 쌍의 가지 사이에 가능한 한 많은 대칭을 유지하면서 위에서 아래로 나무를 만들었습니다. 그의 학생 David Huffman은 같은 유형의 나무를 만들지만 아래에서 위로 프로세스를 뒤집었습니다. Huffman의 통찰은 어떤 일이 발생하든 효율적인 코드에서 가장 덜 공통적인 두 문자가 가장 긴 두 개의 코드를 가져야 한다는 것입니다. 그래서 Huffman은 가장 흔하지 않은 두 문자를 식별하고 분기 쌍으로 함께 그룹화한 다음 프로세스를 반복했습니다. 이번에는 나머지 문자와 방금 만든 쌍 중에서 가장 덜 공통된 항목 두 개를 찾았습니다.

Fano 접근 방식이 흔들리는 메시지를 고려하십시오. '교실'에는 O가 27번, S/C/H/L/R/M이 각각 한 번씩 등장한다. Fano의 균형 잡힌 접근 방식은 O와 다른 한 글자를 왼쪽 가지에 할당하는 것으로 시작합니다. 이러한 글자의 총 XNUMX가지 사용은 나머지 글자의 XNUMX가지 모양과 균형을 이룹니다. 결과 메시지에는 XNUMX비트가 필요합니다.

대조적으로 Huffman은 두 개의 흔하지 않은 문자(예: R 및 M)로 시작하여 함께 그룹화하여 쌍을 하나의 문자처럼 취급합니다.

그의 업데이트된 빈도 차트는 그에게 네 가지 선택 사항을 제공합니다. 네 번 나타나는 O, 기능적으로 두 번 사용되는 새로운 결합 RM 노드, 단일 문자 S, C, H 및 L. Huffman은 다시 두 가지 가장 덜 일반적인 옵션을 선택하여 일치 (예) H와 L.

차트가 다시 업데이트됩니다. O는 여전히 가중치가 4이고, RM과 HL은 이제 각각 가중치가 2이며, 문자 S와 C는 독립적입니다. Huffman은 거기에서 계속해서 각 단계에서 가장 빈도가 낮은 두 옵션을 그룹화한 다음 트리와 빈도 차트를 모두 업데이트합니다.

궁극적으로 "교실"은 11101111110000110110000101이 되어 Fano 하향식 접근 방식에서 약간 벗어났습니다.

XNUMX비트가 별 것 아닌 것처럼 들릴 수 있지만 작은 절감액도 수십억 기가바이트로 확장하면 엄청나게 커집니다.

실제로 Huffman의 접근 방식은 매우 강력하여 오늘날 거의 모든 무손실 압축 전략이 Huffman 통찰력을 전체적으로 또는 부분적으로 사용합니다. Word 문서를 압축하려면 PKZip이 필요합니까? 첫 번째 단계는 반복을 식별하여 메시지 크기를 압축하기 위한 또 다른 영리한 전략을 포함하지만 두 번째 단계는 압축된 메시지를 가져와 Huffman 프로세스를 통해 실행하는 것입니다. 이미지를 JPEG로 저장하시겠습니까? 컴퓨터는 먼저 이미지를 텍스트 기반 표현으로 변환한 다음 다시 Huffman 인코딩을 사용하여 해당 텍스트를 압축합니다.

기말고사를 건너뛰고 싶은 대학원생의 욕구에서 원래 동기가 부여된 프로젝트치고는 나쁘지 않습니다.