☰

ent 프로그램은 "최적 압축"을 어떻게 계산합니까?

tag-icon • tag-icon compression
ent 프로그램은 "최적 압축"을 어떻게 계산합니까?

이것이비인후과프로그램을 파일에서 실행하여 다음과 같은 출력을 제공할 수 있습니다.

엔트로피 = 바이트당 4.731183비트.

최적의 압축은 이 15731바이트 파일의 크기를 40%까지 줄입니다.

15731개 표본의 카이제곱 분포는 235086.62이며, 이 값을 무작위로 초과하는 횟수는 0.01% 미만입니다.

데이터 바이트의 산술 평균은 87.3796(127.5 = 무작위)입니다. Pi의 몬테카를로 값은 4.000000000(오차 27.32%)입니다. 계열 상관 계수는 0.140065입니다(완전히 상관되지 않음 = 0.0).

프로그램은 "최적의 압축"이 무엇을 달성할 수 있는지 어떻게 결정합니까?

나는 심지어 gzip조차도 이 추정치를 초과하는 경우가 많다는 것을 알아냈습니다.

답변1

엔트로피는 파일에 담긴 정보의 다양성을 제공하고,즉파일에 존재하는 고유 값의 수를 표현하면 최상의 압축, 더 정확하게는 최상의 인코딩이 해당 저장 공간을 정확하게 사용하게 됩니다.

귀하의 경우 파일의 길이는 현재 15,731바이트이지만 바이트당 4.731183비트를 저장하므로 총 4.731183 × 15,731비트의 정보가 포함됩니다.즉74,426.24비트의 정보 또는 9,303.28바이트. 최적의 압축을 사용하면 원본 파일의 59.14%에 해당하는 9,304바이트 파일이 생성됩니다. 파일 길이를 참조하지 않고 동일한 계산을 수행할 수 있습니다. 4.733183은 8의 59.16%입니다. 약식으로 표현하면 (8 - 4.733183)은 8의 40.84%이고,수행된 계산입니다.ent, 백분율을 정수로 자릅니다.

           printf("Entropy = %f bits per %s.\n", ent, samp);
           printf("\nOptimum compression would reduce the size\n");
           printf("of this %lld %s file by %d percent.\n\n", totalc, samp,
            (short) ((100 * ((binary ? 1 : 8) - ent) /
                  (binary ? 1.0 : 8.0))));

실제 압축 도구는 반복을 보다 간결한 방식으로 표현함으로써 이 문제를 극복합니다. 결과 비교

$ (printf %5000s; printf %5000s | tr ' ' '1') | ent
Entropy = 1.000000 bits per byte.

Optimum compression would reduce the size
of this 10000 byte file by 87 percent.

$ (printf %5000s; printf %5000s | tr ' ' '1') | gzip | wc -c
48

입력은 많은 수의 바이트로 구성되지만 두 개의 고유한 값만 있고 둘 다 숫자가 동일하므로 엔트로피는 바이트당 1비트입니다. ent입력을 바이트당 1비트로 인코딩할 수 있다고 생각하면,즉8배로 줄었습니다. gzip그러나 이는 공백과 숫자의 연속을 나타내며 결과 파일은 gzip헤더를 포함하더라도 208배 더 작습니다.

관련 정보