快捷導(dǎo)航

Java實現(xiàn)Huffman編碼的示例代碼

更新時間：2023年08月30日 10:01:20 作者：Robinsyn_L

Huffman編碼是一種編碼方式,本文主要介紹了Java實現(xiàn)Huffman編碼的示例代碼,具有一定的參考價值,感興趣的可以了解一下

前言

在使用http1.1協(xié)議傳輸數(shù)據(jù)的時候，會有一些固定的字段，比如cookie、編碼方式、接收的數(shù)據(jù)類型，另外會有一些大量重復(fù)的字段造成請求報文過于冗長，為了解決這個問題，在http2.0的時候，采用了二進制對請求報文進行編碼，同時客戶端和服務(wù)端維護一張靜態(tài)表和靜態(tài)表，對我們的請求報文進行二進制編碼，同時采用Huffman編碼進行壓縮。

Huffman編碼是一種編碼方式，對出現(xiàn)頻次更高的字段采取更短的編碼，Huffman編碼要求每個字符的編碼不能是其他字符編碼的前綴，這篇文章就是準備記錄一下用Java實現(xiàn)Huffman編碼。

一、實現(xiàn)思路

將出現(xiàn)的字符和字符出現(xiàn)的頻次一一映射，將所有字符放進優(yōu)先隊列，優(yōu)先隊列的堆頂存放的是頻次最小的字符，彈出頻次最小的的兩個字符，申請一個新的根節(jié)點，新的根節(jié)點左子結(jié)點是最小頻次的字符，右子結(jié)點是第二小頻次的字符，頻次為左子節(jié)點和右子結(jié)點頻次的和，將新結(jié)點加入優(yōu)先隊列重復(fù)上述過程

二、準備Huffman結(jié)點

public class Node {
	//編碼字符
    private char data;
    //頻次
    private int freq;
    //左子節(jié)點
    private Node left;
    //右子節(jié)點
    private Node right;
}

三、主要實現(xiàn)

public static void main(String[] args) {
        char[] charArray = { 'a', 'b', 'c', 'd', 'e', 'f' };
        int[] charFreq = { 45, 13, 12, 16, 9, 5 };
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(6, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.getFreq() - o2.getFreq();
            }
        });
        for (int i = 0; i < 6; i++) {
            Node node = new Node();
            node.setData(charArray[i]);
            node.setFreq(charFreq[i]);
            priorityQueue.add(node);
        }
        Node root = null;
        while (priorityQueue.size() > 1) {
            Node newNode = new Node();
            Node left = priorityQueue.peek();
            newNode.setLeft(left);
            priorityQueue.poll();
            Node right = priorityQueue.peek();
            newNode.setRight(right);
            priorityQueue.poll();
            newNode.setFreq(left.getFreq() + right.getFreq());
            root = newNode;
            priorityQueue.add(newNode);
        }
        printCode(root, "");
    }
    public static void printCode(Node root, String code) {
        if (root.getLeft() == null && root.getRight() == null && Character.isLetter(root.getData())) {
            System.out.println(root.getData() + ": " + code);
            return;
        }
        printCode(root.getLeft(), code + "0");
        printCode(root.getRight(), code + "1");
    }
	//運行結(jié)果
	//a: 0
	//c: 100
	//b: 101
	//f: 1100
	//e: 1101
	//d: 111

到此這篇關(guān)于Java實現(xiàn)Huffman編碼的示例代碼的文章就介紹到這了,更多相關(guān)Java Huffman編碼內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: