Discussion :

[ram-0000]

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.

[Sylvain Togni]

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.

[ram-0000]

Quel est le contenu du flux ? Du texte ?

Oui, c'est du texte parfois en français parfois 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.

OK pour la compression adaptative mais alors comment se fait la synchronisation des "dictionnaires" entre "l'écrivain" et le "lecteur"

Une autre approche est tout simplement de compresser les données par blocs.

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.

[ToTo13]

Bonjour,

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.

tout dépend de la taille du bloc que tu choisis. S'il est relativement petit, ce sera totalement transparent pour le lecteur.
Sinon tu peux adapter : au lieu d'envoyer en fonction de la taille des blocs, tu le fais en fonction du temps (ex 100ms).

[Sylvain Togni]

OK pour la compression adaptative mais alors comment se fait la synchronisation des "dictionnaires" entre "l'écrivain" et le "lecteur"

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.

Le dictionnaire n'est donc jamais transmit mais il est toujours identique du côté écrivan et du côté lecteur.

[ram-0000]

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.

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 ?

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 ?

[koala01]

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

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
• "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

Maintenant, je n'ai peut être pas saisi l'intégralité du problème