Um algoritmo de compactação eficiente para seqüências de texto curtas [fechado]

Estou procurando um algoritmo para compactar pequenas seqüências de texto: 50-1000 bytes (ou seja, URLs). Qual algoritmo funciona melhor para isso?

Confira o Smaz :

O Smaz é uma biblioteca de compactação simples, adequada para compactar cadeias muito curtas.

Huffman tem um custo estático, a tabela Huffman, então eu discordo que é uma boa escolha.

Existem versões adaptativas que acabam com isso, mas a taxa de compressão pode sofrer. Na verdade, a pergunta que você deve fazer é "qual algoritmo comprimir seqüências de texto com essas características". Por exemplo, se longas repetições são esperadas, a simples codificação Run-Lengh pode ser suficiente. Se você pode garantir que apenas palavras, espaços, pontuação e dígitos ocasionais em inglês estejam presentes, o Huffman com uma tabela Huffman predefinida poderá gerar bons resultados.

Geralmente, os algoritmos da família Lempel-Ziv têm muito boa compactação e desempenho, e as bibliotecas para eles são abundantes. Eu iria com isso.

Com as informações de que o que está sendo compactado são URLs, sugiro que, antes da compactação (com qualquer algoritmo facilmente disponível), você as CODIFIQUE. Os URLs seguem padrões bem definidos e algumas partes são altamente previsíveis. Ao usar esse conhecimento, você pode codificar os URLs em algo menor para começar, e as idéias por trás da codificação Huffman podem ajudá-lo aqui.

Por exemplo, ao traduzir o URL em um fluxo de bits, você pode substituir "http" pelo bit 1 e qualquer outra coisa pelo bit "0" seguido pelo procotol real (ou usar uma tabela para obter outros protocolos comuns, como https, ftp, arquivo). O ": //" pode ser eliminado por completo, desde que você possa marcar o final do protocolo. Etc. Leia sobre o formato da URL e pense em como eles podem ser codificados para ocupar menos espaço.

Não tenho código em mãos, mas sempre gostei da abordagem de criar uma tabela de pesquisa 2D de tamanho 256 * 256 caracteres ( RFC 1978 , PPP Predictor Compression Protocol ). Para compactar uma string, você faz um loop sobre cada caractere e usa a tabela de pesquisa para obter o próximo caractere 'previsto' usando o caractere atual e o anterior como índices na tabela. Se houver uma correspondência, você escreve um único bit 1; caso contrário, escreva um 0, o caractere e atualize a tabela de pesquisa com o caractere atual. Essa abordagem basicamente mantém uma tabela de pesquisa dinâmica (e bruta) do próximo caractere mais provável no fluxo de dados.

Você pode começar com uma tabela de pesquisa zerada, mas obviamente funciona melhor em cadeias muito curtas se for inicializada com o caractere mais provável para cada par de caracteres, por exemplo, para o idioma inglês. Desde que a tabela de pesquisa inicial seja a mesma para compactação e descompactação, você não precisará emiti-la nos dados compactados.

Esse algoritmo não fornece uma taxa de compactação brilhante, mas é incrivelmente econômico com recursos de memória e CPU e também pode trabalhar em um fluxo contínuo de dados - o descompressor mantém sua própria cópia da tabela de pesquisa à medida que descompacta, portanto, a tabela de pesquisa ajusta ao tipo de dados que está sendo compactado.

Qualquer algoritmo / biblioteca que suporte um dicionário predefinido, por exemplo, zlib .

Dessa forma, você pode preparar o compressor com o mesmo tipo de texto que provavelmente aparecerá na entrada. Se os arquivos forem semelhantes de alguma forma (por exemplo, todos os URLs, todos os programas C, todas as postagens StackOverflow, todos os desenhos de arte ASCII), determinadas substrings aparecerão na maioria ou em todos os arquivos de entrada.

Todo algoritmo de compactação economizará espaço se a mesma substring for repetida várias vezes em um arquivo de entrada (por exemplo, "the" no texto em inglês ou "int" no código C.)

Porém, no caso de URLs, certas strings (por exemplo, " http: // www .", ".Com", ".html", ".aspx" geralmente aparecem uma vez em cada arquivo de entrada. Portanto, é necessário compartilhá-las entre os arquivos de alguma forma, em vez de ter uma ocorrência compactada por arquivo, colocando-as em um dicionário predefinido, isso é o

A codificação de Huffman geralmente funciona bem para isso.

Se você está realmente pensando em compactar o texto e não apenas encurtar, em seguida, Deflate / gzip (wrapper em torno do gzip), o zip funciona bem para arquivos e texto menores. Outros algoritmos são altamente eficientes para arquivos maiores, como bzip2 etc.

A Wikipedia possui uma lista de tempos de compactação. (procure comparação de eficiência)

Name       | Text         | Binaries      | Raw images
-----------+--------------+---------------+-------------
7-zip      | 19% in 18.8s | 27% in  59.6s | 50% in 36.4s
bzip2      | 20% in  4.7s | 37% in  32.8s | 51% in 20.0s
rar (2.01) | 23% in 30.0s | 36% in 275.4s | 58% in 52.7s
advzip     | 24% in 21.1s | 37% in  70.6s | 57& in 41.6s
gzip       | 25% in  4.2s | 39% in  23.1s | 60% in  5.4s
zip        | 25% in  4.3s | 39% in  23.3s | 60% in  5.7s

Você pode dar uma olhada no Esquema de compactação padrão para Unicode .

O SQL Server 2008 R2 usa-o internamente e pode atingir até 50% de compactação.