Algorithmes de compression avec petits dictionnaires

Question

Je recherche un algorithme de compression qui fonctionne avec des symboles plus petits qu'un octet. J'ai fait une recherche rapide sur les algorithmes de compression et il est difficile de trouver la taille des symboles utilisés. Quoi qu'il en soit, il y a des flux avec des symboles plus petits que 8 bits. Existe-t-il un paramètre pour DEFLATE pour définir la taille de ses symboles?

Answer 1

symboles de texte en clair plus petit qu'un octet

Les descriptions originales de LZ78 et LZ77 les décrire en termes d'une suite de chiffres décimaux (symboles qui sont approximativement la moitié de la taille d'un octet). Si vous google pour "algorithme de compression d'ADN", vous pouvez obtenir un tas d'informations sur les algorithmes spécialisés pour les fichiers de compression qui sont presque entièrement composé des 4 lettres AGCT, un dictionnaire de 4 symboles, chacun d'environ 1/4 aussi petit qu'un octet. Peut-être que l'un de ces algorithmes pourrait fonctionner pour vous avec relativement peu de peaufinage.

La compression de type LZ77 utilisée dans LZMA peut sembler utiliser deux octets par symbole pour les premiers symboles qu'elle compresse. Mais après avoir compressé quelques centaines de symboles en texte brut (les lettres de texte en langage naturel, ou les séquences de chiffres décimaux, ou les séquences des 4 lettres qui représentent les bases d'ADN, etc.), les "morceaux" compressés à deux octets que LZMA éteint souvent représenter une douzaine ou plus de symboles en clair. (Je soupçonne la même chose pour tous les algorithmes similaires, tels que l'algorithme LZ77 utilisé dans DEFLATE). En principe, si vos fichiers n'utilisent qu'un alphabet restreint de moins de 256 octets, un programmeur pourrait en principe adapter une variante de DEFLATE (ou un autre algorithme) qui pourrait utiliser des informations sur cet alphabet pour produire fichiers compressés de quelques bits plus petits que les mêmes fichiers compressés avec DEFLATE standard. Cependant, de nombreux algorithmes de compression de texte orientés octets - LZ77, LZW, LZMA, DEFLATE, etc. construisent un dictionnaire de chaînes longues communes et peuvent donner des performances de compression (avec un fichier source suffisamment important) à quelques pourcents variante adaptée - les avantages de l'utilisation d'un format de fichier compressé standard valent souvent le sacrifice de quelques pourcents d'économies d'espace potentielles.

symboles compressés plus petits qu'un octet

algorithmes Beaucoup de compression, y compris certains qui donnent la meilleure compression connue sur les fichiers de référence, bit par bit d'information comprimé sortie (comme la plupart des séries de PAQ de compresseurs et certains types de codeurs arithmétiques), tandis que d'autres fournissent des informations compressées de longueur variable sans tenir compte des limites d'octets (telles que la compression de Huffman). Certaines façons de décrire le codage arithmétique parlent de morceaux d'information, tels que des bits individuels ou des pixels, qui sont compressés à «moins d'un bit d'information». L '"argument de comptage" explique pourquoi il n'est pas possible de compresser tous les octets possibles, et encore moins tous les octets possibles et quelques séquences d'octets communes, en mots de code ayant tous une longueur inférieure à 8 bits. Néanmoins, plusieurs algorithmes de compression peuvent représenter et représentent souvent des octets ou (plus rarement) des séquences d'octets, chacune avec un mot de code de moins de 8 bits, en "sacrifiant" ou "échappant" des octets moins courants qui se terminent up représenté par d'autres mots de code qui (y compris le "échappement") sont plus de 8 bits de long.

Ces algorithmes comprennent:

• Le Pike Text compression using 4 bit coding
• octet orienté Huffman
• plusieurs combination algorithms qui font l'analyse syntaxique LZ77 comme du fichier dans « symboles », où chaque symbole représente une séquence de octets, puis Huffman-compression de ces symboles - tels que DEFLATE, LZX, LZH, LZHAM, etc

L'algorithme Pike utilise les 4 bits "01 01 "pour représenter" e "(ou dans certains contextes" E "), les 8 bits" 0000 0001 "pour représenter le mot" le "(4 octets, y compris l'espace avant) (ou dans certains contextes" Le "ou "THE"), etc Il a un petit dictionnaire d'environ 200 des mots anglais les plus fréquents, , y compris un sous-dictionnaire de 16 mots anglais extrêmement communs. Lors de la compression d'un texte en anglais avec un codage Huffman orienté octet, la séquence "e" (espace e) est compressée en deux mots de code avec un total de 6 bits au total. Hélas, lorsque le codage de Huffman est impliqué, je ne peux pas vous dire la taille exacte de ces "petits" mots de code, ou même vous dire exactement quel octet ou séquence d'octets un petit mot de code représente, car il est différent pour chaque fichier . Souvent, le même mot de code représente un octet différent (ou une séquence d'octets différente) à différents emplacements dans le même fichier. Le décodeur détermine quelle séquence d'octets ou d'octets représente un mot de code en fonction des indices laissés par le compresseur dans les en-têtes et des données décompressées jusqu'à présent. Avec le codage de gamme ou le codage arithmétique, le "mot de code" ne peut même pas être un nombre entier de bits.

Answer 2

Vous voudrez peut-être regarder dans un Golomb-Code. Un code golomb utilise un algorithme de division et de conquête pour compresser l'entrée inout. Ce n'est pas une compression de dictionnaire mais ça vaut la peine de le mentionner.