JAVA代码实现
Huffman
package cn.fyfye.algorithm.huffman;
import java.util.*;
public class Huffman implements Comparable<Huffman> {
private Integer weight;
private Character name;
private Integer val;
private Huffman lChildren;
private Huffman rChildren;
public Huffman() {
}
public Huffman(Integer weight, Character name, Integer val, Huffman lChildren, Huffman rChildren) {
this.weight = weight;
this.name = name;
this.val = val;
this.lChildren = lChildren;
this.rChildren = rChildren;
}
/**
* 创建节点数
* @param str 需要编码数据
* @return
*/
public static Huffman createHuffmanRootNode(StringBuffer str) {
Huffman root = null;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < str.length(); i++) {
if (map.containsKey(str.charAt(i))) {
Integer val = map.get(str.charAt(i));
map.put(str.charAt(i), val + 1);
} else {
map.put(str.charAt(i), 1);
}
}
LinkedList<Huffman> listNode = new LinkedList<>();
for (Map.Entry<Character, Integer> en : map.entrySet()) {
Huffman huffman = new Huffman(en.getValue(), en.getKey(), 0, null, null);
listNode.add(huffman);
}
Collections.sort(listNode);
root = binaryTree(listNode);
return root;
}
private static Huffman binaryTree(LinkedList<Huffman> listNode) {
Huffman root = null;
while (listNode.size()>0){
if(listNode.size()==1){
Huffman left = listNode.removeFirst();
left.setVal(0);
return new Huffman(left.getWeight(),null,0,left,null);
}
Huffman left = listNode.removeFirst();
Huffman right = listNode.removeFirst();
left.setVal(0);
right.setVal(1);
if(listNode.size()==0){
root = new Huffman(left.getWeight()+right.getWeight(),null,0,left,right);
}else{
Huffman huffman = new Huffman(left.getWeight() + right.getWeight(), null, 0, left, right);
listNode.add(huffman);
Collections.sort(listNode);
}
}
return root;
}
/**
* 进行编码
* @param root 数
* @param code 存储编码
* @return
*/
public static String encode(Huffman root,HashMap<Character,String> code){
StringBuffer sb = new StringBuffer();
findNodeVal(root,code,new StringBuffer());
for(Map.Entry<Character, String> set :code.entrySet()){
sb.append(set.getValue());
}
return sb.toString();
}
private static void findNodeVal(Huffman root,HashMap<Character,String> code,StringBuffer s){
if(null != root){
if(null == root.getLChildren() && null == root.getRChildren()){
s.append(root.getVal());
code.put(root.getName(),s.substring(1));
s.deleteCharAt(s.length()-1);
}
s.append(root.getVal());
if(null != root.getLChildren()){
findNodeVal(root.getLChildren(),code,s);
}
if(null != root.getRChildren()){
findNodeVal(root.getRChildren(),code,s);
}
s.deleteCharAt(s.length()-1);
}
}
@Override
public int compareTo(Huffman o) {
return this.getWeight()-o.getWeight();
}
}
执行程序
package cn.fyfye.algorithm.huffman;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public class HuffmanTest {
public static void main(String[] args) {
StringBuffer str = new StringBuffer("dsfdskxclvcxvzxxzcasdwfmvvddfdfdfdfdfoibofibfpdob");
HashMap<Character,String> code = new HashMap<>();
Huffman rootNode = Huffman.createHuffmanRootNode(str);
System.out.println(rootNode);
String encode = Huffman.encode(rootNode, code);
System.out.println(encode);
System.out.println(code);
}
}
执行截图
执行.png
Huffman(weight=49, name=null, val=0, lChildren=Huffman(weight=19, name=null, val=0, lChildren=Huffman(weight=9, name=f, val=0, lChildren=null, rChildren=null), rChildren=Huffman(weight=10, name=d, val=1, lChildren=null, rChildren=null)), rChildren=Huffman(weight=30, name=null, val=1, lChildren=Huffman(weight=13, name=null, val=0, lChildren=Huffman(weight=6, name=null, val=0, lChildren=Huffman(weight=3, name=c, val=0, lChildren=null, rChildren=null), rChildren=Huffman(weight=3, name=o, val=1, lChildren=null, rChildren=null)), rChildren=Huffman(weight=7, name=null, val=1, lChildren=Huffman(weight=3, name=s, val=0, lChildren=null, rChildren=null), rChildren=Huffman(weight=4, name=null, val=1, lChildren=Huffman(weight=2, name=null, val=0, lChildren=Huffman(weight=1, name=a, val=0, lChildren=null, rChildren=null), rChildren=Huffman(weight=1, name=k, val=1, lChildren=null, rChildren=null)), rChildren=Huffman(weight=2, name=i, val=1, lChildren=null, rChildren=null)))), rChildren=Huffman(weight=17, name=null, val=1, lChildren=Huffman(weight=8, name=null, val=0, lChildren=Huffman(weight=4, name=null, val=0, lChildren=Huffman(weight=2, name=null, val=0, lChildren=Huffman(weight=1, name=p, val=0, lChildren=null, rChildren=null), rChildren=Huffman(weight=1, name=w, val=1, lChildren=null, rChildren=null)), rChildren=Huffman(weight=2, name=null, val=1, lChildren=Huffman(weight=1, name=l, val=0, lChildren=null, rChildren=null), rChildren=Huffman(weight=1, name=m, val=1, lChildren=null, rChildren=null))), rChildren=Huffman(weight=4, name=v, val=1, lChildren=null, rChildren=null)), rChildren=Huffman(weight=9, name=null, val=1, lChildren=Huffman(weight=4, name=x, val=0, lChildren=null, rChildren=null), rChildren=Huffman(weight=5, name=null, val=1, lChildren=Huffman(weight=2, name=z, val=0, lChildren=null, rChildren=null), rChildren=Huffman(weight=3, name=b, val=1, lChildren=null, rChildren=null))))))
101100111111000010010111101101110010110011100111000010101101110001111011110
{a=101100, b=11111, c=1000, d=01, f=00, i=10111, k=101101, l=110010, m=110011, o=1001, p=110000, s=1010, v=1101, w=110001, x=1110, z=11110}
注:代码仅供参考
作者QQ：420318184
邮箱:fy@0fy0.com
网友评论