이진 스트림의 엔트로피 인코딩

Question

이진 스트림을 압축하려고합니다. 각 '1'이후에는 '0'을 찾을 확률이 더 높으며 각 '0'다음에 '1'을 찾는 확률이 더 높습니다. 어떻게 인코딩해야합니까? 나는 라이스 코드에 대해 생각하고 있었지만 지금까지 얻지 못했습니다 ... 어떤 답장에 대해서 미리 감사드립니다.

Answer 1

간단한 허프만 코딩을 시도해 보셨습니까? 아마도 '10'과 '01'코드 중 하나가 '00'또는 '11'보다 훨씬 높은 확률을 가지면 '0'으로 매핑하고 다른 하나는 '10'으로 매핑 할 수 있습니다. , '110'및 '111'.

물론이 방법은 스트림을 2 비트 청크로 분할하고 하나의 경우 만 최적화하기 때문에 최상의 선택이 아닙니다. 그러나, 4 비트 또는 8 비트와 같은 더 큰 입력 세트에 대한 확률을 계산/측정함으로써 정교 할 수있다. 8 비트 경우 10101010 및 01010101은 00000000 및 11111111보다 자주 사용됩니다.

산술 코딩 또는 비트 프로 파일링을 기반으로하는 일부 압축을 사용하면 더 나은 결과를 얻을 수 있습니다.

또 다른 간단한 접근법은 모든 두 번째 비트를 뒤집는 것입니다. 당신이 말한 확률이 0101010과 같이 많은 수의 스트림 부분을 가지고있는 경향이 있기 때문에 보통 111111과 같은 많은 스트림 부분을 제공 할 것입니다. 보통 111111은 보통의 압축 알고리즘으로 더 잘 압축 될 수 있습니다. 그러나이 방법의 성공 여부는 "확률 격차"가 얼마나 큰지에 달려 있습니다.