快捷導(dǎo)航

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

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

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

前言

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

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

一、實(shí)現(xiàn)思路

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

二、準(zhǔn)備Huffman結(jié)點(diǎn)

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

三、主要實(shí)現(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");
    }
	//運(yùn)行結(jié)果
	//a: 0
	//c: 100
	//b: 101
	//f: 1100
	//e: 1101
	//d: 111

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

您可能感興趣的文章: