霍夫曼算法代码java 编程实现霍夫曼编码
求高手写个关于哈夫曼编码的算法
恩,楼主这个题目相当复杂啊
创新互联公司坚持“要么做到,要么别承诺”的工作理念,服务领域包括:成都网站建设、网站制作、企业官网、英文网站、手机端网站、网站推广等服务,满足客户于互联网时代的青山湖网站设计、移动媒体设计的需求,帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴!
首先读文件,按字符读。一个一个读,统计所有出现字符的频数。
记录到一个链表里吧
第二步,建树。霍夫曼树……复杂程度可想而知。
Huffman 算法
思想: 权大的外结点靠近根, 权小的远离根。
算法: 从m个权值中找出两个最小值W1,W2构成
w
w1 w2 W=W1+W2表通过该结点的频度。
依次往上找……
估计你的100个字符的短文,出现的字符数量估计平均有20个左右,建的树的高度就12就算低的。
3 按结点到跟的距离编码,从左到右编码为0 1 0 1依次进行……
生成霍夫曼编码
把每个字幕的二进制编码记录,打出,这就是密码表
然后对原来的文件进行打印,碰到相应的字母打印出相应的密码(二进制啊,汗……)
估计只有拿到密码才能看明白那一串的01!!
如果某一电文出现的字符为D={M,S,T,A,Q, K} , 每个字符出现的频率为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实现哈夫曼编码
只要自己再加个类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和数据结构大虾们帮下忙: 输入一段文字,该程序可以统计出每个字符出现的次数并对字符进行哈夫曼编码
写给你了,请发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;
/**
* 定义了一种接口,要进行编码的最小单元类必需实现些接口
*
*/
interface CombinableT extends ComparableT {
T combinate(T a, T b);
}
/**
*
* the huffman tree Class 哈夫曼树,包括当前节点数据信息,左节点,右节点信息。
*/
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 = "";
/** 是否对最终生成的哈夫曼进行过编码操作 */
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;
}
/**
*
* 重写此方法用于递归合并节点后进行排序操作
*
*/
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();
}
/**
*
* 对最终生成的树进行哈夫曼编码,使每个叶子节点生成01的路径编码
*
*/
private void setHuffmanCoderString() {
HuffmanTreeT left = this.getLeft();
// 如果有左节点则在路径中追加"0"
if (left != null) {
left.huffmanCodeString = this.huffmanCodeString + "0";
left.setHuffmanCoderString();// 递归编码
}
HuffmanTreeT right = this.getRight();
// 如果有右节点则在路径中追加"1"
if (right != null) {
right.huffmanCodeString = this.huffmanCodeString + "1";
right.setHuffmanCoderString();// 递归编码
}
}
public void printHuffmanCoderString() {
// 打印最终生成树的哈夫曼编码前要进行编码操作,
// 且此操作只执行一次,所以用全局标识变量判断
if (!HuffmanTree.isSettedHuffmanCoderString) {
this.setHuffmanCoderString();
HuffmanTree.isSettedHuffmanCoderString = true;// 标识已执行过编码
}
// 如果是叶子节点(即要编码的单元),则打印出编码信息,如果是非叶子结点(中间临时生成的节点),则不打印
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();// 递归打印
}
}
/**
*
* 用类用于生成一个哈夫曼树
*/
class HuffmanTreeFactoryT extends CombinableT {
/** 初始时一个list列表当作要编码的单元类的容器 */
private ListHuffmanTreeT HuffmanTreeCollection;
/**
*
* @param unitClasses
* 待编码的单元类集合
*
*/
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);
}
/**
* 将待编码的哈夫曼集合处理成只含有一个元素的集合,则这最后一个元素 即为最终生成的哈夫曼树
*/
private void generateHuffmanTree() {
while (true) {
if (HuffmanTreeCollection == null
|| HuffmanTreeCollection.size() = 1)
break;
// 处理之前一定要重新排序,这是哈夫曼编码的关键原理
Collections.sort(HuffmanTreeCollection);
HuffmanTreeT huffmanTreeOne = HuffmanTreeCollection.remove(0);
HuffmanTreeT huffmanTreeTwo = HuffmanTreeCollection.remove(0);
HuffmanTreeT huffmanTreeNew = new HuffmanTreeT();
// 将集合中前面两个元素合并成一个元素插到集合中去
// 并将第一个元素和第二个元素分别作为新元素的左,右节点
huffmanTreeNew.setRoot(huffmanTreeOne.getRoot().combinate(
huffmanTreeOne.getRoot(), huffmanTreeTwo.getRoot()));
huffmanTreeNew.setLeft(huffmanTreeOne);
huffmanTreeNew.setRight(huffmanTreeTwo);
HuffmanTreeCollection.add(huffmanTreeNew);
}
}
/**
*
*
*
* @return 生成最终的哈夫曼树
*
*/
public HuffmanTreeT getHuffmanTree() {
generateHuffmanTree();
return this.HuffmanTreeCollection.get(0);
}
}
/**
* 自定义一个用于测试的单元类
*/
class UnitClass implements Serializable, CombinableUnitClass {
/** 出现概率数据 */
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;
}
/**
*
* 重写此方法用于哈夫曼编码时可以合并两个分支点信息
*
*/
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 + "出现了" + counter(str, c) + "次");
l.add(new UnitClass(c));
}
HuffmanTreeFactoryUnitClass factory = new HuffmanTreeFactoryUnitClass(
l);
factory.getHuffmanTree().printHuffmanCoderString();
}
}
文章题目:霍夫曼算法代码java 编程实现霍夫曼编码
文章网址:http://scyanting.com/article/ddcedpo.html