Le meilleur algorithme de compression pour de courtes chaînes de texte

Question

Je suis à la recherche d'un algorithme pour compresser les petites chaînes de texte: 50 à 1000 octets (c'est à dire d'Url). L'algorithme fonctionne le mieux pour cela?

Answer 1

Vérifiez ceci: http://github.com/antirez/smaz/tree/master

"Smaz est une simple bibliothèque de compression particulièrement adapté à la compression très court des chaînes."

Answer 2

Huffman a un coût statique, la table de Huffman, donc je suis en désaccord c'est un bon choix.

Il y a adaptative des versions qui ne sont loin, mais le taux de compression peut en souffrir. En fait, la question à vous poser est "quel algorithme de compresser les chaînes de texte avec ces caractéristiques". Par exemple, si les longues répétitions sont attendus, course simple-Longueur de Codage peut être suffisant. Si vous pouvez garantir que seuls les mots anglais, des espaces, des punctiation et à l'occasion, les chiffres seront présents, alors Huffman avec un pré-définis Huffman table peut donner de bons résultats.

Généralement, les algorithmes de Lempel-Ziv de la famille ont une très bonne compression et de la performance, et les bibliothèques pour leur abondent. J'irais avec ça.

Avec les informations que ce qui est comprimé sont des Url, alors je suggère que, avant de le compresser (avec quel que soit l'algorithme est facilement disponible), vous les CODIFIER. Url suivez bien définie, et certaines parties sont très prévisibles. En faisant usage de cette connaissance, vous pouvez codifier les URLs dans quelque chose de plus petit pour commencer, et les idées derrière le codage Huffman peut vous aider ici.

Par exemple, la traduction de l'URL d'un flux de bits, vous pouvez remplacer "http" avec le bit 1, et rien d'autre avec le bit "0" suivi par le procotol (ou un tableau pour obtenir d'autres protocoles communs, comme https, ftp, fichier). L' "://" peut être éliminé complètement, aussi longtemps que vous pouvez marquer la fin du protocole. Etc. Aller lire à ce sujet le format d'URL, et de réfléchir sur la façon dont ils peuvent être codifiées afin de prendre moins de place.

Answer 3

Je n'ai pas de code à la main, mais j'ai toujours aimé l'approche de la construction d'une 2D table de recherche de taille 256 * 256 caractères (RFC 1978, PPP Prédicteur du Protocole de Compression). Pour compresser une chaîne de boucle sur chaque char et l'utilisation de la table de recherche pour obtenir le "prédire" caractère suivant à l'aide de l'actuelle et de la précédente char comme index dans la table. Si il y a un match, on n'écrire qu'un seul bit à 1, sinon écrire un 0, le char et de mettre à jour la table de correspondance avec le courant de char. Cette approche fondamentalement maintient une dynamique (brut) table de recherche les plus probables caractère suivant dans le flux de données.

Vous pouvez commencer avec une mise à zéro de la table de choix, mais obviosuly il fonctionne mieux sur de très courtes chaînes si elle est initialisée avec les plus susceptibles de caractères pour chaque paire de caractères, par exemple, pour la langue anglaise. Aussi longtemps que la première table de recherche est le même pour la compression et de la décompression, vous n'avez pas besoin de l'émettre dans le comrpessed de données.

Cet algorithme ne donne pas une brillante taux de compression, mais il est très frugal avec de la mémoire et des ressources du PROCESSEUR et peut aussi travailler sur un flux continu de données - le décompresseur maintient sa propre copie de la table de recherche comme il décompresse, donc la table de recherche ajuste pour le type de données comrpessed.

Answer 4

Tout algorithme/bibliothèque qui prend en charge un preset dictionnaire, par exemple, zlib.

De cette façon, vous pouvez amorcer le compresseur avec le même genre de texte qui est susceptible d'apparaître dans l'entrée. Si les fichiers sont similaires, d'une certaine façon (par exemple, toutes les URLs, tous les programmes C, tous les StackOverflow postes, tous ASCII-art, dessins), puis certaines chaînes apparaissent dans la plupart ou tous les fichiers d'entrée.

Chaque algorithme de compression permettra d'économiser de l'espace si le même sous-chaîne est répété plusieurs fois dans le même fichier d'entrée (par exemple, "le" dans un texte en anglais ou "int" dans le code C,.)

Mais dans le cas de l'Url de certaines chaînes de caractères (par exemple "http://www.", ".com", ".html", ".aspx" apparaissent généralement une fois dans chaque fichier d'entrée. Si vous avez besoin de les partager entre les fichiers d'une certaine manière plutôt que d'avoir un comprimé occurrence par fichier. Les placer dans un preset dictionnaire.

Answer 5

Si vous parlez en fait de comprimer le texte et pas seulement raccourcissement Dégonfler/gzip (wrapper autour de gzip), zip fonctionnent bien pour les petits fichiers de texte et de. D'autres algorithmes sont très efficaces pour les gros fichiers comme bzip2 etc.

Wikipedia a une liste de temps de compression. (cherchez la comparaison de l'efficacité)

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