Discussion :

[Invit�]

Bonsoir,

J'ai un petit projet pour l'�cole, et celui-ci nous emm�ne sur le terrain du cryptage d'Huffman. N�anmoins je me frotte � un gros soucis pour la derni�re fonction � r�aliser. Celle-ci consiste � "d�coder" une string pour cr�er l'arbre binaire. Explications, on encode l'arbre et ses valeurs dans une string
( Encodes a huffman tree to its binary representation using a preOrder traversal:
* each leaf key is encoded into its binary representation on 8 bits preceded by '1'
* each time we go left we add a '0' to the result )
en utilisant un parcours pr�fixe de cet arbre. La fonction sur laquelle je butte doit prendre ce string et retourner l'arbre binaire correspondant.

Fonction telle qu'elle est fournie :

Code :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
3
4
5
6
7
 
def decodetree(dataIN):
    """
    Decodes a huffman tree from its binary representation:
        * a '0' means we add a new internal node and go to its left node
        * a '1' means the next 8 values are the encoded character of the current leaf       
    """

Pour l'utilisation des diff�rentes classes on est autoriser � utiliser BinTree ( qui contient self.key, self.right, self.left uniquement ) et heap ( qui contient self.push, self.pop, self.isEmpty ) /!\ UNIQUEMENT /!\ pas de nodes ou ce genre de chose.

Du coup si vous pouvez m'aider � appr�hender la chose ce ne serait pas de refus, j'ai du mal � visualiser comment cr�er un arbre � partir d'une telle string. Merci � tout ceux qui prendront le temps de m'aider ^^.

[wiztricks]

Salut,

Du coup si vous pouvez m'aider � appr�hender la chose ce ne serait pas de refus, j'ai du mal � visualiser comment cr�er un arbre � partir d'une telle string. Merci � tout ceux qui prendront le temps de m'aider ^^.

L'article de Wikipedia explique cela assez bien.... Et avec un peu de recherche sur Internet vous devriez trouver des explications plus d�taill�s et des codes.

- W

[Sve@r]

Bonjour

et celui-ci nous emm�ne sur le terrain du cryptage d'Huffman.

D�j�, on n'utilise jamais le terme "cryptage". Parce qu'en cryptographie, le "d�cryptage" consiste � d�chiffrer un message chiffr� sans avoir sa clef de d�chiffrement. Donc par opposition, le terme "cryptage" serait alors le chiffrement d'un message clair sans avoir la clef de chiffrement ; ce qui serait tout aussi idiot qu'inutile.
Le terme appropri� pour cr�er un message chiffr� est "chiffrement".

Et l'algorithme de Huffman n'est pas un algorithme de chiffrement mais de compression.

Donc d�j� quand tu feras l'effort minimum de t'int�resser assez � ton TP pour savoir de quoi il parle, nous on fera l'effort de t'aider � le r�aliser.