Quel est l'état actuel des algorithmes de compression de type text-only?

Question

En l'honneur de la Hutter Prize, quels sont les meilleurs algorithmes (et une description rapide de chacun) pour la compression de texte?

Remarque: L'objectif de cette question est d'obtenir une description des algorithmes de compression, et non des programmes de compression.

Answer 1

Les compresseurs poussant les limites combinent des algorithmes pour obtenir des résultats insensés. algorithmes communs comprennent:

• Le Burrows-Wheeler Transform et here - caractères shuffle (ou d'autres blocs de bits) avec un algorithme prévisible pour augmenter les blocs répétés qui rend la source plus facile à compresser. La décompression se produit normalement et le résultat n'est pas mélangé avec la transformation inverse. Remarque: BWT seul ne compresse réellement rien. Cela rend la source plus facile à compresser.
• Prediction by Partial Matching (PPM) - une évolution de arithmetic coding où le modèle de prédiction (contexte) est créé en calculant des statistiques sur la source par rapport aux probabilités statiques. Même si ses racines sont en codage arithmétique, le résultat peut être représenté avec un codage Huffman ou un dictionnaire ainsi qu'un codage arithmétique.
• Mixage de contextes - Le codage arithmétique utilise un contexte statique pour la prédiction, PPM choisit dynamiquement un contexte unique, Context Mixing utilise de nombreux contextes et pèse les résultats. PAQ utilise le mélange de contextes. Here's une vue d'ensemble de haut niveau.
• Dynamic Markov Compression - en rapport avec PPM mais utilise des contextes de niveau de bits par rapport aux octets ou plus. En outre, les participants au prix Hutter peuvent remplacer le texte courant par des entrées de petit octet provenant de dictionnaires externes et différencier les majuscules et les minuscules par un symbole spécial par rapport à deux entrées distinctes. C'est pourquoi ils sont si bons à compresser le texte (en particulier le texte ASCII) et pas aussi précieux pour la compression générale.

Maximum Compression est un site de test de compression de texte et de compression général. Matt Mahoney publie un autre benchmark. Mahoney peut être d'un intérêt particulier car il répertorie l'algorithme principal utilisé par entrée.

Answer 2

Il y a toujours lzip.

Blague à part:

• Si la compatibilité est une préoccupation, PKZIP (DEFLATE algorithme) gagne encore.
• bzip2 est le meilleur compromis entre profiter d'une base d'installation relativement large et d'un taux de compression plutôt bon, mais nécessite un archiveur séparé.
• 7-Zip (LZMA algorithme) compresse très bien et est disponible pour sous la LGPL. Cependant, peu de systèmes d'exploitation sont livrés avec un support intégré.
• rzip est une variante de bzip2 qui, à mon avis mérite plus d'attention. Cela pourrait être particulièrement intéressant pour les gros fichiers journaux qui nécessitent un archivage à long terme. Il nécessite également un archiveur séparé.

Answer 3

Si vous souhaitez utiliser PAQ en tant que programme, vous pouvez installer le package zpaq sur les systèmes basés sur Debian.L'utilisation est (voir aussi man zpaq)

zpaq c archivename.zpaq file1 file2 file3 

compression était à environ 1/10ème de la taille d'un fichier zip. (1.9M vs 15M)