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

This article will explain in detail how to achieve Huffman compression and decompression in java. The editor thinks it is very practical, so I share it with you for reference. I hope you can get something after reading this article.

A Huffman tree and the principle of file compression

1. Huffman tree:

Given N weights as N leaf nodes, a binary tree is constructed. If the weighted path length of the tree reaches the minimum, the binary tree is called the optimal binary tree, also known as Huffman tree. Huffman tree is the tree with the shortest length of weighted path, and the node with larger weight is closer to the root (the node with higher frequency is closer to the root).

Take the following array as an example to construct a Huffman tree

Int a [] = {0pm 1pm 2je 3je 45pm 6je 7je 8}

We can find the following rules

The Huffman tree composed of 1:9 has a total of 17 nodes, that is, n can produce 2*n-1 nodes.

2: the larger the number, the closer to the root node, and the smaller the number, the closer to the root node.

two。 How to use haffman coding to achieve file compression:

For example, the abc.txt file has the following characters: aaaabbbccde

1. Carry out character statistics

Aaaabbbccde a: 4 times b: 3 times c: 2 times d: 1 times e: 1 times

two。 Construction of Huffman Tree based on Statistical results

3. Use Huffman tree to generate Huffman code (starting from the root node, the path is marked as 0 on the left and 1 on the right):

A code: 1b code: 01c code: 000d code: 0011e code: 0010

4. Huffman coding is used instead of characters for compression.

The content of the source file is: aaaabbbccde replaces the source file with the corresponding Huffman encoding (haffman code), then: 11110101 01000000 00110010 (a total of 3 bytes)

Thus, the source file has a total of 11 characters, accounting for 11 bytes of memory, but after being replaced with haffman code, it only occupies 3 bytes, so the purpose of compression can be achieved.

Two main technical points:

1. Huffman tree algorithm (basic algorithm of Huffman compression)

two。 Hash algorithm (can be used in character statistics, or you can use HashMap statistics directly)

3. Bit operation (which involves positioning, setting 0 or 1)

4.java file operations, as well as buffer operations.

5. Storage mode (large-end storage, small-end storage, can read file hexadecimal form)

7. Set the compression password, decompress and input the password to decompress (the content added by the editor himself)

Third, the realization process:

Take the above aaaabbbccde as an example

1. Character statistics:

Public class FreqHuf {public static int BUFFER_SIZE = 1

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.