How to implement Huffman coding algorithm using java

How to use Java to implement the Huffman coding algorithm

The Huffman coding algorithm is an effective method for data compression, by compressing characters with higher frequency Use shorter encodings to reduce storage space and transmission time. This article will introduce how to use Java to implement the Huffman coding algorithm and give specific code examples.

1. Construction of Huffman tree

First, we need to build a Huffman tree. A Huffman tree is a special binary tree in which each leaf node corresponds to a character, and each non-leaf node of the tree has two child nodes. The steps to build a Huffman tree are as follows:

1.1 Create a node class

First, we need to create a node class to represent the nodes of the Huffman tree. The node class contains three attributes: character, frequency, and left and right child nodes.

class Node {
    char data;
    int frequency;
    Node left;
    Node right;

    // 构造函数
    public Node(char data, int frequency){
        this.data = data;
        this.frequency = frequency;
        left = null;
        right = null;
    }
}

1.2 Constructing a Huffman tree

The steps to construct a Huffman tree are as follows:

• Create a node list and treat each character as a separate The node is inserted into the list.
• Sort the node list according to frequency from small to large.
• Take out the two nodes with the smallest frequency from the node list, create a new node as their parent node, and insert the new node into the list.
• Repeat the above steps until there is only one node left in the list, the root node.

class HuffmanTree {
    public static Node buildHuffmanTree(HashMap<Character, Integer> frequencies) {
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.frequency));
        
        // 将每个字符作为一个单独的节点插入到优先队列中
        for (Map.Entry<Character, Integer> entry : frequencies.entrySet()) {
            pq.offer(new Node(entry.getKey(), entry.getValue()));
        }
        
        // 构建哈夫曼树
        while (pq.size() > 1) {
            Node leftChild = pq.poll();
            Node rightChild = pq.poll();
            Node parent = new Node('', leftChild.frequency + rightChild.frequency);
            parent.left = leftChild;
            parent.right = rightChild;
            pq.offer(parent);
        }
        
        return pq.peek();
    }
}

2. Generation of Huffman encoding

Next, we need to generate the character encoding based on the Huffman tree. The coding rule is that starting from the root node, if you go to the left subtree, the code is 0, if you go to the right subtree, the code is 1. For each character, we can generate the encoding by recursively traversing the Huffman tree.

class HuffmanEncoding {
    public static String getHuffmanCode(Node root, char target) {
        StringBuilder code = new StringBuilder();
        generateHuffmanCode(root, target, code);
        return code.toString();
    }

    private static void generateHuffmanCode(Node node, char target, StringBuilder code) {
        if (node == null) {
            return;
        }
        
        if (node.data == target) {
            return;
        }
        
        // 往左子树走
        code.append('0');
        generateHuffmanCode(node.left, target, code);
        
        if (code.charAt(code.length() - 1) != '1') {
            code.deleteCharAt(code.length() - 1);
            // 往右子树走
            code.append('1');
            generateHuffmanCode(node.right, target, code);
        }
        
        if (code.charAt(code.length() - 1) != '1') {
            code.deleteCharAt(code.length() - 1);
        }
    }
}

3. Compression and decompression of Huffman coding

With Huffman coding, we can compress and decompress data.

3.1 Compressed data

Convert the data to be compressed into a character array, traverse each character, and use Huffman coding to generate a compressed encoded string.

class HuffmanCompression {
    public static String compressData(String data, HashMap<Character, String> huffmanCodes) {
        StringBuilder compressedData = new StringBuilder();
        char[] characters = data.toCharArray();

        for (char c : characters) {
            compressedData.append(huffmanCodes.get(c));
        }

        return compressedData.toString();
    }
}

3.2 Decompress data

For the compressed encoded string, we need to decode it according to the Huffman tree, that is, traverse the encoded string starting from the root node. If 0 is encountered, Then go to the left subtree. If you encounter 1, go to the right subtree until you find the leaf node, that is, you find the original character.

class HuffmanDecompression {
    public static String decompressData(String compressedData, Node root) {
        StringBuilder decompressedData = new StringBuilder();
        Node currentNode = root;
        
        for (char bit : compressedData.toCharArray()) {
            if (bit == '0') {
                currentNode = currentNode.left;
            } else if (bit == '1') {
                currentNode = currentNode.right;
            }
            
            if (currentNode.left == null && currentNode.right == null) {
                decompressedData.append(currentNode.data);
                currentNode = root;
            }
        }
        
        return decompressedData.toString();
    }
}

By using the above code, we can implement the Huffman coding algorithm. Using Huffman coding can compress data to a certain extent and reduce storage space and transmission time.

The above is the detailed content of How to implement Huffman coding algorithm using java. For more information, please follow other related articles on the PHP Chinese website!