Java 中的霍夫曼程式碼

Sheeraz Gul 2022年4月26日
Java 中的霍夫曼程式碼

霍夫曼編碼是一種建立節點二叉樹的資料壓縮演算法。該節點可以是內部節點或葉節點。

本教程詳細描述並演示了使用 Java 的 Huffman 程式碼。

在 Java 中演示使用 Huffman 編碼演算法

霍夫曼編碼演算法的思想是根據相應字元的頻率為輸入字元分配可變長度程式碼。

這些程式碼被稱為字首程式碼,因為賦予每個字元的程式碼是唯一的,這有助於霍夫曼編碼的解碼沒有任何歧義。

我們可以使用 Java 中的優先順序佇列構建 Huffman 樹,其中優先順序最高的節點頻率最低。我們將按照下面給出的步驟進行。

  • 首先,為給定文字的每個字元建立一個葉節點,並將節點新增到優先順序佇列中。
  • 如果佇列中有多個節點,則從該佇列中刪除頻率最低且優先順序最高的兩個節點。
  • 現在,建立一個新節點,其中包含之前刪除的兩個子節點,新節點的頻率將等於兩個節點的頻率之和。然後將該節點新增到優先順序佇列中。
  • 最後剩下的節點就是根節點,樹就完成了。

讓我們看一個將文字轉換為霍夫曼編碼的 Java 示例。

主類 Huffman.java

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Huffman
{
    // Huffman Tree Traversing and storing the Huffman Codes in a dictionary.
    public static void encode_huffman(Huffman_Node root_node, String str,
                        Map<Character, String> huffman_Code)
    {
        if (root_node == null) {
            return;
        }

        // if the root node is a leaf node
        if (is_Leaf(root_node)) {
            huffman_Code.put(root_node.charac, str.length() > 0 ? str : "1");
        }

        encode_huffman(root_node.left, str + '0', huffman_Code);
        encode_huffman(root_node.right, str + '1', huffman_Code);
    }

    // Huffman Tree Traversing and decoding the encoded string
    public static int decode_huffman(Huffman_Node root_node, int index, StringBuilder sb)
    {
        if (root_node == null) {
            return index;
        }

        // if the root node is a leaf node
        if (is_Leaf(root_node))
        {
            System.out.print(root_node.charac);
            return index;
        }

        index++;

        root_node = (sb.charAt(index) == '0') ? root_node.left : root_node.right;
        index = decode_huffman(root_node, index, sb);
        return index;
    }

    // This function checks if Huffman Tree contains only one single node
    public static boolean is_Leaf(Huffman_Node root_node) {
        return root_node.left == null && root_node.right == null;
    }

    // Main Huffman tree build function
    public static void Main_Build_HuffmanTree(String text)
    {
        // Base case: empty string
        if (text == null || text.length() == 0) {
            return;
        }

        // Calculate the frequency of each character and store it in a map of dict

        Map<Character, Integer> frequency = new HashMap<>();
        for (char c: text.toCharArray()) {
            frequency.put(c, frequency.getOrDefault(c, 0) + 1);
        }

        // priority queue to store nodes of the Huffman tree
        // the highest priority item has the lowest frequency

        PriorityQueue<Huffman_Node> prio_queue;
        prio_queue = new PriorityQueue<>(Comparator.comparingInt(l -> l.frequency));

        // leaf node for each character, adding it to the priority queue.

        for (var entry: frequency.entrySet()) {
            prio_queue.add(new Huffman_Node(entry.getKey(), entry.getValue()));
        }

        //repeat the process till there is more than one node in the queue
        while (prio_queue.size() != 1)
        {
            // Then remove the two nodes with the highest priority and lowest frequency

            Huffman_Node left = prio_queue.poll();
            Huffman_Node right = prio_queue.poll();

            // Now create a new internal node with two children nodes, and the frequency will be the some of both nodes; add the new node to the priority queue.
            int sum = left.frequency + right.frequency;
            prio_queue.add(new Huffman_Node(null, sum, left, right));
        }

        Huffman_Node root_node = prio_queue.peek();

        // Huffman tree Traversing and storing the Huffman codes in a dict or map
        Map<Character, String> huffmanCode = new HashMap<>();
        encode_huffman(root_node, "", huffmanCode);

        // Display the Huffman codes
        System.out.println("The Huffman Codes for the given text are: " + huffmanCode);
        System.out.println("The original text is: " + text);

        // display the encoded string
        StringBuilder sb = new StringBuilder();
        for (char c: text.toCharArray()) {
            sb.append(huffmanCode.get(c));
        }

        System.out.println("The encoded text is: " + sb);
        System.out.print("The decoded text is: ");

        if (is_Leaf(root_node))
        {
            // For input like a, aa, aaa, etc.
            while (root_node.frequency-- > 0) {
                System.out.print(root_node.charac);
            }
        }
        else {
            // Huffman Tree traversing with decoding the encoded string
            int index = -1;
            while (index < sb.length() - 1) {
                index = decode_huffman(root_node, index, sb);
            }
        }
    }

    // Call the Huffman code
    public static void main(String[] args)
    {
        String text = "This is delftstack";
        Main_Build_HuffmanTree(text);
    }
}

節點類 Huffman_Node.java

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

// A Tree node
class Huffman_Node
{
    Character charac;
    Integer frequency;
    Huffman_Node left = null, right = null;

    Huffman_Node(Character charac, Integer frequency)
    {
        this.charac = charac;
        this.frequency = frequency;
    }

    public Huffman_Node(Character charac, Integer frequency, Huffman_Node left, Huffman_Node right)
    {
        this.charac = charac;
        this.frequency = frequency;
        this.left = left;
        this.right = right;
    }
}

第一類是執行霍夫曼編碼演算法操作的主要類,第二類是用於建立節點的類。該程式碼將為給定文字、編碼文字生成霍夫曼程式碼,並對其進行解碼。

輸出:

The Huffman Codes for the given text are: { =010, a=11100, c=1010, d=11101, e=1000, f=11011, H=0110, h=10010, i=1111, k=11010, l=000, m=01110, .=01111, o=1100, s=001, T=10011, t=1011}
The original text is: Hello This is delftstack.com
The encoded text is: 011010000000001100010100111001011110010101111001010111011000000110111011001101111100101011010011111010110001110
The decoded text is: Hello This is delftstack.com

我們可以看到,給定的文字包含 25 個字元,即 25×8 = 200 位,而編碼的字串只有 111 位,幾乎 45% 的資料壓縮。這種資料壓縮是霍夫曼編碼的主要目的。

Author: Sheeraz Gul
Sheeraz Gul avatar Sheeraz Gul avatar

Sheeraz is a Doctorate fellow in Computer Science at Northwestern Polytechnical University, Xian, China. He has 7 years of Software Development experience in AI, Web, Database, and Desktop technologies. He writes tutorials in Java, PHP, Python, GoLang, R, etc., to help beginners learn the field of Computer Science.

LinkedIn Facebook