Qual é a maneira mais eficiente de armazenar um intervalo numérico?

Esta pergunta é sobre quantos bits são necessários para armazenar um intervalo. Ou, em outras palavras, para um determinado número de bits, qual é o alcance máximo que pode ser armazenado e como?

Imagine que queremos armazenar um sub-intervalo dentro do intervalo de 0 a 255.

Então, por exemplo, 45-74.

Podemos armazenar o exemplo acima como dois bytes não assinados, mas me parece que deve haver alguma redundância de informações lá. Sabemos que o segundo valor é maior que o primeiro, portanto, no caso em que o primeiro valor é grande, menos bits são necessários para o segundo valor e, no caso em que o segundo valor é grande, menos bits são necessários para o primeiro .

Eu suspeito que qualquer técnica de compactação produziria um resultado marginal; portanto, pode ser uma pergunta melhor perguntar "qual é o intervalo máximo que pode ser armazenado em um byte?". Isso deve ser maior do que o possível, armazenando os dois números separadamente.

Existem algoritmos padrão para fazer esse tipo de coisa?

Apenas conte o número de intervalos possíveis. Existem 256 intervalos com o limite inferior 0 (0-0, 0-1, ... 0-254, 0-255), 255 intervalos com o limite inferior 1, ... e, finalmente, 1 intervalo com o limite inferior 255 (255- 255) Portanto, o número total é (256 + 255 + ... + 1) = 257 * 128 = 32.896. Como isso é um pouco maior que 2 ¹⁵ = 32.768, você ainda precisará de pelo menos 16 bits (2 bytes) para armazenar essas informações.

Em geral, para números de 0 a n-1, o número de intervalos possíveis é n * (n + 1) / 2. Isso é menor que 256 se n for 22 ou menos: n = 22 fornece 22 * ​​23/2 = 253 possibilidades. Portanto, um byte é suficiente para subintervalos de 0 a 21 .

Outra maneira de analisar o problema é o seguinte: armazenar um par de números inteiros no intervalo de 0 a n-1 é quase o mesmo que armazenar um subintervalo de 0- (n-1) mais um único bit que determina se o primeiro número é menor ou maior que o segundo. (A diferença vem do caso em que ambos os números inteiros são iguais, mas essa chance se torna cada vez menor à medida que n aumenta.) É por isso que você só pode economizar um único bit com essa técnica e, provavelmente, a principal razão pela qual ela raramente é usada.

Para um número tão pequeno de bits, é inviável salvar muitos bits, como apontou Glorfindel . No entanto, se o domínio que você está usando tiver mais alguns bits, você poderá obter economias significativas para o caso médio, codificando intervalos com o valor inicial e um delta.

Vamos supor que o domínio seja o número inteiro, então 32 bits. Com a abordagem ingênua, você precisa de 64 bits (início, fim) para armazenar um intervalo.

Se mudarmos para uma codificação de (start, delta), podemos construir o final do intervalo a partir disso. Sabemos que, no pior dos casos, o início é 0 e o delta tem 32 bits.

2 ^ 5 é 32, então codificamos o comprimento do delta em cinco bits (sem comprimento zero, sempre adicione 1), e a codificação se torna (início, comprimento, delta). Na pior das hipóteses, isso custa 32 * 2 + 5 bits, então 69 bits. Portanto, no pior caso, se todos os intervalos forem longos, isso será pior do que a codificação ingênua.

Na melhor das hipóteses, custa 32 + 5 + 1 = 38 bits.

Isso significa que, se você precisar codificar muitos intervalos, e cada um deles cobrir apenas uma pequena parte do seu domínio, você acaba gastando menos espaço, em média, usando essa codificação. Não importa como as partidas são distribuídas, uma vez que a partida sempre terá 32 bits, mas importa como os comprimentos dos intervalos são distribuídos. Se os comprimentos mais pequenos que você tiver, melhor a compactação, mais os intervalos que cobrirão todo o comprimento do domínio, pior será a codificação.

No entanto, se você tiver vários intervalos agrupados em torno de pontos de partida semelhantes (por exemplo, porque obtém valores de um sensor), poderá obter economias ainda maiores. Você pode aplicar a mesma técnica ao valor inicial e usar um viés para compensar o valor inicial.

Digamos que você tenha 10000 intervalos. Os intervalos são agrupados em torno de um determinado valor. Você codifica o viés com 32 bits.

Usando a abordagem ingênua, você precisaria de 32 * 2 * 10 000 = 640 000 bits para armazenar todos esses intervalos.

A codificação da polarização leva 32 bits e, na melhor das hipóteses, a codificação de cada intervalo 5 + 1 + 5 + 1 = 12 bits, para um total de 120 000 + 32 = 120 032 bits. Na pior das hipóteses, você precisa de 5 + 32 + 5 + 32 bits, portanto 74 bits, para um total de 740 032 bits.

Isso significa que, para 10.000 valores em um domínio que leva 32 bits para codificar, obtemos

• 120 032 bits com a codificação delta inteligente na melhor das hipóteses
• 640 000 bits com a codificação inicial, final e sempre ingênua (sem melhor ou pior caso)
• 740 032 bits com a codificação delta inteligente, na pior das hipóteses

Se você usar a codificação ingênua como linha de base, isso significa uma economia de até 81,25% ou um custo até 15,625% maior.

Dependendo de como seus valores são distribuídos, essas economias são significativas. Conheça o domínio da sua empresa! Saiba o que você deseja codificar.

Como extensão, você também pode alterar o viés. Se você analisar os dados e identificar grupos de valores, poderá classificá-los em intervalos e codificar cada um deles separadamente, com seu próprio viés. Isso significa que você pode aplicar essa técnica não apenas a intervalos agrupados em torno de um único valor inicial, mas também a intervalos agrupados em torno de vários valores.

Se seus pontos de partida são distribuídos igualmente, essa codificação não funciona muito bem.

Essa codificação é obviamente extremamente ruim para indexar. Você não pode simplesmente ler o valor x-ésimo. Só pode ser lido apenas sequencialmente. O que é apropriado em algumas situações, por exemplo, streaming na rede ou armazenamento em massa (por exemplo, em fita ou HD).

Avaliar os dados, agrupá-los e escolher o viés correto pode ser um trabalho substancial e pode exigir algum ajuste fino para obter melhores resultados.

Esse tipo de problema é o assunto do artigo seminal de Claude Shannon, Uma teoria matemática da comunicação , que introduziu a palavra “bit” e compactação de dados mais ou menos inventada.

A idéia geral é que o número de bits usados ​​para codificar um intervalo é inversamente proporcional à probabilidade desse intervalo ocorrer. Por exemplo, suponha que o intervalo 45-74 apareça cerca de 1/4 do tempo. Você pode dizer que a sequência 00 corresponde a 45-74. Para codificar o intervalo 45-74, você gera "00" e para aí.

Suponhamos também que os intervalos 99-100 e 140-155 apareçam aproximadamente 1/8 das vezes. Você pode codificar cada um deles com uma sequência de 3 bits. Qualquer 3 bits funcionará desde que não comece com "00", que já foi reservado para o intervalo de 45 a 74.

00: 45-74
010: 99-100
101: 140-155

Você pode continuar dessa maneira até que todo intervalo possível tenha uma codificação. O intervalo menos provável pode precisar de mais de 100 bits. Mas tudo bem, porque raramente aparece.

Não são algoritmos para encontrar o melhor codificação. Não vou tentar explicá-los aqui, mas você pode encontrar mais acessando o link acima ou pesquisando “Theory Information”, “Shannon-fano coding” ou “Huffman coding”.

Como outros já apontaram, provavelmente é melhor armazenar o número inicial e a diferença entre o número inicial e o final. Você deve usar uma codificação para o início e outra para a diferença, pois elas têm distribuições de probabilidade diferentes (e acho que a última é mais redundante). Conforme sugerido pelo polygnome, o melhor algoritmo depende do seu domínio.

Para expandir a resposta de @Glorfindel:

Como n → ∞, (n - 1) → n. Assim, Ω (faixas) → n² / 2 e log (Ω (faixas)) → (2n - 1). Como a codificação ingênua leva 2n bits, a compressão máxima assintótica salva apenas 1 bit.

Há uma resposta semelhante, mas para obter uma compactação ideal, você precisa:

1. Um método ideal de codificação de entropia (leia sobre codificação aritmética e o essencialmente equivalente (mesma taxa de compressão, um pouco mais rápida, mas também mais difícil de entender) ANS )
2. O máximo de informação possível sobre a distribuição dos dados. Fundamentalmente, isso não envolve apenas "adivinhar" a frequência com que um número pode aparecer, mas você pode descartar certas possibilidades com certeza. Por exemplo, você pode excluir intervalos de tamanho negativo e, possivelmente, tamanho 0, dependendo de como você define um intervalo válido. Se você tiver vários intervalos para codificar de uma só vez, poderá classificá-los, por exemplo, em ordem decrescente de largura ou aumentar o valor inicial / final, e excluir muitos valores (por exemplo, se você garantir um pedido diminuindo a largura, o intervalo anterior tinha uma largura de 100 e o valor inicial para o próximo é 47, você só precisa considerar as possibilidades de até 147 para valores finais).

É importante ressaltar que o número 2 significa que você deseja codificar as coisas de maneira que os valores mais informativos (por bit codificado) sejam os primeiros. Por exemplo, enquanto eu sugeria a codificação de uma lista classificada "no estado em que se encontra", normalmente seria mais inteligente codificá-la como uma "árvore binária" - ou seja, se elas forem classificadas por largura e você tiver lenelementos, comece pelo elemento de codificação len/2. Diga que tinha largura w. Agora você conhece todos os elementos antes que eles tenham largura em algum lugar em [0, w], e todos os elementos depois dele tenham largura em algum lugar em [w, max val you accept]. Repita de forma recursiva (subdividindo cada lista meia pela metade, etc.) até cobrir os lenelementos (a menos que seja fixo, você desejará codificarlenprimeiro, assim você não precisa se preocupar com tokens finais). Se "max val you accept" estiver realmente aberto, pode ser inteligente primeiro codificar o valor mais alto que realmente aparece nos seus dados, ou seja, o último elemento e, em seguida, fazer o particionamento binário. Novamente, o que for mais informativo por bit primeiro.

Além disso, se você estiver codificando a largura do intervalo primeiro e souber o valor máximo possível com o qual está lidando, obviamente poderá descartar todos os valores iniciais que fariam transbordar ... você entendeu a ideia. Transforme e ordene seus dados de forma que você possa deduzir o máximo possível sobre o restante dos dados ao decodificá-los, e um algoritmo de codificação de entropia ideal garantirá que você não esteja desperdiçando bits na codificação de informações que "já conhece". .