霍夫曼算法代碼java 編程實(shí)現(xiàn)霍夫曼編碼

求高手寫(xiě)個(gè)關(guān)于哈夫曼編碼的算法

恩，樓主這個(gè)題目相當(dāng)復(fù)雜啊

創(chuàng)新互聯(lián)公司堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都網(wǎng)站建設(shè)、網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿(mǎn)足客戶(hù)于互聯(lián)網(wǎng)時(shí)代的青山湖網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

首先讀文件，按字符讀。一個(gè)一個(gè)讀，統(tǒng)計(jì)所有出現(xiàn)字符的頻數(shù)。

記錄到一個(gè)鏈表里吧

第二步，建樹(shù)?；舴蚵鼧?shù)……復(fù)雜程度可想而知。

Huffman 算法

思想： 權(quán)大的外結(jié)點(diǎn)靠近根， 權(quán)小的遠(yuǎn)離根。

算法： 從m個(gè)權(quán)值中找出兩個(gè)最小值W1，W2構(gòu)成

w

w1 w2 W=W1+W2表通過(guò)該結(jié)點(diǎn)的頻度。

依次往上找……

估計(jì)你的100個(gè)字符的短文，出現(xiàn)的字符數(shù)量估計(jì)平均有20個(gè)左右，建的樹(shù)的高度就12就算低的。

3 按結(jié)點(diǎn)到跟的距離編碼，從左到右編碼為0 1 0 1依次進(jìn)行……

生成霍夫曼編碼

把每個(gè)字幕的二進(jìn)制編碼記錄，打出，這就是密碼表

然后對(duì)原來(lái)的文件進(jìn)行打印，碰到相應(yīng)的字母打印出相應(yīng)的密碼（二進(jìn)制啊，汗……）

估計(jì)只有拿到密碼才能看明白那一串的01！！

如果某一電文出現(xiàn)的字符為D={M，S，T，A，Q， K} ， 每個(gè)字符出現(xiàn)的頻率為W={10，29，4，8，15，7}，

則用改算法生成的密碼為：

S：0 A：100 M：101 Q：111

T：1100 K：1101

100 1100 101 0 111 0 1101 0 0 密文的含義是：

A T M S Q S K S S

用java實(shí)現(xiàn)哈夫曼編碼

只要自己再加個(gè)類(lèi)Tree就可以了。

代碼如下：

public class Tree {

double lChild, rChild, parent;

public Tree (double lChild, double rChild, double parent) {

this.lChild = lChild;

this.rChild = rChild;

this.parent = parent;

}

public double getLchild() {

return lChild;

}

public void setLchild(double lChild) {

this.lChild = lChild;

}

public double getRchild() {

return rChild;

}

public void setRchild(double rChild) {

this.rChild = rChild;

}

public double getParents() {

return parent;

}

public void setParents(double root) {

this.parent = root;

}

}

JAVA和數(shù)據(jù)結(jié)構(gòu)大蝦們幫下忙： 輸入一段文字，該程序可以統(tǒng)計(jì)出每個(gè)字符出現(xiàn)的次數(shù)并對(duì)字符進(jìn)行哈夫曼編碼

寫(xiě)給你了，請(qǐng)發(fā)JAVA版塊

package other;

import java.io.Serializable;

import java.util.ArrayList;

import java.util.Collections;

import java.util.HashMap;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

/**

* 定義了一種接口，要進(jìn)行編碼的最小單元類(lèi)必需實(shí)現(xiàn)些接口

*

*/

interface CombinableT extends ComparableT {

T combinate(T a, T b);

}

/**

*

* the huffman tree Class 哈夫曼樹(shù)，包括當(dāng)前節(jié)點(diǎn)數(shù)據(jù)信息，左節(jié)點(diǎn)，右節(jié)點(diǎn)信息。

*/

class HuffmanTreeT extends CombinableT implements

ComparableHuffmanTreeT {

/** the root of huffman tree */

private T root;

/** the left node of huffman tree */

private HuffmanTreeT left;

/** the right node of huffman tree */

private HuffmanTreeT right;

/** 哈夫曼編碼字符串，如:0000110 */

private String huffmanCodeString = "";

/** 是否對(duì)最終生成的哈夫曼進(jìn)行過(guò)編碼操作 */

private static boolean isSettedHuffmanCoderString = false;

public T getRoot() {

return root;

}

public void setRoot(T root) {

this.root = root;

}

public HuffmanTreeT getLeft() {

return left;

}

public void setLeft(HuffmanTreeT left) {

this.left = left;

}

public HuffmanTreeT getRight() {

return right;

}

public void setRight(HuffmanTreeT right) {

this.right = right;

}

/**

*

* 重寫(xiě)此方法用于遞歸合并節(jié)點(diǎn)后進(jìn)行排序操作

*

*/

public int compareTo(HuffmanTreeT o) {

return o.getRoot().compareTo(this.getRoot());

}

public String toString() {

return "the root:" + this.getRoot() + "\r\nthe left:" + this.getLeft()

+ "\r\nthe right:" + this.getRight();

}

/**

*

* 對(duì)最終生成的樹(shù)進(jìn)行哈夫曼編碼，使每個(gè)葉子節(jié)點(diǎn)生成01的路徑編碼

*

*/

private void setHuffmanCoderString() {

HuffmanTreeT left = this.getLeft();

// 如果有左節(jié)點(diǎn)則在路徑中追加"0"

if (left != null) {

left.huffmanCodeString = this.huffmanCodeString + "0";

left.setHuffmanCoderString();// 遞歸編碼

}

HuffmanTreeT right = this.getRight();

// 如果有右節(jié)點(diǎn)則在路徑中追加"1"

if (right != null) {

right.huffmanCodeString = this.huffmanCodeString + "1";

right.setHuffmanCoderString();// 遞歸編碼

}

}

public void printHuffmanCoderString() {

// 打印最終生成樹(shù)的哈夫曼編碼前要進(jìn)行編碼操作，

// 且此操作只執(zhí)行一次，所以用全局標(biāo)識(shí)變量判斷

if (!HuffmanTree.isSettedHuffmanCoderString) {

this.setHuffmanCoderString();

HuffmanTree.isSettedHuffmanCoderString = true;// 標(biāo)識(shí)已執(zhí)行過(guò)編碼

}

// 如果是葉子節(jié)點(diǎn)（即要編碼的單元），則打印出編碼信息，如果是非葉子結(jié)點(diǎn)（中間臨時(shí)生成的節(jié)點(diǎn)），則不打印

if (this.left == null this.right == null)

System.out.println("the " + this.getRoot() + " huffmanCoder:"

+ this.huffmanCodeString);

if (this.left != null)

this.left.printHuffmanCoderString();// 遞歸打印

if (this.right != null)

this.right.printHuffmanCoderString();// 遞歸打印

}

}

/**

*

* 用類(lèi)用于生成一個(gè)哈夫曼樹(shù)

*/

class HuffmanTreeFactoryT extends CombinableT {

/** 初始時(shí)一個(gè)list列表當(dāng)作要編碼的單元類(lèi)的容器 */

private ListHuffmanTreeT HuffmanTreeCollection;

/**

*

* @param unitClasses

* 待編碼的單元類(lèi)集合

*

*/

public HuffmanTreeFactory(ListT unitClasses) {

if (unitClasses == null || unitClasses.size() == 0)

throw new IllegalArgumentException(

"the unit classes collection can't be empty");

HuffmanTreeCollection = new LinkedListHuffmanTreeT();

// 初始化哈夫曼集合容器

for (T unitClass : unitClasses) {

HuffmanTreeT huffmanTree = new HuffmanTreeT();

huffmanTree.setRoot(unitClass);

huffmanTree.setLeft(null);

huffmanTree.setLeft(null);

HuffmanTreeCollection.add(huffmanTree);

}

Collections.sort(HuffmanTreeCollection);

}

/**

* 將待編碼的哈夫曼集合處理成只含有一個(gè)元素的集合，則這最后一個(gè)元素 即為最終生成的哈夫曼樹(shù)

*/

private void generateHuffmanTree() {

while (true) {

if (HuffmanTreeCollection == null

|| HuffmanTreeCollection.size() = 1)

break;

// 處理之前一定要重新排序，這是哈夫曼編碼的關(guān)鍵原理

Collections.sort(HuffmanTreeCollection);

HuffmanTreeT huffmanTreeOne = HuffmanTreeCollection.remove(0);

HuffmanTreeT huffmanTreeTwo = HuffmanTreeCollection.remove(0);

HuffmanTreeT huffmanTreeNew = new HuffmanTreeT();

// 將集合中前面兩個(gè)元素合并成一個(gè)元素插到集合中去

// 并將第一個(gè)元素和第二個(gè)元素分別作為新元素的左，右節(jié)點(diǎn)

huffmanTreeNew.setRoot(huffmanTreeOne.getRoot().combinate(

huffmanTreeOne.getRoot(), huffmanTreeTwo.getRoot()));

huffmanTreeNew.setLeft(huffmanTreeOne);

huffmanTreeNew.setRight(huffmanTreeTwo);

HuffmanTreeCollection.add(huffmanTreeNew);

}

}

/**

*

*

*

* @return 生成最終的哈夫曼樹(shù)

*

*/

public HuffmanTreeT getHuffmanTree() {

generateHuffmanTree();

return this.HuffmanTreeCollection.get(0);

}

}

/**

* 自定義一個(gè)用于測(cè)試的單元類(lèi)

*/

class UnitClass implements Serializable, CombinableUnitClass {

/** 出現(xiàn)概率數(shù)據(jù) */

private int rate;

public UnitClass(int rate) {

this.rate = rate;

}

public int getRate() {

return rate;

}

public void setRate(int rate) {

this.rate = rate;

}

/**

* implements thid compartTo() in order to sort the

*

* collection stored from unitclass

*/

public int compareTo(UnitClass o) {

return o.getRate() this.rate ? 1 : o.getRate() this.rate ? -1 : 0;

}

public String toString() {

return "the rate is:" + rate;

}

/**

*

* 重寫(xiě)此方法用于哈夫曼編碼時(shí)可以合并兩個(gè)分支點(diǎn)信息

*

*/

public UnitClass combinate(UnitClass a, UnitClass b) {

if (a == null || b == null)

return null;

return new UnitClass(a.getRate() + b.getRate());

}

}

public class Test {

public static int counter(String s, char c) {

int count = 0;

for (int i = 0; i s.length(); i++) {

if (s.charAt(i) == c) {

count++;

}

}

return count;

}

public static void main(String[] args) {

String str = "你好呵呵123abbeab啊";

ListUnitClass l = new ArrayListUnitClass();

for (int i = 0; i str.length(); i++) {

char c = str.charAt(i);

System.out.println(c + "出現(xiàn)了" + counter(str, c) + "次");

l.add(new UnitClass(c));

}

HuffmanTreeFactoryUnitClass factory = new HuffmanTreeFactoryUnitClass(

l);

factory.getHuffmanTree().printHuffmanCoderString();

}

}

當(dāng)前文章：霍夫曼算法代碼java 編程實(shí)現(xiàn)霍夫曼編碼
分享地址：http://www.muchs.cn/article30/ddcedpo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供云服務(wù)器、服務(wù)器托管、網(wǎng)頁(yè)設(shè)計(jì)公司、搜索引擎優(yōu)化、企業(yè)建站、網(wǎng)站改版

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)