Shulou(Shulou.com)06/01 Report--

This article mainly introduces the example analysis of the Hoffman tree in java, which has a certain reference value, and interested friends can refer to it. I hope you will gain a lot after reading this article.

Hoffman Tree I. basic introduction

2. Several important concepts and examples of Hoffman tree

The steps to construct a Hoffman tree

For example: arr = {13 6 7 8 13 29}

Public class HuffmanTree {public static void main (String [] args) {int [] arr = {13,7,8,3,29,6,1}; Node root = createHuffmanTree (arr); preOrder (root) } / / write a preorder traversal method public static void preOrder (Node root) {if (root! = null) {root.preOrder ();} else {System.out.println ("Tree is empty and cannot be traversed ~") }} / / the method to create a Huffman tree / * @ param arr needs to create an array of Huffman trees * @ return the root node of the Huffman tree created * / public static Node createHuffmanTree (int [] arr) {/ / the first step is to Easy to operate / / 1. Traverse the arr array / / 2. Compose each element of arr into a Node / / 3. Put Node into ArrayList List nodes = new ArrayList (); for (int value: arr) {nodes.add (new Node (value));} while (nodes.size () > 1) {/ / sort from small to large Collections.sort (nodes) System.out.println ("nodes =" + nodes) / / take out the two binary trees with the lowest root node weight / / Note: if they are arranged from the largest to the smallest, you should take the penultimate and penultimate / / (1) take out the node with the lowest weight (binary tree) Node leftNode = nodes.get (0) / / (2) take out the node with the second lowest weight (binary tree) Node rightNode = nodes.get (1); / / (3) build a new binary tree Node parent = new Node (leftNode.value + rightNode.value); parent.left = leftNode Parent.right = rightNode; / / (4) delete the processed binary tree nodes.remove (leftNode) from ArrayList; nodes.remove (rightNode); / / (5) add parent to nodes nodes.add (parent) } / / returns the root node return nodes.get (0) of the Huffman tree;} / / create a node class / / in order for the Node object to support sorting Collections collections sort / / let Node implement the Comparable interface class Node implements Comparable {int value;// node weight Node left;// points to the left child node Node right / / point to the right child node public Node (int value) {this.value = value;} / / write a preorder traversal public void preOrder () {System.out.println (this); if (this.left! = null) {this.left.preOrder () } if (this.right! = null) {this.right.preOrder ();} @ Override public String toString () {return "Node [value=" + value + "]" } @ Override public int compareTo (Node o) {/ / means to arrange return this.value-o.value from small to large;}} Huffman coding I. basic introduction

Second, principle analysis

6) description:

The original length is 359, compressed (359-133) / 359 = 62.9%

This encoding satisfies the prefix encoding, that is, the encoding of the characters cannot be the prefix of other character encodings. It will not cause polysemy of matching.

Huffman coding is a lossless compression scheme.

Note:

Notes on Hoffman coding compressed files

1) if the file itself is compressed, there will be no significant change in compression efficiency using Huffman coding, such as video, ppt, and so on.

2) Huffman coding is processed in bytes, so it can handle all files (binary files, text files).

3) if there is not much repeated data in a file, the compression effect will not be obvious.

Thank you for reading this article carefully. I hope the article "sample Analysis of Hoffman Tree in java" shared by the editor will be helpful to you. At the same time, I also hope you will support us and pay attention to the industry information channel. More related knowledge is waiting for you to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.