Huffman Encoding Introduction
Le codage de Huffman traite du problème de couplage de codage des caractères et du binaire correspondant aux caractères, qui est divisé en codage et décodage, dans le but de comprimer la longueur de données binaires correspondant aux caractères. Nous savons que lorsque les personnages sont stockés et transférés, ils sont binaires (l'ordinateur ne connaît que 0/1), il existe donc une relation de cartographie entre les personnages et le binaire. Les caractères appartiennent au jeu de caractères (Charset). Les caractères doivent être stockés et transmis en binaire via Encode. Lorsqu'ils sont affichés, ils doivent être décodés en caractères. Le jeu de caractères et les méthodes de codage sont des relations individuelles (Unicode peut être codé avec UTF-8, UTF-16, etc.). Après avoir compris le jeu de caractères, le codage et le décodage, le problème du code brouillé volant dans le ciel peut être facilement résolu. Prenant la minuscule A de la lettre anglaise à titre d'exemple, en codage ASCII, la décimale est 97 et le binaire est 01100001. Chaque caractère en ASCII est codé avec 8 bits (1 byte). S'il y a 1000 caractères à transmettre, 8000 bits doivent être transmis. Le problème est que la fréquence d'utilisation de la lettre E en anglais est de 12,702%, tandis que Z est de 0,074%. Le premier est plus de 100 fois celui des derniers, mais il utilise le binaire avec les mêmes chiffres. Cela peut être fait mieux, la méthode est un codage de longueur variable. Le principe directeur est de coder la fréquence plus élevée avec des chiffres plus courts et ceux à faible fréquence avec des chiffres plus longs. L'algorithme de codage de Huffman traite de tels problèmes.
Huffman Encoding Implémentation Java
Les structures de données principalement utilisées par l'algorithme de codage de Huffman sont des arbres binaires complets et des files d'attente prioritaires. Ce dernier utilise java.util.priorityqueue, et le premier s'implémente (tous sont des classes internes). Le code est le suivant:
Arbre de classe statique {racine du nœud privé; Node public getroot () {return root; } public void setroot (nœud root) {this.root = root; }} Le nœud de classe statique implémente le <node comparable> {private String chars = ""; fréquence int privée = 0; parent de nœud privé; Node privé LeftNode; Node privé RightNode; @Override public int compareto (nœud n) {return fréquence - 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 () {return fréquence; } public void setFrequence (int fréquence) {this.frequency = fréquence; } public String getchars () {return chars; } public void setChars (String Chars) {this.chars = chars; } Node public getParent () {return parent; } public void setParent (nœud parent) {this.parent = parent; } Node public getleftNode () {return LeftNode; } public void SetLeftNode (Node LeftNode) {this.leftnode = LeftNode; } noeud public getRightNode () {return reightNode; } public void setRightNode (nœud RightNode) {this.RightNode = RightNode; }} Statistiques
Étant donné que le tableau d'encodage doit être organisé en fonction de la fréquence, alors bien sûr, vous devez obtenir les informations statistiques de la fréquence. J'ai implémenté une méthode pour résoudre un tel problème. S'il y a déjà des statistiques, convertissez-vous en map <caractère, entier>. Si les informations que vous obtenez sont un pourcentage, multipliez par 100 ou 1000, ou 10000. Il peut toujours être converti en entier. Par exemple, 12,702% multipliés par 1000 est 12702, et le codage de Huffman ne se soucie que des problèmes de taille. La méthode statistique est mise en œuvre comme suit:
Map statique publique <caractère, entier> statistiques (char [] chararray) {map <caractère, entier> map = new hashmap <caractère, entier> (); pour (charc c: chararray) {caractère caractère = nouveau caractère (c); if (map.containsKey (caractères)) {map.put (caractères, map.get (caractères) + 1); } else {map.put (caractère, 1); }} retour de retour; } Construire un arbre
La construction d'un arbre est une étape de base dans l'algorithme de codage de Huffman. L'idée est d'accrocher tous les caractères sur un nœud feuille d'un arbre complètement binaire, et la fréquence du nœud gauche de tout nœud enfant non page n'apparaît pas plus que le nœud droit. L'algorithme convertit les statistiques en nœuds et les stocke dans une file d'attente prioritaire. Chaque fois que deux nœuds avec la fréquence minimale apparaissent à partir de la file d'attente, un nouveau nœud parent (nœud non-feuille) est construit. La somme des deux nœuds dont le contenu du personnage apparaît, et la fréquence est également leur somme. Le premier pop-up est utilisé comme nœud enfant gauche, et le suivant est utilisé comme nœud enfant droit, et le nœud parent nouvellement construit est placé dans la file d'attente. Répétez les actions ci-dessus n-1 fois, n est le nombre de caractères différents (le nombre dans la file d'attente est réduit de 1 à chaque fois). Terminez les étapes ci-dessus, il reste un nœud dans la file d'attente et le nœud racine de l'arbre apparaît. Le code est le suivant:
BuildTree d'arborescence statique privée (map <caractère, entier> statistiques, liste <Node> feuilles) {caractères [] keys = statistics.KeySet (). toArray (nouveau caractère [0]); PriorityQueue <Node> priorityQueue = new priorityQueue <Node> (); pour (caractères de caractère: touches) {node node = new node (); node.chars = caractères.toString (); node.frequency = statistics.get (caractères); priorityqueue.add (nœud); feuilles.add (nœud); } int size = priorityEue.size (); for (int i = 1; i <= size - 1; i ++) {node node1 = priorityQueue.poll (); Node node2 = priorityqueue.poll (); Node Sumnode = new node (); SUMNODE.CHARS = Node1.Chars + Node2.chars; SUMNODE.FREQUENCY = Node1.FraQuence + Node2.FraQuence; SUMNODE.LEFTNODE = NODE1; SUMNODE.RIGHTNODE = NODE2; Node1.parent = Sumnode; Node2.parent = Sumnode; priorityQueue.add (Sumnode); } Arbre arbre = new arbre (); Tree.root = priorityqueue.poll (); arbre de retour; } codage
Le codage correspondant d'un personnage est de rechercher à partir du nœud feuille où se trouve le caractère. Si le nœud de caractères est le nœud gauche du nœud parent, ajoutez 0 avant le caractère codé, sinon s'il s'agit du nœud droit, ajoutez 1 jusqu'au nœud racine. Tant que la relation de cartographie entre les caractères et le code binaire est obtenue, le codage est très simple. Le code est le suivant:
Encode de chaîne statique publique (String OriginalStr, map <caractère, entier> statistiques) {if (originaltr == null || originalstr.equals ("")) {return ""; } char [] chararray = originalstr.tocharArray (); List <Node> LeafNodes = new ArrayList <Node> (); BuildTree (statistiques, noons de feuilles); Map <caractère, string> codinfo = buildEncodingInfo (LeafNodes); StringBuffer Buffer = new StringBuffer (); pour (char c: chararray) {caractère caractère = nouveau caractère (c); Buffer.APPEND (encodinfo.get (caractère)); } return buffer.toString (); } Map statique privé <caractères, string> BuildEncodingInfo (list <Node> LeafNoDes) {map <caractères, string> Codewords = new Hashmap <caractères, string> (); pour (Node Node NEAFODES: Leafnodes) {Caractère de caractère = nouveau caractère (LeafNode.getchars (). Charat (0)); String Codeword = ""; Nœud currentNode = leafNode; do {if (currentNode.isleftchild ()) {Codeword = "0" + Codeword; } else {Codeword = "1" + Codeword; } currentNode = currentNode.parent; } while (currentNode.parent! = null); CodewordS.put (caractère, mot de code); } return Codewords; } décodage
Étant donné que l'algorithme de codage Huffman peut garantir que tout code binaire ne sera pas le préfixe d'un autre code, le décodage est très simple. Sortez chaque bit du binaire en séquence, recherchez de la racine de l'arbre, 1 vers la droite, 0 à gauche, atteignez le nœud feuille (hit), et revenez au nœud racine et continuez à répéter les actions ci-dessus. Le code est le suivant:
Public Static String Decode (String binarystr, map <caractère, entier> statistiques) {if (binarystr == null || binarystr.equals ("")) {return ""; } char [] binaryCararray = binarystr.tocharArray (); LinkedList <Garacter> binaryList = new LinkedList <Comacacre> (); int size = binaryCharArray.length; for (int i = 0; i <size; i ++) {binaryList.addlast (nouveau caractère (binaryCharArray [i])); } List <Node> LeafNodes = new ArrayList <Node> (); Tree Tree = BuildTree (statistiques, notes de feuilles); StringBuffer Buffer = new StringBuffer (); while (binaryList.size ()> 0) {node node = tree.root; do {caractère c = binaryList.RemoveFirst (); if (c.CharValue () == '0') {node = node.leftNode; } else {node = node.RightNode; }} while (! node.isleaf ()); Buffer.APPEND (Node.Chars); } return buffer.toString (); } Tester et comparaison
Les tests suivants sur l'exactitude du codage de Huffman (encodé d'abord, puis décodé, y compris le chinois), et la comparaison du codage de Huffman avec des caractères communs codant pour des cordes binaires. Le code est le suivant:
public static void main (String [] args) {String oRstr = "Huffman codes compress data très efficacement: des économies de 20% à 90% sont typiques," + "en fonction des caractéristiques de la compression des données. Map <caractère, entier> statistiques = statistiques (oRstr.tocharArray ()); Chaîne codée BinaRist = Encode (ORIRST, Statistiques); String DecodedStr = Decode (codéBinaristR, statistiques); System.out.println ("String d'origine:" + oRstr); System.out.println ("Huffman ENCOed Binary String:" + EncodedBinaRist); System.out.println ("String décodé de Binariy String:" + DecodedStr); System.out.println ("chaîne binaire d'UTF-8:" + GetStringofByte (oRist, charset.forname ("utf-8"))); System.out.println ("chaîne binaire de UTF-16:" + GetStringofByte (oRist, charset.forname ("utf-16"))); System.out.println ("chaîne binaire de US-ACCII:" + getStringofByte (oRist, charset.forname ("US-ACCII"))); System.out.println ("chaîne binaire de GB2312:" + getStringofByte (oRist, charset.forname ("gb2312"))); } public static String getStringofByte (String Str, Charset Charset) {if (str == null || str.equals ("")) {return ""; } byte [] bytearray = str.getBytes (charset); int size = bytearray.length; StringBuffer Buffer = new StringBuffer (); for (int i = 0; i <size; i ++) {byte temp = bytearray [i]; Buffer.APPEND (getStringofByte (temp)); } return buffer.toString (); } public static String getStringofByte (octet b) {stringBuffer buffer = new StringBuffer (); pour (int i = 7; i> = 0; i--) {octet temp = (byte) ((b >> i) & 0x1); Buffer.APPEND (String.ValueOf (TEMP)); } return buffer.toString (); }Ce qui précède est tout le contenu de cet article. J'espère que cela sera utile à l'apprentissage de tous et j'espère que tout le monde soutiendra davantage Wulin.com.