Préface
Je pense que les amis qui ont appris les structures de données doivent connaître Huffman. Ce grand dieu a inventé le célèbre "arbre binaire optimal". Afin de le commémorer, nous l'appelons le "Huffman Tree". L'arbre Huffman peut être utilisé pour le codage de Huffman, et la connaissance de l'encodage est très grande, comme pour la compression, la cryptographie, etc. Jetons un œil à ce qu'est l'arbre Huffman aujourd'hui.
concept
Bien sûr, l'une des routines est que nous devons comprendre certains concepts de base.
1. Longueur du chemin: le chemin qui forme les deux nœuds d'un nœud de l'arborescence à un autre nœud. Le nombre de branches sur le chemin est appelé la longueur du chemin.
2. Longueur du chemin de l'arbre: la somme des longueurs de chemin de la racine de l'arbre à chaque nœud. Ce que nous appelons un arbre binaire complet, c'est la longueur de chemin la plus courte de ce type.
3. La longueur du chemin pondéré de l'arbre: Si une valeur pondérée est attribuée à chaque nœud feuille de l'arbre, la longueur de chemin pondérée de l'arbre est égale à la somme du produit de la longueur du chemin du nœud racine à tous les nœuds de feuille et le poids du nœud feuille.
Alors, comment déterminer si un arbre est un arbre binaire optimal? Jetons un coup d'œil aux arbres suivants:
Leurs longueurs de puissance sont:
WPL1: 7 * 2 + 5 * 2 + 2 * 2 + 4 * 2 = 36
Wpl2: 7 * 3 + 5 * 3 + 2 * 1 + 4 * 2 = 46
WPL3: 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3 = 35
Il est évident que le troisième arbre a le chemin de poids le plus court (vous ne le croyez pas, vous pouvez l'essayer. Si vous pouvez en trouver un plus court, vous gagnerez probablement le prix Turing). C'est ce que nous appelons "l'arbre binaire optimal (arbre Hafman)". Sa méthode de construction est très simple. Vous sélectionnez le nœud avec le plus petit poids et le placez au bas de l'arbre, et placez les deux plus petites connexions dans un nouveau nœud. Il convient de noter que le poids du nouveau nœud formé doit être égal à la somme des poids de ces deux nœuds. Ensuite, remettez ce nouveau nœud dans le nœud où nous devons former l'arbre pour continuer le tri. De cette façon, tous les nœuds avec des informations stockés dans l'arbre Hafman sont sur les nœuds de feuille.
Après avoir terminé le concept, je suis peut-être un peu "peu clair".
Donnons un exemple pour le construire clairement.
Il y a une chaîne: aaaaaaaabbbbaaaaCccccccdddddfff
Dans la première étape, nous comptons d'abord le nombre de fois que chaque personnage apparaît et l'appelons le poids du personnage. a 15, b 5, c 8, d 6, f 3.
La deuxième étape consiste à trouver les deux caractères avec le plus petit poids, B5 et F3, et à construire le nœud.
Retirez ensuite F3 et B5, maintenant A15, C8, D6, FB8.
Étape 3, répétez la deuxième étape jusqu'à ce qu'un seul nœud soit laissé.
C'est maintenant DFB14, A15, C8.
enfin,
Ok, donc notre arbre Huffman est construit.
Étapes pour construire
Selon la logique ci-dessus, pour le résumer, il y a quelques étapes:
1. Statistiques Le nombre de caractères et de caractères apparaissant dans une chaîne;
2. Créez des nœuds en fonction de la structure de la première étape;
3. Trier les poids de nœud Ascending Order;
4. Sortez les deux nœuds avec le plus petit poids et générez un nouveau nœud parent;
5. Supprimer les deux nœuds avec le plus petit poids et stocker le nœud parent dans la liste;
6. Répétez l'étape 4 ou 5 jusqu'à ce qu'il reste un nœud;
7. Attribuez le dernier nœud au nœud racine.
Code java
Le principe est terminé et l'étape suivante consiste à implémenter le code.
Tout d'abord, il existe une classe de nœud pour stocker les données.
Package Huffman; / ** * Classe de nœuds * @author yuxiu * * / classe publique Node {Code de chaîne publique; // Hafman Encodage du nœud public int codesize; // longueur du nœud Huffman Encoding Public String Data; // NODE DATA PUBLIC INT COUNT Node public Rchild; Node public () {} public Node (String Data, int count) {this.data = data; this.count = count; } Node public (int count, nœud lchild, nœud rchild) {this.count = count; this.lchild = lchild; this.rchild = rchild; } Node public (String Data, int count, nœud lChild, nœud rchild) {this.data = data; this.count = count; this.lchild = lchild; this.rchild = rchild; }}Ensuite, il y a le processus de mise en œuvre.
Package Huffman; Importer Java.io. *; Importer java.util. *; public class Huffman {private String str; // Utilisé à l'origine pour compression newtrt private New Le même caractère dans la même position Private ArrayList <NODE> NODELIST; // La file d'attente pour stocker les nœuds 15 16 / ** * Créez l'arborescence Huffman * * @param str * / public void creathfmtree (String str) {this.str = str; charlist = new ArrayList <string> (); NodeList = new ArrayList <Node> (); // 1. Statistiques Le nombre de caractères et de caractères apparaissant dans une chaîne // L'idée de base est de mettre une chaîne non ordonnée telle qu'AbabccDebed dans la Charlist, qui est aa, bbb, cc, dd, ee // et la longueur de la chaîne dans la liste est le poids correspondant pour (int i = 0; i <str.Length (); i ++) {char ch = str.harat (i); // retirer le drapeau du caractère = true; pour (int j = 0; j <charlist.size (); j ++) {if (charlist.get (j) .charat (0) == ch) {// si le même caractère est trouvé String s = charlist.get (j) + ch; charlist.set (j, s); Flag = false; casser; }} if (Flag) {charlist.add (charlist.size (), ch + ""); }} // 2. Créez un nœud en fonction de la structure de la première étape pour (int i = 0; i <charlist.size (); i ++) {String data = charlist.get (i) .charat (0) + ""; // Obtenez le premier caractère de chaque chaîne dans Charlist int count = charlist.get (i) .length (); // La longueur de la chaîne dans la liste est le nœud de poids de poids correspondant Node = nouveau nœud (data, count); // Créer un objet nœud nodelist.add (i, nœud); // rejoindre la file d'attente de nœud} // 3. Sort (nodeList); tandis que (nodelist.size ()> 1) {// lorsque le nombre de nœuds est supérieur à un // 4. Sortez les deux nœuds avec le plus petit poids et générez un nouveau nœud parent // 5. Supprimer les deux nœuds avec le plus petit poids et stocker le nœud parent dans le nœud de liste gauche = NodeList.Remeve (0); Node droit = nodelist.reMove (0); int Parentweight = Left.Count + droite.Count; // Le poids du nœud parent est égal à la somme des poids du nœud de nœud enfant Parent = nouveau nœud (poids parent, gauche, droite); Nodelist.add (0, parent); // Mettez le nœud parent à la première position} // 6. Répétez les quatrième et cinquième étapes pour être la boucle While // 7. Attribuez le dernier nœud au nœud racine root = nodelist.get (0); } / ** * Ordre ascendant * * @param nodelist * / public void Sort (ArrayList <Node> NodeList) {for (int i = 0; i <nodelist.size () - 1; i ++) {for (int j = i + 1; j <nodelist.size (); j ++) {node temp; if (nodelist.get (i) .Count> nodelist.get (j) .Count) {temp = nodelist.get (i); Nodelist.set (i, nodelist.get (j)); Nodelist.set (J, Temp); }}}} / ** * Traversal * * @param node * node * / public void output (node node) {if (node.lchild! = Null) {output (node.lchild); } System.out.print (Node.Count + ""); // Transfert dans l'ordre if (node.rchild! = Null) {output (node.rchild); }} public void Output () {output (root); } / ** * Méthode principale * * @param args * / public static void main (String [] args) {Huffman Huff = new Huffman (); // Créer l'objet Havalman Huff.Creathfmtree ("Sdfassvvvdfgsfdfsdfs"); // construire l'arborescence}Résumer
Ce qui précède consiste à mettre en œuvre l'arbre Huffman basé sur Java. J'espère que cet article sera utile à tout le monde pour apprendre à utiliser Java. Si vous avez des questions, veuillez laisser un message à discuter.