0에서 64 사이의 2개 위치를 인코딩하는 가장 효율적인 방법은 무엇입니까?

Question

중간 어딘가에만 데이터가 포함되어 있고 그 전후는 0이라는 사실을 이용하여 압축하고 싶은 64비트 값이 있습니다.

실제 데이터의 길이가 l 비트이고 앞에 n 0이, 끝에 m 0이 채워져 n + l + m = 64가 된다고 가정해 보겠습니다.64비트를 전송/저장하는 대신 l 비트와 함께 64비트 간격으로 데이터 위치를 인코딩하는 데 필요한 모든 것을 전송할 수 있습니다.

예를 들어, l, m 및 데이터 비트를 저장하고 있다고 가정하면 l을 읽고 l 비트의 데이터를 읽고 m을 읽고 데이터 m 비트를 왼쪽으로 이동하여 원래의 64비트 패턴을 복원합니다.

내가 생각해 낼 수 있는 가장 작은 오버헤드는 l, n, m 중 두 개(각각은 0에서 64 사이일 수 있음)를 저장하기 위한 6비트의 두 배입니다.그 숫자를 줄이는 것이 가능한가요?

Answer 1

l은 0에서 64까지일 수 있으므로 l을 보내지 말고 n과 m을 보내십시오. 둘 다 0일 수 있고 64까지 올라갈 필요가 없기 때문입니다(단지 64에 더할 수 있으면 됩니다).

l 비트는 1로 시작하고 끝나야 하므로 전송할 필요가 없습니다.

n에 대해 6비트를 보냅니다.
m에 대해 최대 6비트를 전송합니다(아래 참조).
l = 64 - (n + m) 계산
l = 0이면 숫자는 0입니다. 다른 것은 보내지 마세요.
l = 1이면 숫자는 1 * 2^m입니다. 다른 것은 보내지 마세요.
l = 2이면 숫자는 3 * 2^m입니다. 다른 것은 보내지 마세요.
중간 l - 2비트를 보냅니다.

최대 오버헤드 = 10비트.

m에 대한 비트 감소는 다음과 같습니다.
n > 32이면 m < 32라는 것을 알 수 있으므로 5비트만 필요합니다.
n > 48이면 m < 16이라는 것을 알 수 있으므로 4비트만 필요합니다.
n > 56이면 m < 8이라는 것을 알 수 있으므로 3비트만 필요합니다.
n > 60이면 m < 4라는 것을 알 수 있으므로 2비트만 필요합니다.
n = 63이면 m < 2라는 것을 알 수 있으므로 1비트만 필요합니다.

Answer 2

귀하의 분석은 단일 값에 적합한 것 같습니다.그러나 이러한 값을 많이 함께 전송하는 경우 gzip과 같은 일반 엔트로피 인코딩 알고리즘이 더 나은 성능을 발휘할 것입니다. 0으로 구성된 문자열을 꽤 잘 제거하고 데이터의 중복성을 활용할 수도 있기 때문입니다.

Answer 3

당신이 문제를 언급했듯이, 당신이 제안한 해결책보다 더 나은 것을 할 수는 없습니다.

그러나 숫자에서 0의 분포가 왜곡된 경우 허프만 코드 또는 유사한 기술을 사용하여 개수를 표시하면 평균적으로 더 나은 압축을 얻을 수 있습니다.또 다른 가능성은 0 분포가 하나의 64비트 값에서 다음 값으로 강하게 연관되어 있는 경우 델타 코딩을 사용하는 것입니다.

두 경우 모두 0의 수를 나타내기 위해 가변 비트 수를 사용해야 합니다.그리고 왜곡이나 상관 관계에 대한 가정이 잘못된 것으로 판명되면 간단한 방법으로 수행한 경우보다 평균적으로 더 많은 비트를 사용하게 될 수 있습니다.

Answer 4

귀하의 솔루션은 꽤 좋은 것 같습니다.
허프만 코딩 특히 빈도가 높은 값이 있는 경우 값을 압축하는 또 다른 방법입니다.

구현이 크게 어렵지는 않지만, 전송할 데이터가 많지 않다면 부담스러울 수도 있습니다.

Answer 5

있다 64 가능한 시작 위치 n 1의 시퀀스와 시퀀스의 길이 l 그러면 더 이상은 안 돼 64 - n.그래서 거기에

r = sum(n = 0..63, 64 - n) + 1

총 시퀀스.추가된 것은 모두 0으로 이루어진 시퀀스에 대한 것입니다.수학을 하면 다음과 같은 결과가 나옵니다.

r = 64 * 64 - (63 * 64) / 2 + 1
  = 2081

2081개의 가능한 값을 표현하려면 다음이 필요합니다. log2(2081) = 11.023 비트.두 가지를 사용하여 정보를 인코딩하라는 제안 6 필요한 비트 수 12 따라서 총 비트 수는 최적입니다(가능한 모든 값의 균등 분포 가정 하에서).