엔트로피와 무손실 압축 속도와의 관계

Question

에서 Shannon의 소스 코딩 정리 압축 문자열의 엔트로피는 원래 문자열의 엔트로피에 의해 제한되어 있음을 알고 있습니다.

H(X) <= L < H(X) + 1/N 

여기서 h (x)는 소스 문자열의 엔트로피이고 n은 소스 문자열의 길이이고, l은 압축 된 스트링의 예상 길이입니다.

이것은 반드시 무손실 압축에 제한이 있음을 의미합니다.

내가 알고 싶은 것은 다음과 같습니다.

• 엔트로피를 일부 예상 압축 비율과 직접 연관시킬 수 있습니까?

• 엔트로피를 사용하여 압축 비율의 상한을 찾을 수 있습니까?

Answer 1

소스 문자열의 길이를 모르면 엔트로피와 압축 비율을 직접 연관시킬 수는 없지만 L의 가장 작은 값을 해결하여 최대 압축 비율에 대한 이론적 한계를 볼 수 있습니다.이 한계를 메트릭으로 사용할 수 있습니다. 압축 알고리즘의 효율성이 좋지 않다고해서 더 나은 알고리즘이 발견되거나 심지어 존재한다는 의미는 아닙니다.

그래서 그렇습니다. 엔트로피를 사용하여 이론적 최대 무손없는 압축 비율을 찾을 수 있지만, 주어진 압축 알고리즘에 대해 예상 압축 비율을 결정하는 데 사용할 수 없습니다.

Answer 2

Shannon의 정리는 임의의 데이터 및 확률 측면에서 정의됩니다. 마찬가지로 엔트로피 문자열은 임의의 문자열에 대해서만 정의됩니다. 엔트로피는 문자열 자체가 아닌 분포의 특성입니다. 따라서 Shannon의 정리를 비공식적으로 다시 사용할 수 있습니다.

주어진 확률 분포에서 문자열을 무작위로 선택하면 문자열에 대해 얻을 수있는 가장 좋은 평균 압축 비율은 확률 분포의 엔트로피 속도로 주어집니다.

임의의 문자열이 주어지면 해당 문자열을 1 비트로 압축 할 압축 알고리즘을 쉽게 작성할 수 있지만 알고리즘은 반드시 다른 문자열의 길이를 증가시킵니다. 압축 알고리즘은 다음과 같이 작동합니다.

1. 입력 문자열이 같은 경우 일부 사전 선택된 임의 문자열, 출력은 1 비트 문자열 "0"입니다.
2. 그렇지 않으면 출력은 "1"의 n+1 비트 문자열과 입력 문자열입니다.

해당 감압 알고리즘은 다음과 같습니다.

1. 입력이 "0"인 경우 출력은 우리의 이전 사전 선택된 임의 문자열
2. 그렇지 않으면 출력은 첫 번째 입력 비트를 제외한 모든 것입니다.

여기서 핵심은 우리가 기록 할 수 없다는 것입니다 하나 주어진 분포의 모든 문자열에 대해 압축하는 알고리즘 모두 평균적으로 높은 비율로. 문자열이 너무 많습니다.

줄의 확률 분포가있는 경우 분포의 엔트로피 속도를 계산 한 다음 무작위로 문자열을 선택할 수 있습니다. 분포에 따르면 그리고 그것을 사용하여 압축하려고 시도하십시오 어느 알고리즘, 압축 문자열의 상대적 크기는 평균적으로 엔트로피 속도보다 적지 않습니다. 이것이 Shannon의 정리가 말한 것입니다.

Answer 3

예. 그만큼 엔트로피 속도 영어 중에서 종종 캐릭터 당 1.5 비트 (주 또는 테이크)로 인용됩니다. 일반적인 인코딩은 문자 당 8 비트를 사용합니다. 따라서 최대 압축 텍스트는 원본 크기의 1.5/8 (~ 19%)이어야합니다. Jane Austin 's Pride and Prejudice의 일반 텍스트 버전에 대한 실제 결과 : orig = 701k, bzip2 = 178k, ~ 25%.

Answer 4

예! 제 생각에는 이 종이 당신을 올바른 방향으로 가리킬 것입니다.

에타 실제 용지를 읽으려면 IEEE 회원이어야하는 것 같습니다. 누군가가 공개적으로 이용 가능한 자원을 찾거나 (여기서 수학을 설명 할 수 있다면) 물론 훨씬 더 나을 것입니다!