Version imprimable
Bonjour,
Je suis à la recherche d'un algorithme de compression de flux.
La fonctionnalité principale est qu'il doit savoir compresser et décompresser à la volée, je m'explique.
D'un côté, il y a un "ecrivain" qui envoie des données à un "lecteur". Le "lecteur" doit pouvoir commencer à lire/décompresser alors que "l'écrivain" n'a pas encore finit d'envoyer/compresser.
L'algorithme de compression Huffman ne va pas car il faut attendre la fin de la compression pour décompresser.
Quel est le contenu du flux ? Du texte ?
Tout algorithme de compression peut être utilisé, même Huffman, il suffit d'utiliser une table de codes prédéfinie. Elle est calculée une fois pour toute en fonction des spécificités des données. Si c'est du texte en anglais, par exemple, les codes seront calculés à partir de la probabilité d'occurrence de chaque lettre en anglais.
Une amélioration à cela est la compression adaptative : les paramètres de compression sont modifiés à mesure que les données sont émises. Les fréquences sont mises à jour, les codes changent petit à petit, la compression s'adapte aux données et devient plus efficace.
Une autre approche est tout simplement de compresser les données par blocs.
Oui, c'est du texte parfois en français parfois en anglaisCitation:
Envoyé par Sylvain Togni
OK pour la compression adaptative mais alors comment se fait la synchronisation des "dictionnaires" entre "l'écrivain" et le "lecteur"Citation:
Envoyé par Sylvain Togni
Pas adapté pour mon cas, car cela oblige à attendre que le bloc soit complet pour le transmettre ou alors à compléter le bloc en cours si je veux le transmettre immédiatement. Les messages que j'ai à transmettre n'ont pas tous la même taille.Citation:
Envoyé par Sylvain Togni
Bonjour,
tout dépend de la taille du bloc que tu choisis. S'il est relativement petit, ce sera totalement transparent pour le lecteur.Citation:
Envoyé par ram_0000
Sinon tu peux adapter : au lieu d'envoyer en fonction de la taille des blocs, tu le fais en fonction du temps (ex 100ms).
L'écrivain et le lecteur partent avec le même dictionnaire et le modifient avec le même algorithme à partir des données déjà envoyées/reçues.Citation:
Envoyé par ram_0000
Le dictionnaire n'est donc jamais transmit mais il est toujours identique du côté écrivan et du côté lecteur.
Cela me plait bien comme principe. Maintenant, je reviens à la question initiale, quels algorithmes utilisent ce principe ?Citation:
Envoyé par Sylvain Togni
Autre question, comme il s'agit d'un flux (théoriquement de longueur infinie), comment fait-on pour limiter la taille du dictionnaire des 2 côtés ?
Salut,
J'ai peu être très mal compris la question, mais...
Visibilement l'"écrivain" et le "lecteur" sont physiquement sur deux machines différentes.
Tu entre donc dans un contexte "client/serveur" classique, non :question:
Dés lors:
- Le dictionnaire est mis à jour sur le serveur (par l'"écrivain")
- La mise à jour est envoyée au client
- Seul le serveur est responsable du controle de la taille du dictionnaire
- C'est donc du coté serveur que tu te contente de refuser l'ajout d'une information si le dictionnaire devient trop grand ;)
- Tu peux sans problème décider d'une taille de block raisonnable pour l'envoi du dictionnaire (ou des mises à jours) au client, et le fait que le dernier bloc d'une taille (arbitraire) de 32k par exemple ne contienne que, par exemple, 2 k de données ne pose aucun problème :D
- "Au pire", tu peux envisager l'envoi d'un message "rien à transmettre" si la connexion est permanente ;)
J'aurais donc tendance à te rappeler que la solution la plus simple est toujours la moins compliquée... heu, je veux dire la meilleure :D
Maintenant, je n'ai peut être pas saisi l'intégralité du problème ;) :aie:
Oui, la connexion entre "l'écrivain" et le "lecteur" est un flux TCP. C'est justement ce flux que je veux compresser.Citation:
Visibilement l'"écrivain" et le "lecteur" sont physiquement sur deux machines différentes.
Tu entre donc dans un contexte "client/serveur" classique, non
1/ Les données échangées sont du texte pur (parfois en anglais, parfois en français, parfois dans d'autres langues).
2/ La longueur des messages échangés est essentiellement variables. Cela va de quelques octets à 2000 ou 3000 octets.
3/ La fréquence des messages est très variable (de plusieurs messages par seconde à 1 message toute les heures)
Donc je reviens à ma question, quels algorithmes peuvent être implémentés dans ce cadre là ?
* Performant en terme de compression
* Si possible simple
La methode standard est la compression LZW (Ecma-151).
C'est simple a implémenter (nombreux sources dispo sur le net) et c'est bien adapté pour la compression de texte. Les données peuvent etre envoyées à n'importe quel moment: inutile d'attendre qu'un bloc soit "complet" pour l'envoyer. On peut utiliser le code de controle "EOR" (end-of-record) pour signaler la fin d'un bloc "partiel".
Salut !
Pourquoi ne pas t'inspirer du système de compression inventé par Claude Chappe en 1794? Pour tous renseignements, je te recommande
http://chappe.ec-lyon.fr/
Ainsi tu auras au moins une solution originale!
Jean-Marc Blanc
Merci pour l'URL, je connaissait mais pas dans les détails.Citation:
Envoyé par FR119492
Toutefois, je n'ai pas vu de compression dans le télégraphe de Chappe. Tout au plus un dictionnaire minimaliste partagé entre l'émetteur et le destinataire. De plus, ce dictionnaire n'est pas dynamique.
Je pense que je vais partir effectivement sur cet algoCitation:
Envoyé par pseudocode