A forma mais eficiente para codificar 2 posições entre 0 e 64?

Question

Eu tenho 64 bit valores que eu quero compressa, explorando o fato de que apenas uma parte em algum lugar no meio contém dados e antes e depois que são zeros.

Say os dados reais é L bits de comprimento e preenchido com n 0s em 0s dianteiros e m no final de tal modo que n + m + l = 64. Em vez de transmissão / armazenamento de 64 bits, que pode transmitir L bits mais o que eu necessidade para codificar a posição dos dados no intervalo de 64 bits.

Por exemplo, digamos que eu estava armazenando l, m e os bits de dados, então gostaria de restaurar o padrão 64-bit original, lendo l, lendo L bits de dados, lendo m e transferindo os dados m bits para a esquerda.

O menor sobrecarga I pode chegar a é duas vezes 6 bits para o armazenamento de qualquer dois de l, n e m (cada um pode estar entre 0 e 64). É possível reduzir esse número?

Answer 1

l pode ser de 0 a 64, l por isso não enviar, envie n e m, uma vez que tanto pode ser zero, e não precisa ir até 64 (eles simplesmente precisam de ser capaz de adicionar 64).

Os l bits devem começar e terminar com um 1, para que eles não precisam ser transmitidos.

enviar 6 bits para n
enviar até 6 bits para m (veja abaixo)
Calcular l = 64 - (n + m)
se l = 0, o número é 0, não envie qualquer outra coisa
se l = 1, o número é de 1 * 2 ^ m, não envie qualquer outra coisa
se l = 2, o número é de 3 * 2 ^ m, não envie qualquer outra coisa
enviar o l meio - 2 bits.

= Máximo de sobrecarga de 10 bits.

A redução dos bits para m é porque
se n> 32, então você sabe m <32, então só precisa de 5 bits
se n> 48, então você sabe m <16, então só precisa de 4 bits
se n> 56, então você sabe m <8, então só precisa de 3 bits
se n> 60, então você sabe m <4, portanto, só precisa de 2 bits
se n = 63, então você sabe m <2, então só precisa de 1 bit

Answer 2

Sua análise parece certo para vlaues individuais. Mas se você é lotes de transmissão de tais valores em conjunto, um algoritmo de codificação de entropia genérico como gzip provavelmente vai fazer melhor, uma vez que pode eliminar as cordas de zeros muito bem e também exploram redundâncias nos dados.

Answer 3

Como você indicou o problema, não, você não pode fazer melhor do que a solução que propusemos.

No entanto, se a distribuição dos zeros nos números é distorcida, você pode ser capaz de obter uma melhor compressão, em média, usando códigos Huffman ou uma técnica semelhante para representar as contagens. Outra possibilidade é a utilização delta codificação se a distribuição zero é fortemente correlacionada de um valor de 64 bits para a próxima.

Em ambos os casos, você precisará usar um número variável de bits para representar o número de zeros. E se os seus pressupostos sobre skewedness ou correlação vir a ser falsa, você pode acabar usando mais bits em média, do que se tivesse feito isso de forma simples.

Answer 4

A sua solução parece muito bom.
Huffman codificação é uma outra maneira de comprimir os seus valores, especialmente se existem valores com grande freqüência.

Não é muito difícil de implementar, mas ele pode ser avassaladora se você não tem muitos dados para transmissão.

Answer 5

Existem posições iniciais possíveis 64 n da seqüência de uns e o comprimento do l seqüência pode haver mais tempo, então 64 - n. Portanto, há um

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

sequências no total. A um adicionou-se para uma sequência de zeros. Fazendo alguns rendimentos de matemática o seguinte.

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

Representando 2081 valores possíveis requer pedaços log2(2081) = 11.023. A sua sugestão para codificar a informação utilizando dois números de bits 6 que exigem pedaços 12 no total é, consequentemente, óptimo (com base no pressuposto de distribuições iguais de todos os valores possíveis).