Algorithmes De Compression De Données
je me demandais si quelqu'un a une liste d'algorithmes de compression de données. Je ne sais rien sur la compression de données et j'espérais en savoir plus sur les différents algorithmes et voir lesquels sont les plus récents et doivent encore être développés sur un grand nombre d'ASICs.
j'espère implémenter une compression de données ASIC qui est indépendante du type de données entrant (audio,vidéo,images,etc.)
si ma question est trop ouverte, s'il vous plaît faites-le moi savoir et je vais réviser. Je vous remercie
5 réponses
Il y a une tonne d'algorithmes de compression. Il vous faut un algorithme de compression sans perte. Un algorithme de compression sans perte comprime les données de telle sorte qu'elles puissent être décompressées pour obtenir exactement ce qui a été donné avant la compression. Le contraire serait un algorithme de compression avec perte. La compression avec perte peut supprimer des données d'un fichier. Les images PNG utilisent la compression sans perte alors que les images JPEG peuvent et utilisent souvent la compression avec perte.
Certains des plus connues les algorithmes de compression comprennent:
archives ZIP utilisez une combinaison de codage Huffman et LZ77 pour obtenir des temps de compression et de décompression rapides et taux de compression raisonnablement bons.
LZ77 est à peu près une forme généralisée de RLE et il donnera souvent de bien meilleurs résultats.
Huffman permet le la plupart des octets répétés pour représenter le plus petit nombre de bits. Imaginez un fichier texte qui ressemble à ceci:
aaaaaaaabbbbbcccdd
Une implémentation typique de Huffman entraînerait la carte suivante:
Bits Character
0 a
10 b
110 c
1110 d
ainsi le fichier serait compressé à ceci:
00000000 10101010 10110110 11011101 11000000
^^^^^
Padding bits required
18 octets aller jusqu'à 5. Bien sûr, le tableau doit être inclus dans le fichier. Cet algorithme fonctionne mieux avec plus de données :P
Alex Allain a un bel article sur le Huffman Algorithme de Compression au cas où le Wiki ne suffirait pas.
n'hésitez pas à demander pour plus d'informations. Cette rubrique est vachement large.
Il y a beaucoup d'algorithmes de compression de données autour de. Si vous cherchez quelque chose d'encyclopédique, je recommande l' Guide de la Compression de Données par Salomon et al, qui est à peu près aussi complet que vous êtes susceptible d'obtenir (et a de bonnes sections sur les principes et la pratique de la compression des données, ainsi).
Ma meilleure supposition est que la compression basée sur ASIC est habituellement implémentée pour une application particulière, ou comme un élément spécialisé d'un SoC, plutôt que comme une puce de compression autonome. Je doute également que la recherche d'un format de compression "le plus récent et le plus grand" soit la façon d'y aller -- je m'attendrais à ce que la normalisation, la maturité et l'adaptation à un but particulier soient plus importantes.
voici quelques algorithmes sans perte (peuvent parfaitement récupérer les données originales en utilisant ceux-ci):
- code Huffman
- LZ78 (et LZW variation)
- LZ77
- codage Arithmétique
- Sequitur
- prédiction avec correspondance partielle (ppm)
beaucoup de formats bien connus comme png ou gif utilisent des variantes ou des combinaisons de ceux-ci.
d'un autre côté, il y a aussi des algorithmes de perte (compromis précision pour compresser vos données, mais fonctionne souvent assez bien). Les techniques de pointe de la perte combinent des idées de codage différentiel, quantification, et DCT, entre autres.
pour en savoir plus sur la compression des données, je recommande https://www.elsevier.com/books/introduction-to-data-compression/sayood/978-0-12-809474-7. Il s'agit d'un texte d'introduction très accessible. La 3e édition disponible en pdf en ligne.
mon journal Une Enquête auprès Des Approches Architecturales pour la Compression de Données dans la mémoire Cache et la Mémoire Principale Systèmes (permalink ici) examine de nombreux algorithmes de compression et aussi des techniques pour les utiliser dans les processeurs modernes. Il passe en revue les algorithmes/techniques de compression de qualité recherche et de qualité commerciale, de sorte que vous pouvez trouver un qui n'a pas encore été mis en œuvre dans ASIC.
LZW ou Lempel Ziv algorithme est un grand lossless. Pseudo-code ici: http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lzw.html