Où puis-je trouver un algorithme de compression sans perte, qui produit des sorties sans en-tête?

Question

Est-ce que quelqu'un d'entre vous connaît un algorithme de compression sans perte, qui produit des sorties sans en-tête? Par exemple, ne stockez pas le huffman tree utilisé pour le compresser? Je ne parle pas des arbres de Huffman codés en dur, mais j'aime savoir s'il y a un algorithme qui peut compresser et décompresser l'entrée sans stocker certaines métadonnées dans sa sortie. Ou est-ce même théoriquement impossible?

Answer 1

Adaptive Huffman coding fait exactement cela. Plus généralement, le terme adaptive coding est utilisé pour décrire entropy codes avec cette propriété. Certains dictionary codes ont également cette propriété, par ex. run-length encoding (RLE) et Lempel-Ziv-Welch (LZW). Pourquoi cherchez-vous des algorithmes de compression avec une sortie compressée sans en-tête?

Answer 2

Run Length Encoding serait un exemple

Answer 3

Bien sûr, il est posible. Entre autres, la famille de compresseurs LZ n'a pas besoin de produire quoi que ce soit en dehors des données compressées, car le dictionnaire est construit en ligne au fur et à mesure de la progression de la compression (ou de la décompression). Vous avez beaucoup d'implémentations de référence pour ces algorithmes de type LZ. Par exemple, LZMA, composant de 7zip.

Answer 4

lzo vient à l'esprit. il est utilisé dans OpenVPN, avec d'excellents résultats

Answer 5

Pourquoi? Peut-être (a) vous avez un système comme la téléphonie bidirectionnelle qui a besoin d'une compression/décompression en continu à faible latence. La catégorie de codage adaptatif des algorithmes de compression mentionnés par Zach Scrivena et la famille LZ de dictionary compression algorithmes mentionnés par Diego Sevilla et Javier sont excellents pour ce genre d'application. Les implémentations pratiques de ces algorithmes ont généralement un octet ou deux de métadonnées au début (ce qui les rend inutiles pour les applications (b)), mais cela a peu ou pas d'effet sur la latence. Peut-être (b) vous vous intéressez principalement à la cryptographie, et vous savez que compresser avant crypter donne des propriétés de sécurité améliorées, tant que le texte compressé n'a pas d'en-tête de métadonnées fixe "crib". Les algorithmes de cryptage modernes ne sont pas (pour autant que nous le sachions) vulnérables à ces "crèches", mais si vous êtes paranoïaque vous pourriez être intéressé par "compression bijective" (a, b, c, etc.). Il n'est pas possible de détecter les erreurs de transmission (bits retournés, bits insérés, bits supprimés, etc.) lorsqu'un récepteur reçoit une telle sortie compressée (rendant ces algorithmes non particulièrement utiles pour les applications (a)).

Peut-être (c) vous êtes intéressé par la compression sans en-tête pour une autre raison. Cela semble fascinant - quelle est cette raison?