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.