Um algoritmo de compactação eficiente para cadeias de texto curtas

Eu estou procurando por 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 strings muito curtas.

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

Existem versões adaptativas que eliminam isso, mas a taxa de compression pode sofrer. Na verdade, a pergunta que você deve fazer é “qual algoritmo para compactar strings 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 em inglês, espaços, pontuação e os dígitos ocasionais estarão presentes, então Huffman com uma tabela Huffman pré-definida pode produzir bons resultados.

Geralmente, os algoritmos da família Lempel-Ziv têm uma compression e desempenho muito bons, 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 de compactar (com qualquer algoritmo que esteja facilmente disponível), você as codifique. URLs seguem padrões bem definidos, e algumas partes são altamente previsíveis. Ao usar esse conhecimento, você pode codificar as URLs em algo menor para começar, e as ideias por trás da codificação Huffman podem ajudá-lo aqui.

Por exemplo, traduzindo a URL em um stream de bits, você poderia replace “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 descartado por completo, desde que você possa marcar o final do protocolo. Etc. Leia sobre o formato de URL e pense em como eles podem ser codificados para ocupar menos espaço.

Eu não tenho código para entregar, mas sempre gostei da abordagem de construir uma tabela de consulta 2D de tamanho 256 * 256 caracteres ( RFC 1978 , PPP Predictor Compression Protocol ). Para compactar uma string, você faz um loop em cada caractere e usa a tabela de consulta para obter o próximo caractere “previsto” usando os caracteres atual e anterior como índices na tabela. Se houver uma correspondência, você escreverá um único bit de 1, caso contrário, escreva um 0, o caractere e atualize a tabela de consulta 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 stream de dados.

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

Esse algoritmo não fornece uma taxa de compactação shiny, mas é incrivelmente econômico com resources de memory e CPU e também pode funcionar em um stream contínuo de dados – o descompactador mantém sua própria cópia da tabela de consulta conforme ela é descompactada. ajusta-se ao tipo de dados que está sendo compactado.

Qualquer algoritmo / biblioteca que suporte um dictionary predefinido, por exemplo, zlib .

Dessa forma, você pode preparar o compressor com o mesmo tipo de texto que provavelmente aparecerá na input. Se os arquivos são semelhantes de alguma forma (por exemplo, todas as URLs, todos os programas em C, todos os posts do StackOverflow, todos os desenhos de arte ASCII), então algumas subseqüências aparecerão na maioria ou em todos os arquivos de input.

Todo algoritmo de compactação economizará espaço se a mesma subseqüência for repetida várias vezes em um arquivo de input (por exemplo, “o” em texto em inglês ou “int” em código C.)

Mas, no caso de URLs, certas cadeias de caracteres (por exemplo, ” http: // www .”, “.Com”, “.html”, “.aspx” geralmente aparecem uma vez em cada arquivo de input. Portanto, é necessário compartilhá-las entre arquivos de alguma forma, em vez de ter uma ocorrência compactada por arquivo. Colocá-los em um dictionary predefinido conseguirá isso.

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

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

A Wikipedia tem uma lista de tempos de compactação. (procure por 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 querer dar uma olhada no Esquema de Compactação Padrão para Unicode .

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