Quelqu'un peut-il donner des pointeurs comment je peux implémenter la compression / la décompression LZW dans des conditions de mémoire faible (<2K). est-ce possible?
8 Réponses :
Ma meilleure recommandation consiste à examiner le Busybox Source et voyez si leur mise en œuvre de LZW est suffisamment petite pour travailler dans votre environnement.
Probablement pas - Busybox est destiné aux systèmes avec beaucoup plus de ressources.
Avez-vous vérifié plutôt que de simplement dire «probablement pas». À peu près, tous les algorithmes de Busybox sont les plus petits (à la fois en taille de code et dans l'espace de travail) que tous les développeurs ont été en mesure de trouver / créer, souvent au détriment des performances décentes. Si la performance est trop mauvaise, il existe généralement une option de compilation pour choisir entre une taille minuscule avec des performances horribles et une taille / performance modérée.
@Tomlogic: La plupart des implémentations de LZW que j'ai vues dans le passé avaient la taille du dictionnaire (mémoire principale) comme une compilation de la compilation définie. Cela vaut la peine de vérifier. La taille minimale du dictionnaire IIRC est de 257 + 1. Mais ce serait un équivalent à aucune compression du tout.
Cela fait plus de 15 ans que je jouais avec l'algorithme de compression LZW, prenez donc ce qui suit avec un grain de sel.
Compte tenu des contraintes de mémoire, cela va être difficile au mieux. Le dictionnaire que vous construisez consomme la grande majorité de ce que vous avez disponible. (En supposant que le code + la mémoire <= 2k.)
Choisissez une petite taille fixe pour votre dictionnaire. Dire 1024 entrées.
Laissez chaque entrée de dictionnaire Prendre la forme de .... Cette structure fait le dictionnaire récursif. Vous avez besoin de l'élément à l'index précédent pour être valide pour pouvoir fonctionner correctement. Est-ce que cela est fonctionnel? Je ne suis pas sûr. Cependant, supposons-nous pour le moment que c'est et découvre où cela nous conduit ... Si vous utilisez les types standard pour INT et de caractères, vous allez épuisé rapidement rapidement. Vous voudrez emballer les choses ensemble aussi bien que possible. 1024 entrées prendront 10 bits pour stocker. Votre nouveau personnage, prendra probablement 8 bits. Total = 18 bits. 18 bits * 1024 entrées = 18432 bits ou 2304 octets. Au premier abord, cela semble trop grand. Qu'est-ce qu'on fait? Profitez du fait que les 256 premières entrées sont déjà connues - votre ensemble d'ASCII étendu typique ou de quoi avez-vous. Cela signifie que nous avons vraiment besoin de 768 entrées. 768 * 18 bits = 13824 bits ou 1728 octets. Cela vous laisse avec environ 320 octets pour jouer avec le code. Naturellement, vous pouvez jouer avec la taille du dictionnaire et voir ce qui est bon pour vous, mais vous ne vous retrouverez pas avec beaucoup d'espace pour votre code. Puisque vous regardez si peu d'espace de code, je m'attendrais à ce que vous finissiez par coder en montage. J'espère que cela aide.
Est-il possible de jeter le dictionnaire et de re-analysé pour obtenir uniquement l'entrée nécessaire de la source à chaque recherche? Bien sûr, cela sera incroyablement lent mais ce sera peut-être le seul moyen.
@R ..: Je ne pense pas. Dictionnaire est l'état de en / décodeur. Les bits dans le flux codé sont des index dans le dictionnaire.
La bibliothèque ZLIB que tout le monde utilise est gonflée entre autres problèmes (pour incorporé). Je suis à peu près sûr que cela ne fonctionnera pas pour votre cas. J'ai eu un peu plus de mémoire peut-être 16k et je ne pouvais pas l'obtenir pour s'adapter. Il alloue et zéros de gros morceaux de mémoire et conserve des copies de choses, etc. L'algorithme peut peut-être le faire, mais trouver du code existant est le défi.
Je suis allé avec http://lzfx.googlecode.com La boucle de décompression est minuscule, c'est la La compression de type LZ plus ancienne qui s'appuie sur les résultats précédents, vous devez donc avoir accès aux résultats non compressés ... L'octet suivant est un 0x5, l'octet suivant est un 0x23, les 15 prochains octets sont une copie du 15 200 octets il y a , les 6 prochains octets sont une copie de 127 ... Le nouvel algorithme LZ est une table variable de largeur basée sur la largeur variable qui peut être grande ou croissance en fonction de la mise en œuvre.
Je traitais de données répétitives et j'essayais de faire pression sur quelques k sur quelques centaines, je pense que la compression était d'environ 50%, pas bien mais que le travail et la routine de décompression ont été minuscules. Le paquet LZFX ci-dessus est petit, pas comme Zlib, comme deux fonctions principales qui ont le code juste là, pas des dizaines de fichiers. Vous pouvez probablement changer la profondeur du tampon, peut-être améliorer l'algorithme de compression si vous le souhaitez. Je devais modifier le code de décompression (comme 20 ou 30 lignes de code), il était peut-être un pointeur lourd et je l'ai changé à des tableaux car dans mon environnement embarqué, les pointeurs étaient au mauvais endroit. Burns peut-être un registre supplémentaire ou non en fonction de la manière dont vous l'implémentez et de votre compilateur. J'ai aussi fait cela afin que je puisse absréasser les extratures et les magasins des octets que je les avais emballé dans la mémoire qui n'était pas adressable à l'octet.
Si vous trouvez quelque chose de mieux, veuillez le poster ici ou Ping Me via Stackoverflow, je suis également très intéressé par d'autres solutions intégrées. J'ai cherché un peu un peu et ce qui précède était le seul utile que j'ai trouvé et j'ai eu la chance que mes données soient telles que cela comprimait assez bien à l'aide de cet algorithme ... pour l'instant.
Il y a un programme de compression appelé Puclunch CS.TUT.FI/~ALBERT/DEM/PUCRUNCH que peut-être que vous trouverez intéressant.
Eh bien, j'ai trouvé ce embedded.com/design/opensource/217800397 il dit "cette compression la technique est capable d'atteindre des ratios de compression respectables, généralement de l'ordre de 50 "60%, tout en consommant environ 2k de RAM" ... Je dois essayer ceci
Quelqu'un peut-il donner des pointeurs comment je peux implémenter la compression / la décompression LZW dans des conditions de mémoire faible (<2K). est-ce possible?
pourquoi lzw? LZW a besoin de beaucoup de mémoire. Il est basé sur un ratio hachage / dictionnaire et de compression est proportionnel à la taille du hachage / dictionnaire. Plus de mémoire - meilleure compression. Moins de mémoire - la sortie peut être encore plus grande que l'entrée.
Je n'ai pas touché de codage pour très long temps, mais IIRC Huffman Le codage est un peu meilleur en matière de consommation de mémoire.
Mais tout dépend du type d'informations que vous souhaitez compresser.
Si le choix de l'algorithme de compression n'est pas dans la pierre, vous pouvez essayer GZIP / LZ77 à la place. Voici une implémentation très simple que j'ai utilisée et adaptée une fois:
ftp://quatramaran.ens.fr/pub/madore/misc /myunzip.c
Vous devrez nettoyer la façon dont il lit l'entrée, la manipulation des erreurs, etc. Mais c'est un bon départ. C'est probablement aussi beaucoup trop gros si vos données et votre code doivent être adaptés à 2K, mais au moins la taille de données est déjà petite.
gros plus est que c'est le domaine public afin que vous puissiez l'utiliser, mais vous aimez!
J'ai utilisé LZSS . J'ai utilisé code de
typedef unsigned int UINT; typedef unsigned char BYTE; BYTE *lzw_encode(BYTE *input ,BYTE *output, long filesize, long &totalsize); BYTE *lzw_decode(BYTE *input ,BYTE *output, long filesize, long &totalsize);
-1 Comment cela devrait répondre à la question? Où est une description ou un lien pour la bibliothèque. Ou infos sur la taille ou quelque chose d'autre
Le dictionnaire le plus bas pour lzw est SO:
Veuillez noter que c'est une exigence de dictionnaire. Vous devez avoir environ 100-150 octets pour l'état ou les variables dans la pile.
Decompresseur utilisera moins de mémoire que le compresseur.
Donc, je pense que vous pouvez essayer de compresser vos données avec la version 9 bit compresse . Documentation détaillée ici .
N Dictionnaire de bit nécessite (2 ** n) * Tailleof (code) + (((2 ** n) - 257) * Taille de (code) + (2 ** n ) - 257 .
Quel est l'environnement?
Eh bien, j'ai besoin de mettre ce code dans un combiné mobile basse fin de bienvenue ....
J'ai mis à jour vos tags à ajouter
intégré afin que vous obtiendrez une exposition aux programmeurs qui travaillent avec des ressources contraintes comme <2K. En raison de l'exigence du dictionnaire, vous voudrez peut-être explorer d'autres algorithmes de compression (comme LZ77?)La contrainte est-elle l'utilisation de la mémoire transitoire ou la taille d'entrée / sortie?