Bagaimana untuk melaksanakan algoritma pengekodan Huffman menggunakan java

Cara melaksanakan algoritma pengekodan Huffman dalam Java

Algoritma pengekodan Huffman ialah kaedah yang berkesan untuk pemampatan data, yang mengurangkan ruang storan dan penghantaran dengan menggunakan pengekodan yang lebih pendek untuk masa aksara yang lebih kerap. Artikel ini akan memperkenalkan cara menggunakan Java untuk melaksanakan algoritma pengekodan Huffman dan memberikan contoh kod khusus.

1. Pembinaan pokok Huffman

Pertama, kita perlu membina pokok Huffman. Pokok Huffman ialah pokok binari khas di mana setiap nod daun sepadan dengan watak, dan setiap nod bukan daun pokok itu mempunyai dua nod anak. Langkah-langkah untuk membina pokok Huffman adalah seperti berikut:

1.1 Cipta kelas nod

Pertama, kita perlu mencipta kelas nod untuk mewakili nod pokok Huffman. Kelas nod mengandungi tiga atribut: aksara, kekerapan dan nod anak kiri dan kanan.

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 Membina pokok Huffman

Langkah-langkah untuk membina pokok Huffman adalah seperti berikut:

• Buat senarai nod dan masukkan setiap aksara ke dalam senarai sebagai nod yang berasingan.
• Isih senarai nod daripada kecil kepada besar mengikut kekerapan.
• Keluarkan dua nod dengan kekerapan terkecil daripada senarai nod, buat nod baharu sebagai nod induknya dan masukkan nod baharu ini ke dalam senarai.
• Ulang langkah di atas sehingga hanya tinggal satu nod dalam senarai iaitu nod akar.

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. Generasi pengekodan Huffman

Seterusnya, kita perlu menjana pengekodan aksara berdasarkan pokok Huffman. Peraturan pengekodan ialah bermula dari nod akar, jika anda pergi ke subtree kiri, kodnya ialah 0, jika anda pergi ke subtree kanan, kodnya ialah 1. Untuk setiap aksara, kita boleh menjana pengekodan dengan melintasi pokok Huffman secara rekursif.

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. Mampatan dan penyahmampatan pengekodan Huffman

Dengan pengekodan Huffman, kami boleh memampatkan dan menyahmampat data.

3.1 Data mampat

Tukar data untuk dimampatkan kepada tatasusunan aksara, melintasi setiap aksara dan gunakan pengekodan Huffman untuk menjana rentetan dikodkan yang dimampatkan.

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 Data yang dinyahmampatkan

Untuk rentetan yang dikodekan, kita perlu menyahkod mengikut pokok Huffman, iaitu, melintasi rentetan yang dikodkan bermula dari nod akar Jika 0 ditemui, pergi ke subpokok kiri menemui 1, pergi ke subtree kanan sehingga anda menemui nod daun, iaitu, anda menemui watak asal.

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();
    }
}

Dengan menggunakan kod di atas, kita boleh melaksanakan algoritma pengekodan Huffman. Menggunakan pengekodan Huffman boleh memampatkan data pada tahap tertentu dan mengurangkan ruang penyimpanan dan masa penghantaran.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma pengekodan Huffman menggunakan java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!