Prefacio
Creo que los amigos que han aprendido las estructuras de datos deben conocer a Huffman. Este gran dios inventó el famoso "Árbol binario óptimo". Para conmemorarlo, lo llamamos el "árbol de Huffman". El árbol Huffman se puede usar para la codificación de Huffman, y el conocimiento de la codificación es muy grande, como para compresión, criptografía, etc. Echemos un vistazo a lo que es el árbol de Huffman hoy.
concepto
Por supuesto, una de las rutinas es que necesitamos comprender algunos conceptos básicos.
1. Longitud de la ruta: la ruta que forma los dos nodos de un nodo en el árbol a otro nodo. El número de ramas en la ruta se llama longitud de la ruta.
2. Longitud del camino del árbol: la suma de las longitudes de la ruta desde la raíz del árbol hasta cada nodo. Lo que llamamos un árbol binario completo es la longitud de camino más corta de este tipo.
3. La longitud del camino ponderado del árbol: si se asigna un valor ponderado a cada nodo de hoja del árbol, la longitud de la ruta ponderada del árbol es igual a la suma del producto de la longitud del camino desde el nodo de la raíz hasta todos los nodos de la hoja y el peso del nodo de la hoja.
Entonces, ¿cómo determinamos si un árbol es un árbol binario óptimo? Echemos un vistazo a los siguientes árboles:
Sus longitudes de potencia son:
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
Es obvio que el tercer árbol tiene el camino de peso más corto (no lo crees, puedes probarlo. Si puedes encontrar uno más corto, probablemente ganes el premio Turing). Esto es lo que llamamos el "Árbol binario óptimo (árbol Hafman)". Su método de construcción es muy simple. Selecciona el nodo con el peso más pequeño y lo coloca en la parte inferior del árbol, y coloca las dos conexiones más pequeñas en un nuevo nodo. Cabe señalar que el peso del nuevo nodo formado debe ser igual a la suma de los pesos de estos dos nodos. Luego vuelva a colocar este nuevo nodo en el nodo donde necesitamos formar el árbol para continuar clasificando. De esta manera, todos los nodos con información almacenada en el árbol Hafman están en los nodos de la hoja.
Después de terminar el concepto, puedo estar un poco "poco claro".
Demos un ejemplo para construirlo claramente.
Hay una cadena: aaaaaaaabbbaaaaaccccccccdddddfff
En el primer paso, primero contamos el número de veces que aparece cada personaje y lo llamamos el peso del personaje. A 15, B 5, C 8, D 6, F 3.
El segundo paso es encontrar los dos caracteres con el peso más pequeño, B5 y F3, y construir el nodo.
Luego retire F3 y B5, ahora A15, C8, D6, FB8.
Paso 3, repita el segundo paso hasta que solo quede un nodo.
Ahora es DFB14, A15, C8.
por fin,
Ok, entonces nuestro árbol de Huffman está construido.
Pasos para construir
Según la lógica anterior, para resumirla, hay algunos pasos:
1. Estadísticas El número de caracteres y caracteres que aparecen en una cadena;
2. Crear nodos de acuerdo con la estructura del primer paso;
3. Ordene el orden de los pesos del nodo;
4. Saque los dos nodos con el peso más pequeño y genere un nuevo nodo principal;
5. Elimine los dos nodos con el peso más pequeño y almacene el nodo principal en la lista;
6. Repita el paso 4 o 5 hasta que quede un nodo;
7. Asigne el último nodo al nodo raíz.
Código Java
El principio está terminado y el siguiente paso es implementar el código.
Primero, hay una clase de nodo para almacenar datos.
paquete huffman;/** * clase de nodo * @author yuxiu * */public class node {public String Code; // Hafman Codificación de Node public int codesize; // Longitud del nodo Huffman que codifica datos de cadena pública; // Node Data Public int Count; // Node Public Node Node Node Lchild; Nodo público RCHILD; public nodo () {} public nodo (string data, int count) {this.data = data; this.count = Count; } nodo público (int count, nodo lchild, nodo rchild) {this.count = count; this.lchild = lchild; this.rchild = rchild; } nodo público (string data, int count, nodo lchild, nodo rchild) {this.data = data; this.count = Count; this.lchild = lchild; this.rchild = rchild; }}Luego está el proceso de implementación.
paquete huffman; import java.io.*; import java.util.*; public class Huffman {private String str; // usado originalmente para compresión privada string newstr = ""; // La cadena conectada por Huffman que codifica el nodo privado Root; // el nodo raíz de la bandera boolean de huffman binary binary boolean; Almacenamiento de diferentes caracteres es el mismo personaje en la misma posición ArrayList private <node> nodelist; // La cola para almacenar nodos 15 16/ ** * Construya el árbol de Huffman * * @param str */ public void Creathfmtree (String Str) {this.str = str = str; charlist = new ArrayList <String> (); Nodelist = new ArrayList <Node> (); // 1. Estadísticas El número de caracteres y caracteres que aparecen en una cadena // La idea básica es colocar una cadena desordenada como ababccdebed en la charlist, que es aa, bbb, cc, dd, ee // y la longitud de la cadena en la lista es el peso correspondiente para (int i = 0; i <str.lengther // Saque el indicador de caracteres = true; for (int j = 0; j <charlist.size (); j ++) {if (charlist.get (j) .charat (0) == ch) {// Si se encuentra el mismo carácter S = CharList.get (j)+ch; Charlist.set (J, S); bandera = falso; romper; }} if (flag) {charlist.add (charlist.size (), ch + ""); }} // 2. Cree un nodo de acuerdo con la estructura del primer paso para (int i = 0; i <charlist.size (); i ++) {string data = charlist.get (i) .charat (0)+""; // Obtenga el primer carácter de cada cadena en Charlist int count = charlist.get (i) .length (); // La longitud de la cadena en la lista es el nodo de peso de peso correspondiente = nuevo nodo (datos, recuento); // Crear objeto de nodo Nodelist.Add (i, nodo); // Únete a la cola de nodo} // 3. Sort (nodelist); while (nodelist.size ()> 1) {// cuando el número de nodos es mayor que uno // 4. Saque los dos nodos con el peso más pequeño y genere un nuevo nodo principal // 5. Elimine los dos nodos con el peso más pequeño y almacene el nodo principal en el nodo de lista izquierda = nodelist.remove (0); Nodo derecho = nodelist.remove (0); int parentweight = left.count + right.count; // El peso del nodo principal es igual a la suma de los pesos del nodo del nodo infantil parent = nuevo nodo (peso parado, izquierda, derecha); Nodelist.add (0, padre); // Coloque el nodo principal en la primera posición} // 6. Repita los pasos cuarto y quinto para ser el bucle while // 7. Asigne el último nodo a la raíz raíz raíz = nodelist.get (0); } / ** * orden ascendente * * @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 nodo * nodo * / public void output (nodo nodo) {if (node.lchild! = Null) {output (node.lchild); } System.out.print (node.count + ""); // Traversal en orden if (node.rchild! = Null) {output (node.rchild); }} public void output () {output (root); }/** * Método principal * * @param args */public static void main (string [] args) {huffman huff = new Huffman (); // Cree el objeto Havalman Huff.Creathfmtree ("SDFassVVVVDFGSFDFSDFS"); // construye el árbol}Resumir
Lo anterior se trata de implementar el árbol Huffman basado en Java. Espero que este artículo sea útil para que todos aprendan a usar Java. Si tiene alguna pregunta, deje un mensaje para discutir.