Dossier N-445
Secret
Difficile
Codage Huffman V
Cette énigme a été créée par jaudi
Dossier non résolu — en attente de déchiffrement
Ce forum est un forum d'aide et de discussion, il est cependant interdit de donner la solution de l'énigme !
jaudi
2026-07-25 21:04:45
Je me suis appuyé sur le pseudo-code d'un document scientifique mais il me semble en effet qu'il y a un bug quelque part, car je suis d'accord avec le problème signalé par @Jericho. Si je "publie l'algorithme de codage", je trouve cela dommage car l'énigme perdrait toute sa difficulté ! :-)
Je suis vraiment désolé pour cette potentielle erreur et je vais essayer de regarder tout cela !
Je suis vraiment désolé pour cette potentielle erreur et je vais essayer de regarder tout cela !
mvc Expert
2026-07-25 20:20:43
Bonsoir,
J'ai également des problèmes de compréhension de la méthode : quand les arbres sont rééquilibrés? (poids et fréquences), et comment. Je suis surpris que 00 corresponde au code de B, je pensais que les 0 correspondait tout le temps a NYT. En fait cet algorithme est très délicat et la moindre erreur casse tout. Le plus simple serait de publier l'algorithme de codage utilisé pour lever les doutes.
J'ai également des problèmes de compréhension de la méthode : quand les arbres sont rééquilibrés? (poids et fréquences), et comment. Je suis surpris que 00 corresponde au code de B, je pensais que les 0 correspondait tout le temps a NYT. En fait cet algorithme est très délicat et la moindre erreur casse tout. Le plus simple serait de publier l'algorithme de codage utilisé pour lever les doutes.
Jericho Maître
2026-07-25 18:39:29
Je crois que j'ai une indigestion de Huffman ! :-[]
Mais plus sérieusement : je pense que la note (et donc peut-être ton script) comporte une erreur au moment du troisième "B".
@jaudi
C'est lors de la lecture du 3e B (6e caractère) que la note commet une erreur d'algorithme :
• Ce que tu dis dans la note : on émet le code 00, on passe la fréquence de B à 3, puis on continue directement aux lettres suivantes sans modifier l'arbre.
• Ce qu'exige l'algorithme : avant l'incrémentation, B a un poids de 2 (au code 00). La branche EMB2 (au code 1) a également un poids de 2. En passant à une fréquence de 3, B devient plus lourd que la branche EMB2 (poids 3 > poids 2). La propriété d'ordre de l'arbre est violée.
• La correction : B et la branche EMB2 doivent permuter.
◦ La feuille B monte au code 1 (son poids passe à 3).
◦ La branche EMB2 descend au code 00 (son poids reste à 2).
◦ Par conséquent, les codes de A et C changent de préfixe : A devient 000 et C devient 001.
Je peux me tromper... mais avec le crypto tel quel je n'arrive à rien.
On peut en parler ailleurs si tu veux...
Mais plus sérieusement : je pense que la note (et donc peut-être ton script) comporte une erreur au moment du troisième "B".
@jaudi
C'est lors de la lecture du 3e B (6e caractère) que la note commet une erreur d'algorithme :
• Ce que tu dis dans la note : on émet le code 00, on passe la fréquence de B à 3, puis on continue directement aux lettres suivantes sans modifier l'arbre.
• Ce qu'exige l'algorithme : avant l'incrémentation, B a un poids de 2 (au code 00). La branche EMB2 (au code 1) a également un poids de 2. En passant à une fréquence de 3, B devient plus lourd que la branche EMB2 (poids 3 > poids 2). La propriété d'ordre de l'arbre est violée.
• La correction : B et la branche EMB2 doivent permuter.
◦ La feuille B monte au code 1 (son poids passe à 3).
◦ La branche EMB2 descend au code 00 (son poids reste à 2).
◦ Par conséquent, les codes de A et C changent de préfixe : A devient 000 et C devient 001.
Je peux me tromper... mais avec le crypto tel quel je n'arrive à rien.
On peut en parler ailleurs si tu veux...