Meilleure réponse
Si par « meilleur » vous entendez le taux de compression, alors selon le Large Text Compression Benchmark cest CMIX. Le seul problème est que vous avez besoin dun ordinateur avec 32 Go de mémoire pour lexécuter. Et puis il faudra 4 jours pour compresser ou décompresser 1 Go de texte.
Comme la plupart des programmes les mieux classés, CMIX utilise le prétraitement du dictionnaire et le mélange de contexte de style PAQ. Le préprocesseur remplace les mots par des symboles de 1 à 3 bits dun dictionnaire et effectue dautres traitements tels que le remplacement des lettres majuscules par un symbole spécial et le symbole minuscule correspondant. Il peut également analyser les préfixes et suffixes communs.
Un modèle de contexte prend un contexte (par exemple, les n derniers bits) et devine une probabilité p que le bit suivant sera un 0 ou 1. Le résultat est transmis à un codeur arithmétique, qui code le bit très proche de la limite de Shannon de log2 1 / p bits. Le taux de compression dépend donc entièrement de la façon dont p est estimé. Un algorithme de mélange de contexte fait des prédictions très précises en combinant les prédictions de nombreux modèles indépendants. CMIX utilise plusieurs centaines de modèles, cest pourquoi il nécessite tant de temps et de mémoire. La raison pour laquelle il existe tant de modèles est quil existe de nombreux contextes possibles, de nombreuses façons de convertir un contexte en prédiction, de nombreuses façons de mettre à jour le modèle et de nombreuses façons de combiner de manière adaptative les prédictions dautres modèles et de sélectionner les meilleurs à laide de une hiérarchie de mélangeurs. Les mélangeurs de contexte pratiques peuvent utiliser de 2 à 20 modèles, sacrifiant une partie de la compression pour la simplicité et la convivialité.
Les meilleurs compresseurs sont proches de la compréhension texte. Ils modélisent la structure lexicale, sémantique et grammaticale de la langue. Par exemple, le dictionnaire est organisé en regroupant des mots apparentés, tels que mère avec père et lundi avec mardi . Il en résulte des codes de dictionnaire qui ne diffèrent que par les bits faibles. Ensuite, certains des modèles de contexte abandonneront les bits faibles, permettant au compresseur de prédire Jai vu mon père lundi après avoir vu Jai vu ma mère mardi .
Les détails techniques peuvent être assez compliqués. Si vous souhaitez en savoir plus, consultez Explication de la compression des données .
Réponse
En supposant que vous parlez de sans perte compression (les textes peuvent être compressés avec perte avec le langage SMS par exemple), il est bien connu que vous ne pouvez pas compresser sans perte « nimporte quel » fichier binaire. En dautres termes, certains fichiers verront leur taille augmentée. Cela est dû aux fichiers den-tête du codeur et aux mathématiques de base des bijections impossibles entre [0, …, N] et [0, …, N-1], ou au principe du pigeon-trou de Dirichlet (Schubfachprinzip). Voir http://en.wikipedia.org/wiki/Pigeonhole\_principle
Comme dit précédemment, « meilleur » fait généralement référence à un taux de compression moyen @ Sam-Jp. Le jeu de caractères des textes (par exemple, ascii 7 ou 8 bits compte) et leur type est également important. La « meilleure compression » sur les fichiers texte écrits en langage humain pur se comporte différemment sur les fichiers postscript, rtf, doc ou même pdf contenant du texte, car certains formats encapsulent déjà la compression. Par conséquent, le « meilleur » taux de compression dépend du contenu de la base de données, de lhomogénéité et de la typologie des fichiers texte, comme le montre la compression de texte anglais donnée dans le lien @ Igor-Carron: http://www.maximumcompression.com/data/text.php
Speed @ Jonathan-Hseu est également très important. En fonction de votre application (de larchivage aux interactions avec la base de données @ Daniel-Lemire), on se concentre soit sur la vitesse de compression ou de décompression (généralement une fois, décompresser plusieurs), ou les deux.
Mais dautres fonctionnalités peuvent être évaluées comme eh bien, surtout avec lavènement dénormes ensembles de données et de systèmes dacquisition diversifiés: -performance daccès aléatoire ou capacité de recherche dans les fichiers compressés -résilience derreur (résistance aux bits corrompus) -capacité en ligne, cest-à-dire être capable de compresser efficacement le flux de données au fur et à mesure compression de textes structurés non seulement dans un ordre raster mais en arborescence, graphes – faible complexité ou efficacité énergétique du codeur, ou décodeur, ou les deux – parallélisation possible – possibilité de codage distribué (travail de compression partagé à différents nœuds dun réseau)
Finalement, même pour le texte, on peut sortir de la boîte sans perte. Et nous revenons aux SMS précédemment cités, où le sens est important, mais peut-être pas lorthographe correcte, voir par exempleKaufman & Klein, Compression semi-sans perte http://www.computer.org/portal/web/csdl/doi/10.1109/DCC.2004.1281520
Comme dhabitude, poser la question du « meilleur » résout en affinant la question du but réel, en définissant des métriques de qualité et pondération appropriée de ces métriques pour définir « votre » meilleur @ Alex-Kamil. Les sujets des sources suivantes sont inspirants:
* Transactions IEEE sur la théorie de linformation http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=18 * Transactions IRE sur la théorie de linformation http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=4547527 * Data Compression Conference pages.cs.brandeis.edu/~dcc/
Enfin, nétant pas spécialiste mais amateur de la compression sans perte, jai récemment été étonné par les performances (en taux de compression) de Deplump (http://www.deplump.com/index.html) sur de longs fichiers texte anglais et quelques fichiers binaires (en comparaison avec mes favoris rar, Bzip2 et 7zip cités dans dautres réponses). Vous pouvez le tester pour de courts fichiers en ligne. Pour plus dinformations, consultez F. Wood et al. The Sequence Memoizer, 2011 (voir http://www.sequencememoizer.com/) ou la page Web de Franck Wood http://www.stat.columbia.edu/~fwood/