엔트로피는 무엇을 의미합니까?

데이터 압축은 1940 년대에 클로드 섀넌이 제기한 정보론에서 비롯된 것이 아니라, 정보를 얼마나 작게 압축할 수 있는지에 대한 기본 원칙은 열역학의' 엔트로피' 라는 용어를 빌려 한 정보에 인코딩해야 할 정보의 양을 나타내는 정보론의 정리를 따르고 있다.

0 과 1 으로 구성된 이진수로 N 개의 기호가 포함된 정보를 인코딩하는 것을 고려해 보십시오. 기호 Fn 이 정보 전체에서 반복될 확률이 Pn 이라고 가정하면 기호의 엔트로피, 즉 기호를 나타내는 데 필요한 자릿수는 다음과 같습니다.

En =-log2(Pn)

전체 정보의 엔트로피, 즉 전체 정보를 나타내는 데 필요한 비트 수는 E = ∑En 입니다.

예를 들어, a b c 만 3 자인 다음 문자열의 경우 ：

Aabbaccbaa

문자열 길이가 10 이고 문자 a b c 가 각각 5 3 2 번 나타나면 a b c 가 정보에 나타날 확률은 각각 0.5 0.3 0.2 이고 엔트로피는 다음과 같습니다.

Ea =-log2(0.5)= 1

EB =-log2(0.3)= 1.737

EC =-log2(0.2)= 2.322

전체 정보의 엔트로피, 즉 전체 문자열을 나타내는 데 필요한 자릿수는 다음과 같습니다.

E = Ea * 5+Eb * 3+Ec * 2 = 14.855 입니다.

컴퓨터에서 일반적으로 사용되는 ASCII 코드를 사용하여 위의 문자열을 표현하면 전체 80 비트가 필요합니다! 이제 원본 정보 내용을 잃지 않고 정보를 압축할 수 있는 이유를 알 수 있습니다. 간단히 말해서, 자주 나타나는 기호를 더 적은 숫자로 표현하는 것이 데이터 압축의 기본 원칙입니다.

세심한 독자는 우리가 어떻게 0 1 과 같은 이진수로 몇 개의 이진수를 표현해야 하는지 곧 생각할 것이다. 이것은 확실히 어렵지만 불가능한 것도 아니다. 일단 우리가 0 의 몇 비트를 정확하게 표현할 수 있는 방법을 찾으면, 우리는 무손실 압축의 한계에 도전할 권리가 있다. 걱정하지 마세요. 제 4 장을 보면 알 수 있어요.

모형

위의 설명에서, 우리는 하나의 정보를 압축하려면 먼저 정보의 각 기호의 확률을 분석해야 한다는 것을 알게 되었다. 압축 프로그램마다 다른 방법으로 기호가 나타날 확률을 결정합니다. 기호 확률이 정확할수록 좋은 압축 효과를 얻을 수 있습니다. 압축 프로그램에서 입력 정보를 처리하고, 기호 확률을 계산하고, 출력할 코드를 결정하는 모듈을 모형이라고 합니다.

정보의 문자 발생 확률을 추정하기가 너무 어려워 다양한 압축 모델이 있습니까? 위의 문자열에 대해서는 각 문자의 확률을 쉽게 알 수 없습니까? 네, 그렇습니다. 하지만 위의 문자열은 10 자 길이밖에 되지 않습니다. 이것은 단지 하나의 예일 뿐이다. 우리 현실에서 압축해야 할 서류를 감안하면 대부분 수십 K, 심지어 수백 K 의 길이를 가지고 있다. 몇 개의 M 바이트 파일이 흔하지 않나요?

예, 파일의 모든 문자를 미리 스캔하고 각 문자의 확률을 계산할 수 있습니다. 이 방법을 압축 용어로는 "정적 통계 모델" 이라고 합니다. 그러나 파일마다 문자 분포 확률이 다르므로 먼저 압축해야 하는 모든 파일의 문자 확률을 계산하는 데 많은 시간을 할애하거나 각 개별 파일에 대한 확률 테이블을 저장하여 압축을 풉니다. 불행히도 파일을 스캔하는 데는 시간이 많이 걸릴 뿐만 아니라 확률 테이블을 저장하면 압축 파일이 훨씬 늘어날 수 있습니다. 따라서 실제 응용 프로그램에서는 정적 통계 모델이 거의 사용되지 않습니다.

대부분의 실제 압축 프로그램은' 어댑티브 모델' 이라는 것을 사용합니다. 가변 모델은 학습 기능이 있는 로봇이라고 할 수 있습니다. 정보를 입력하기 전에 그는 정보의 내용에 대해 아무것도 모르고 각 문자의 발생 확률이 같다고 가정했다. 문자가 지속적으로 입력되고 인코딩됨에 따라 그는 이미 나타난 문자의 확률을 계산하고 기록하여 후속 문자의 인코딩에 적용합니다. 즉, 어댑티브 모델의 압축 효과는 압축 시작 시 이상적이지 않지만 압축이 진행됨에 따라 문자 확률의 정확한 값에 점점 더 가까워지고 원하는 압축 효과를 얻을 수 있습니다. 가변 모델은 또한 입력 정보의 문자 분포의 급격한 변화를 수용할 수 있으며 확률 테이블을 저장하지 않고 다른 파일의 문자 분포를 수용할 수 있습니다.

위에서 언급한 모델을 통칭하여 "통계 모델" 이라고 부를 수 있는데, 이는 각 문자의 발생 횟수를 기준으로 문자 확률을 얻기 때문입니다. 또 다른 모델을 사전 모델이라고 합니다. 사실, 우리가 삶에서' ICBC' 라는 단어를 언급할 때, 우리 모두는 그것이' 중국공상은행' 을 의미한다는 것을 알고 있습니다. 비슷한 예가 많이 있지만, * * * 의 전제는 우리 마음속에 약어사전이 있다는 것입니다. 사전 모델도 마찬가지입니다. 문자가 나타날 확률을 직접 계산하는 대신 사전을 사용합니다. 입력 정보가 읽히면 모델은 사전에서 입력 정보가 일치하는 가장 긴 문자열을 찾은 다음 사전에서 해당 문자열의 색인 정보를 출력합니다. 일치 시간이 길수록 압축 효과가 좋습니다. 실제로 사전 모델은 여전히 문자 확률 계산을 기반으로 하지만 사전 모델은 문자의 반복 횟수를 계산하는 대신 전체 문자열의 일치를 사용합니다. 사전 모델이 얻은 압축 효과는 여전히 엔트로피의 한계를 돌파할 수 없다는 것을 증명할 수 있다.

물론 일반 압축 프로그램의 경우 큰 사전을 저장하는 데 필요한 공간은 여전히 감당할 수 없으며 미리 정의된 사전은 다른 파일의 데이터 변화에 적응할 수 없습니다. 그건 그렇고, 사전 모델도 그에 상응하는' 적응' 방안을 가지고 있다. 정보가 계속 입력됨에 따라 이미 입력한 정보에서 조합을 만들 수 있습니다.