Quais são algumas alternativas para uma matriz de bits?

Question

Eu tenho um aplicativo de recuperação de informações que cria matrizes de bits da ordem de dezenas de milhões de bits.O número de bits "definidos" na matriz varia amplamente, de todos limpos a todos definidos.Atualmente, estou usando uma matriz de bits simples (java.util.BitSet), então cada uma das minhas matrizes de bits ocupa vários megabytes.

Meu plano é observar a cardinalidade do primeiro N bits e, em seguida, tome uma decisão sobre qual estrutura de dados usar para o restante.Claramente, algumas estruturas de dados são melhores para matrizes de bits muito esparsas e outras quando aproximadamente metade dos bits está definida (quando a maioria dos bits está definida, posso usar a negação para tratá-la como um conjunto esparso de zeros).

• Que estruturas podem ser boas em cada extremo?
• Tem algum no meio?

Aqui estão algumas restrições ou dicas:

1. Os bits são definidos apenas uma vez e em ordem de índice.
2. Preciso de 100% de precisão, então algo como um filtro Bloom não é bom o suficiente.
3. Depois que o conjunto for construído, preciso ser capaz de iterar com eficiência os bits do "conjunto".
4. Os bits são distribuídos aleatoriamente, portanto, os algoritmos de codificação de comprimento de execução provavelmente não serão muito melhores do que uma simples lista de índices de bits.
5. Estou tentando otimizar a utilização da memória, mas a velocidade ainda carrega alguns peso.

Algo com uma implementação Java de código aberto é útil, mas não é estritamente necessário.Estou mais interessado nos fundamentos.

Answer 1

A menos que os dados sejam verdadeiramente aleatórios e tem uma distribuição simétrica 1/0, então isso simplesmente se torna um problema de compactação de dados sem perdas e é muito análogo à compactação CCITT Grupo 3 usada para preto e branco (ou seja:Binário) Imagens de FAX.CCITT Grupo 3 usa um esquema de codificação Huffman.No caso do FAX eles usam um conjunto fixo de códigos Huffman, mas para um determinado conjunto de dados, você pode gerar um conjunto específico de códigos para cada conjunto de dados para melhorar a taxa de compressão alcançada.Contanto que você só precise acessar os bits sequencialmente, como você sugeriu, essa será uma abordagem bastante eficiente.O acesso aleatório criaria alguns desafios adicionais, mas você provavelmente poderia gerar um índice de árvore de pesquisa binária para vários pontos de deslocamento na matriz que permitiria chegar perto do local desejado e depois entrar a partir daí.

Observação:O esquema de Huffman ainda funciona bem mesmo que os dados sejam aleatórios, desde que a distribuição 1/0 não seja perfeitamente uniforme.Ou seja, quanto menos uniforme for a distribuição, melhor será a taxa de compressão.

Finalmente, se os bits são verdadeiramente aleatórios com uma distribuição par, então, bem, de acordo com Senhor.Claude Shannon, você não conseguirá compactá-lo em uma quantidade significativa usando nenhum esquema.

Answer 2

Eu consideraria fortemente o uso da codificação de intervalo no lugar da codificação de Huffman.Em geral, a codificação de intervalo pode explorar a assimetria de forma mais eficaz do que a codificação de Huffman, mas isso ocorre especialmente quando o tamanho do alfabeto é tão pequeno.Na verdade, quando o "alfabeto nativo" é simplesmente 0s e 1s, a única maneira de Huffman conseguir qualquer compressão é combinando esses símbolos - que é exatamente o que a codificação de intervalo fará, de forma mais eficaz.

Answer 3

Talvez seja tarde demais para você, mas existe uma biblioteca muito rápida e com uso eficiente de memória para matrizes de bits esparsas (sem perdas) e outros tipos de dados baseados em tentativas.Olhe para Matrizes Judy

Answer 4

Obrigado pelas respostas.Isto é o que vou tentar para escolher dinamicamente o método certo:

Vou coletar todos os primeiros N hits em uma matriz de bits convencional e escolha um dos três métodos, com base na simetria desta amostra.

• Se a amostra for altamente assimétrica, simplesmente armazenarei os índices nos bits definidos (ou talvez a distância até o próximo bit) em uma lista.
• Se a amostra for altamente simétrica, continuarei usando uma matriz de bits convencional.
• Se a amostra for moderadamente simétrica, usarei um método de compressão sem perdas como a codificação de Huffman sugerido por Inscitekjeff.

Os limites entre as regiões assimétricas, moderadas e simétricas dependerão do tempo exigido pelos vários algoritmos equilibrados em relação ao espaço de que necessitam, onde o valor relativo do tempo versus espaço seria um parâmetro ajustável.O espaço necessário para a codificação de Huffman é uma função da simetria, e traçarei o perfil disso com testes.Além disso, testarei todos os três métodos para determinar os requisitos de tempo da minha implementação.

É possível (e na verdade espero) que o método de compactação intermediária seja sempre melhor que a lista ou a matriz de bits ou ambos.Talvez eu possa encorajar isso escolhendo um conjunto de códigos de Huffman adaptados para maior ou menor simetria.Então posso simplificar o sistema e usar apenas dois métodos.

Answer 5

Mais um pensamento de compressão:

Se a matriz de bits não for muito longa, você pode tentar aplicar o Transformada Burrows-Wheeler antes de usar qualquer codificação de repetição, como Huffman.Uma implementação ingênua levaria memória O(n^2) durante a (des)compressão e tempo O(n^2 log n) para descompactar - é quase certo que também existem atalhos disponíveis.Mas se houver alguma estrutura sequencial em seus dados, isso deve realmente ajudar na codificação de Huffman.

Você também pode aplicar essa ideia a um bloco de cada vez para manter o uso de tempo/memória mais prático.Usar um bloco por vez pode permitir que você sempre mantenha a maior parte da estrutura de dados compactada se estiver lendo/gravando sequencialmente.

Answer 6

A compactação direta e sem perdas é o caminho a percorrer.Para torná-lo pesquisável, você terá que compactar blocos relativamente pequenos e criar um índice em uma matriz de blocos.Este índice pode conter o deslocamento do bit inicial em cada bloco.

Answer 7

Prova combinatória rápida de que você não pode economizar muito espaço:

Suponha que você tenha um subconjunto arbitrário de n/2 bits definido como 1 de um total de n bits.Você tem (n escolha n/2) possibilidades.Usando Fórmula de Stirling, isso é aproximadamente 2^n / sqrt(n) * sqrt(2/pi).Se todas as possibilidades forem igualmente prováveis, então não há como dar às escolhas mais prováveis ​​representações mais curtas.Portanto, precisamos de log_2 (n escolha n/2) bits, que é cerca de n - (1/2)log(n) bits.

Isso não é uma economia de memória muito boa.Por exemplo, se você estiver trabalhando com n = 2 ^ 20 (1 mega), poderá salvar apenas cerca de 10 bits.Simplesmente não vale a pena.

Dito tudo isso, também parece muito improvável que quaisquer dados realmente úteis sejam verdadeiramente aleatórios.Caso haja mais estrutura em seus dados, provavelmente há uma resposta mais otimista.