Introducción de codificación de Huffman
La codificación de Huffman se ocupa del problema de emparejamiento de codificación de caracteres y binarios correspondientes a los caracteres, que se divide en codificación y decodificación, con el propósito de comprimir la longitud de los datos binarios correspondientes a los caracteres. Sabemos que cuando los personajes se almacenan y transfieren, son binarios (la computadora solo sabe 0/1), por lo que hay una relación de mapeo entre los personajes y el binario. Los caracteres pertenecen al conjunto de caracteres (charset). Los caracteres deben ser almacenados y transmitidos en binario a través de la codificación. Cuando se muestran, deben ser decodificados de regreso a los personajes. El conjunto de caracteres y los métodos de codificación son relaciones de uno a muchos (Unicode se puede codificar con UTF-8, UTF-16, etc.). Después de comprender el conjunto de caracteres, codificar y decodificar, el problema del código confuso que vuela por todo el cielo se puede resolver fácilmente. Tomando la minúscula A de la letra inglesa como ejemplo, en la codificación ASCII, el decimal es 97 y el binario es 01100001. Cada personaje en ASCII está codificado con 8 bits (1 byte). Si se transmiten 1000 caracteres, entonces se deben transmitir 8000 bits. El problema es que la frecuencia del uso de la letra E en inglés es del 12.702%, mientras que Z es 0.074%. El primero es más de 100 veces mayor que el segundo, pero usa binario con los mismos dígitos. Se puede hacer mejor, el método es la codificación de longitud variable. El principio rector es codificar la frecuencia más alta con dígitos más cortos y aquellos con baja frecuencia con dígitos más largos. El algoritmo de codificación de Huffman trata de tales problemas.
Huffman codifica la implementación de Java
Las estructuras de datos utilizadas principalmente por el algoritmo de codificación de Huffman son árboles binarios completos y colas prioritarias. Este último usa java.util.priorityqueue, y los primeros se implementan (todos son clases internas). El código es el siguiente:
Árbol de clase estática {raíz de nodo privado; public nodo getRoot () {return root; } public void setroot (raíz de nodo) {this.root = root; }} El nodo de clase estática implementa comparable <node> {private string chars = ""; INT de la frecuencia privada = 0; padre de nodo privado; Nodo privado LeftNode; Nodo privado Nodo Right Node; @Override public int Compareto (nodo n) {frecuencia de retorno - n.frequency; } public boolean isleaf () {return Chars.length () == 1; } public boolean isroot () {return parent == null; } public boolean isleftchild () {return parent! = null && this == parent.leftnode; } public int getFrequence () {Frecuencia de retorno; } public void setFrequence (int frecuencia) {this.frequency = frecuencia; } public String getChars () {return Chars; } public void setchars (cadena de cadena) {this.chars = chars; } public nodo getParent () {return parent; } public void setParent (nodo parent) {this.parent = parent; } public nodo getLeftNode () {return LeftNode; } public void setleftnode (nodo leftNode) {this.leftnode = leftNode; } public nodo getRightNode () {return RightNode; } public void setRightNode (nodo RightNode) {this.rightNode = rightNode; }} Estadística
Dado que la tabla de codificación debe organizarse de acuerdo con la frecuencia, entonces, por supuesto, debe obtener la información estadística de la frecuencia. Implementé un método para lidiar con tal problema. Si ya hay estadísticas, entonces conviértase en MAP <caracteres, entero>. Si la información que obtiene es un porcentaje, multiplique por 100 o 1000, o 10000. Siempre se puede convertir a un entero. Por ejemplo, 12.702% multiplicado por 1000 es 12702, y Huffman que codifica solo se preocupa por los problemas de tamaño. El método estadístico se implementa de la siguiente manera:
Public Static Map <caracteres, entero> estadísticas (char [] chararray) {map <caracteres, integer> map = new Hashmap <caracteres, integer> (); para (Charc C: CharArray) {caracteres caracteres = nuevo carácter (c); if (map.containskey (caracteres)) {map.put (caracteres, map.get (caracteres) + 1); } else {map.put (carácter, 1); }} mapa de retorno; } Construyendo un árbol
Construir un árbol es un paso central en el algoritmo de codificación de Huffman. La idea es colgar todos los caracteres en un nodo de hoja de un árbol completamente binario, y la frecuencia del nodo izquierdo de cualquier nodo infantil que no sea de página no aparece más que el nodo derecho. El algoritmo convierte estadísticas en nodos y los almacena en una cola prioritaria. Cada vez que aparecen dos nodos con la frecuencia mínima de la cola, se construye un nuevo nodo principal (nodo no hojado). La suma de los dos nodos cuyo contenido de personajes simplemente aparece, y la frecuencia también es su suma. La primera ventana emergente se usa como nodo infantil izquierdo, y la siguiente se usa como el nodo infantil correcto, y el nodo principal recién construido se coloca en la cola. Repita las acciones anteriores n-1 veces, n es el número de caracteres diferentes (el número en la cola se reduce en 1 cada vez). Termine los pasos anteriores, queda un nodo en la cola, y aparece el nodo raíz del árbol. El código es el siguiente:
Builttree de árbol estático privado (map <caracteres, entero> estadísticas, list <node> hojas) {carácter [] keys = statistics.keyset (). toArray (nuevo carácter [0]); Priorityqueue <node> priorityqueue = new priorityqueue <node> (); for (personaje de caracteres: teclas) {nodo nodo = new node (); node.chars = caracteres.ToString (); node.frequency = statistics.get (carácter); priorityqueue.add (nodo); hojas.add (nodo); } int size = priorityqueue.size (); for (int i = 1; i <= size - 1; i ++) {nodo nodo1 = priorityqueue.poll (); Nodo nodo2 = priorityqueue.poll (); Nodo sumnode = new Node (); sumnode.chars = node1.chars + node2.chars; sumnode.frequency = node1.fraquence + node2.fraquence; sumnode.leftnode = node1; sumnode.rightNode = node2; nodo1.parent = sumnode; nodo2.parent = sumnode; priorityqueue.add (sumnode); } Árbol de árbol = nuevo árbol (); árbol.root = priorityqueue.poll (); Árbol de regreso; } codificación
La codificación correspondiente de un personaje es buscar desde el nodo de hoja donde se encuentra el personaje. Si el nodo de caracteres es el nodo izquierdo del nodo principal, agregue 0 antes del carácter codificado, de lo contrario, si es el nodo derecho, agregue 1 hasta el nodo raíz. Mientras se obtenga la relación de mapeo entre los caracteres y el código binario, la codificación es muy simple. El código es el siguiente:
public static String code (String OriginalStr, MAP <caracteres, Integer> Statistics) {if (OriginalStr == NULL || OriginalStr.Equals ("")) {return ""; } char [] CharArray = OriginalStr.ToCarArray (); List <node> feafNodes = new ArrayList <Node> (); BuildTree (estadísticas, Nodos de hoja); Map <carácter, string> encodinfo = buildEncodingInfo (foardnodes); StringBuffer Buffer = new StringBuffer (); para (char c: chararray) {caracteres caracteres = nuevo carácter (c); buffer.append (encodinfo.get (personaje)); } return buffer.ToString (); } mapa estático privado <caracteres, string> buildEncodingInfo (list <node> feafNodes) {map <caracteres, string> codewords = new HashMap <caracteres, string> (); para (Node LeakNodes: LeakNodes) {carácter carácter = nuevo carácter (feafNode.getChars (). charat (0)); Cadena codeword = ""; Nodo CurrentNode = LeafNode; do {if (currentNode.IsleftChild ()) {Codeword = "0" + CodeWord; } else {codeword = "1" + codeword; } currentNode = currentNode.Parent; } while (currentNode.Parent! = NULL); codews.put (carácter, codeword); } return Codewords; } descodificación
Debido a que el algoritmo de codificación de Huffman puede garantizar que cualquier código binario no sea el prefijo de otro código, la decodificación es muy simple. Saque cada bit de la secuencia binaria, busque desde la raíz del árbol, 1 a la derecha, 0 a la izquierda, alcance el nodo de la hoja (golpe) y regrese al nodo de la raíz y continúe repitiendo las acciones anteriores. El código es el siguiente:
public static String decode (String binarystr, map <caracteres, entero> estadísticas) {if (binarystr == null || binarystr.equals ("")) {return ""; } char [] binaryCharArray = binarystr.toCarArray (); LinkedList <Captact> binaryList = new LinkedList <arport> (); int size = binaryCharArray.length; para (int i = 0; i <size; i ++) {binaryList.addlast (nuevo carácter (binaryCharArray [i])); } List <node> feafNodes = new ArrayList <Node> (); Árbol de árbol = BuildTree (estadísticas, Nodos de hoja); StringBuffer Buffer = new StringBuffer (); while (binaryList.size ()> 0) {nodo nodo = tree.root; do {carácter c = binaryList.removeFirst (); if (c.charValue () == '0') {node = node.leftnode; } else {node = node.rightNode; }} while (! node.isleaf ()); buffer.append (node.chars); } return buffer.ToString (); } Prueba y comparación
Las siguientes pruebas sobre la corrección de la codificación de Huffman (codificadas primero, luego decodificadas, incluido el chino), y la comparación de la codificación de Huffman con carácter común que codifica cuerdas binarias. El código es el siguiente:
public static void main (string [] args) {string oistr = "Huffman codifica los datos de comprimir de manera muy efectiva: los ahorros del 20% al 90% son típicos," + "dependiendo de las características de los datos que se comprimen. Aumento de China"; Map <caracteres, integer> statistics = statistics (oistr.toCarArray ()); Cadena EncodedBinaristr = encode (oistr, estadísticas); String decodedstr = decode (codedbinarist, estadísticas); System.out.println ("Cadena original:" + orrist); System.out.println ("Huffman CONCOED Binary String:" + ENCODEDBINARISTR); System.out.println ("Cadena decodificada de la cadena binariy:" + decodedstr); System.out.println ("Cadena binaria de UTF-8:" + getStringOfByte (oistr, charset.forname ("utf-8"))); System.out.println ("Cadena binaria de UTF-16:" + getStringofbyte (oistr, charset.forname ("utf-16"))); System.out.println ("Cadena binaria de US-ASCII:" + getTringofbyte (oistr, charset.forname ("us-ascii"))); System.out.println ("Cadena binaria de GB2312:" + getStringOfByte (oistr, charset.forname ("GB2312"))); } cadena estática pública getTringofByte (string str, charset charset) {if (str == null || str.equals ("")) {return ""; } byte [] byteArray = str.getBytes (charset); int size = bytearray.length; StringBuffer Buffer = new StringBuffer (); para (int i = 0; i <size; i ++) {byte temp = bytearray [i]; buffer.append (getTringofByte (temp)); } return buffer.ToString (); } cadena estática pública getTringofByte (byte b) {stringBuffer buffer = new StringBuffer (); for (int i = 7; i> = 0; i--) {byte temp = (byte) ((b >> i) y 0x1); buffer.append (string.ValueOf (temp)); } return buffer.ToString (); }Lo anterior es todo el contenido de este artículo. Espero que sea útil para el aprendizaje de todos y espero que todos apoyen más a Wulin.com.