Discussion :

[Nehmé]

Bonjour à tous,

J'ai des chaînes binaires très longues(>100,000 bits) que j'ai besoin de compresser pour pouvoir les comparer rapidement(savoir si 2 chaines sont égales) et ne pas exploser ma mémoire.

Est ce qu'il y a des méthodes connues pour faire ceci ?

Merci !

[benDelphic]

heu toutes les méthodes de compression marchent : Huffman par exemple

[Champialex]

Pour une compression efficace, ca dépend beaucoup des caractéristiques de ta chaine (et aussi des contraintes que tu as)! Huffman sera bien s'il y a une grande disparité dans les motifs de ta chaine (ca consiste à coder le motifs le plus fréquent avec le mot code le plus court), LZW marchera bien aussi!
Si les tu sais que les séquences de 0 et de 1 sont longues, tu obtiendra un tres bon taux de compression simplement en comptant leurs tailles!
Voila, précise un peu ta demande et ton besoin!
Je te donne quand même un petit lien très bien fait sur la théorie de l'information, tout est très bien expliqué : http://www-public.int-evry.fr/~uro/
Voila si tu veux aller direct à Huffman, va dans cours simplifié, puis clique sur source discrète puis...
Voili voilou!
Beaucoup d'infos la dessus sont dispos sur le net!

[Nehmé]

Merci pour les détails !
Compter les bits consécutifs me semble une très bonne idée.
Je travaille sur un algorithme Tabu dans lequel je sauve une liste de solution déjà visitées (chaque élément de la liste représente une chaine binaire).
Chaque fois que je génère une nouvelle solution, je dois savoir rapidement si cette solution a dejà été visitée.

Il y'a donc 2 facteurs:
- mémoire: la liste Tabu ne peux pas contenir les chaines binaires eux même mais une compression de ces chaines.
- temps d'execution: je dois être capable de savoir rapidement si une solution générées est contenu dans la liste.

Si je compte les bits consécutifs, le taux de compression sera bon et la comparaison sera rapide car après avoir compressé une nouvelle solution, je ne dois la comparer qu'avec les éléments de la liste ayant la même taille.

Je n'ai pas encore regarder les autres méthodes de compression, mais je vais le faire pour voir s'il y'a meilleure.

Merci !

[Nehmé]

Merci pour les détails !
Compter les bits consécutifs me semble une très bonne idée.
Je travaille sur un algorithme Tabu dans lequel je sauve une liste de solution déjà visitées (chaque élément de la liste représente une chaine binaire).
Chaque fois que je génère une nouvelle solution, je dois savoir rapidement si cette solution a dejà été visitée.

Il y'a donc 2 facteurs:
- mémoire: la liste Tabu ne peux pas contenir les chaines binaires eux même mais une compression de ces chaines.
- temps d'execution: je dois être capable de savoir rapidement si une solution générées est contenu dans la liste.

Si je compte les bits consécutifs, le taux de compression sera bon et la comparaison sera rapide car après avoir compressé une nouvelle solution, je ne dois la comparer qu'avec les éléments de la liste ayant la même taille.

Je n'ai pas encore regarder les autres méthodes de compression, mais je vais le faire pour voir s'il sont meilleures que compter les bits consécutifs.

Merci !

[Champialex]

Fais gaffe, il faut vraiment que tu soit sur qu'il y ai en moyennes de longues suites de 0 ou de 1 pour que ca marche bien! Sinon ca fera l'inverse...
Ex : la chaine 1010100, si tu choisis de prendre de compter max trois caracteres ca te donnera 01 1 01 0 01 1 01 0 01 1 10 0, tu peux aussi choisir qu'il y a tjrs une alternance 0/1, dans ce cas il faut que tu code sur 3 bits (ta chaine mesure 7) et ca donne : 000 001 001 001 001 001 001 010.
Dans les deux cas, ca grossis beaucoup la chaine!
Jette un coup d'œil au codage arithmétique, il me semble très bien adapté à ton problème (il permet de stocker ta chaine en un seul nombre réel). Par contre il faut faire gaffe à la précision de l'ordinateur, donc il te faudra peut être stocker ton nombre dans plusieurs doubles.

[Nebulix]

- 100kbits c'est 12 koctets ou 3000 mots de 32 bits, et la comparaison est une opération rapide. Est-ce la peine de se compliquer la vie ?
- Ces chaines peuvent-elles être compressées ? S'il n'y a pas de bonnes raisons pour celà dans leur nature même (que nous ne connaissons pas), si elles ne présentent pas une certaine redondance intrinsèque, ce n'est pas évident.

[Obsidian]

Bonjour,

J'ai des chaînes binaires très longues(>100,000 bits) que j'ai besoin de compresser pour pouvoir les comparer rapidement(savoir si 2 chaines sont égales) et ne pas exploser ma mémoire. Est ce qu'il y a des méthodes connues pour faire ceci ?

Non seulement 100.000 bits, ce n'est pas grand chose pour une machine moderne, comme on l'a dit au dessus, mais surtout : pour comprimer tes chaînes, il va falloir les lire en entier ! Donc, autant faire directement la comparaison.

Cela n'a de sens que si tu as énormément de chaînes à comparer et que tu veux toutes les confronter une à une, c'est-à-dire faire un produit cartésien. Par exemple, 100.000 chaînes à comparer entre elles ferait 10 milliards de comparaisons et ça commencerait effectivement à être très long.

Là, c'est plus un hash à la MD5 qu'il te faudrait, plutôt qu'une véritable compression. Et même dans ce cas, cela n'est intéressant que si les chaînes à comparer sont globalement identiques dans leur premiers caractères. Sinon, quelque soit la longueur de la chaîne, comparer « A… » et « B… » échouera invariablement dès le premier caractère, et cela restera de loin la méthode la plus efficace.

[Nehmé]

Merci pour vos réponses ! et je m'excuse pour le retard ! (vacances)

Effectivement compter les bits consécutifs n'est pas la solution car je n'ai pas toujours des longues suites.

Mon algorithme génère à chaque itérations entre 100 et 1000 chaînes et chacune de ces chaînes doit être comparée à tous les chaînes contenu dans la liste Tabu dont la taille est environ 25% à 50% du nombre de chaînes générées à chaque itérations.

Après un certain nombre d'itérations, les solutions générées deviennent très semblables et la comparaison prend trop de temps. C'est pourquoi il me semble que la compression est nécessaire.

[Nebulix]

Après un certain nombre d'itérations, les solutions générées deviennent très semblables et la comparaison prend trop de temps. C'est pourquoi il me semble que la compression est nécessaire.

Il faut donc exploiter cette similitude pour optimiser la comparaison (et éventuellement la compression)

[Obsidian]

Après un certain nombre d'itérations, les solutions générées deviennent très semblables et la comparaison prend trop de temps. C'est pourquoi il me semble que la compression est nécessaire.

C'est-à-dire qu'une vraie compression est très chronophage : il n'y a qu'à se pencher sur le temps que prend la compression d'un fichier. Cela peut aller jusqu'à plusieurs secondes pour un fichier de taille moyenne. Si tu as beaucoup de chaînes à traiter, le temps que tu peux espérer gagner risque d'être largement contrebalancé par la durée de la compression. C'est normal car l'objectif est de minimiser l'espace en mémoire, pas la durée des traitements.

Ce qu'il te faut, c'est plutôt une fonction de hachage rapide, par exemple MD5, mais surtout, il te faut trier ta liste de référence si tu ne l'as pas déjà fait, et t'arranger pour qu'elle le reste (en classant directement toute nouvelle chaîne à sa place). Si, actuellement, tu te contentes de repasser en revue toutes les chaînes de ta liste à chaque nouvelle chaîne produite, ce n'est même pas la peine de songer à faire de l'optimisation ailleurs…

[Nehmé]

C'est-à-dire qu'une vraie compression est très chronophage : il n'y a qu'à se pencher sur le temps que prend la compression d'un fichier. Cela peut aller jusqu'à plusieurs secondes pour un fichier de taille moyenne. Si tu as beaucoup de chaînes à traiter, le temps que tu peux espérer gagner risque d'être largement contrebalancé par la durée de la compression. C'est normal car l'objectif est de minimiser l'espace en mémoire, pas la durée des traitements.

Ce qu'il te faut, c'est plutôt une fonction de hachage rapide, par exemple MD5, mais surtout, il te faut trier ta liste de référence si tu ne l'as pas déjà fait, et t'arranger pour qu'elle le reste (en classant directement toute nouvelle chaîne à sa place). Si, actuellement, tu te contentes de repasser en revue toutes les chaînes de ta liste à chaque nouvelle chaîne produite, ce n'est même pas la peine de songer à faire de l'optimisation ailleurs…

Le truc c'est que l'algorithme Tabu requiert l'utilisation d'une queue et non une liste (Les chaines doivent rester dans l'ordre d'insertion en sorte que quand la queue est pleine, chaque fois qu'on insère une nouvelle chaine, on supprime la plus vieille et donc celle à la fin de la queue).