[👨‍💻🇻🇳] Huffman Decoding: Quá trình giải nén

Ở bài viết Cài đặt thuật toán Huffman Coding, chúng ta đã tìm hiểu cách cài đặt thuật toán Huffman Coding để mã hóa (nén) chuỗi dữ liệu thành chuỗi nhị phân. Trong bài viết này, chúng ta sẽ tiếp tục tìm hiểu quá trình giải nén dữ liệu từ cây Huffman và cài đặt phương thức decode(String encoded) cho class HuffmanCoding.

Để giải mã chuỗi nhị phân đã mã hóa, chúng ta cần có cây Huffman (cây nhị phân mã hóa chứa giá trị mã hóa của từng ký tự). Sau đó, duyệt tuần tự qua chuỗi bit mã hóa theo các bước sau:

1.1. Duyệt qua từng bit của chuỗi bit mã hóa từ nút gốc đến khi gặp nút lá.
1.2. Nếu bit hiện tại là bit 0, chuyển qua nhánh trái.
1.3. Nếu bit hiện tại là bit 1, chuyển qua nhánh phải.
1.4. Khi gặp nút lá, ta thêm ký tự ở nút lá vào chuỗi kết quả. Sau đó trở lại nút gốc cho bit tiếp theo.

Trở lại với class HuffmanCoding trong bài viết Cài đặt thuật toán Huffman Coding, chúng ta sẽ cài đặt phương thức decode(String encoded) của class này.

Thuật toán có thể được cài đặt như sau:

public String decode(String encoded) {
    Node node = this.root;
    StringBuilder result = new StringBuilder();
    for (char c : encoded.toCharArray()) {
        node = c == '0' ? node.getLeft() : node.getRight();
        if (node.isLeaf()) {
            result.append(node.getCharacter());
            node = root;
        }
    }
    return result.toString();
}

Test lại với hàm main:

public static void main(String[] args) {
    String str = "Hellooo!";
    System.out.println("Source: " + str);

    HuffmanCoding h = new HuffmanCoding().process(str);
    String encoded = h.encode();
    System.out.println("Encoded: " + encoded);
    System.out.println("Decoded: " + h.decode(encoded));
}

Kết quả là:

Source: Hellooo!
Encoded: 110111110100001110
Decoded: Hellooo!

References

#Huffman #Decoding #Quá #trình #giải #nén

[give_form id="2868661"]

[👨‍💻🇻🇳] Huffman Decoding: Quá trình giải nén

[👨‍💻🇻🇳] Cài đặt thuật toán Huffman Coding

Những mẫu tóc trẻ em nam đẹp dễ thương khiến ai cũng khen [🛍️🇻🇳] fado.vn

[🛍️🇻🇳] Shopee Việt Nam 🛍️ Top1Shop ❤️️ – SIÊU SALE LẠI TỚI – ĐÓN QUÀ PHƠI PHỚI 1️⃣ Follow Shopee Fanpage và thích bài vi …

Top 499++ tên thánh cho nữ cực ý nghĩa ít ai biết [🛍️🇻🇳] fado.vn

[🧘🇻🇳] Nguyễn Hiếu Yoga 🧘Top1Yoga🕉️ – Yoga Hiếu Nguyễn nhắc đến tên bạn. Giảm mỡ bụng, Giảm Cân quá dễ khi áp d …

Compare items

Shopping cart