Java 实现Huffman 编码算法详解编程语言

  
static class Tree { 
private Node root; 
public Node getRoot() { 
return root; 
} 
public void setRoot(Node root) { 
this.root = root; 
} 
} 
static class Node implements Comparable { 
private String chars = ""; 
private int frequence = 0; 
private Node parent; 
private Node leftNode; 
private Node rightNode; 
@Override 
public int compareTo(Node n) { 
return frequence - n.frequence; 
} 
public boolean isLeaf() { 
return chars.length() == 1; 
} 
public boolean isRoot() { 
return parent == null; 
} 
public boolean isLeftChild() { 
return parent != null && this == parent.leftNode; 
} 
public int getFrequence() { 
return frequence; 
} 
public void setFrequence(int frequence) { 
this.frequence = frequence; 
} 
public String getChars() { 
return chars; 
} 
public void setChars(String chars) { 
this.chars = chars; 
} 
public Node getParent() { 
return parent; 
} 
public void setParent(Node parent) { 
this.parent = parent; 
} 
public Node getLeftNode() { 
return leftNode; 
} 
public void setLeftNode(Node leftNode) { 
this.leftNode = leftNode; 
} 
public Node getRightNode() { 
return rightNode; 
} 
public void setRightNode(Node rightNode) { 
this.rightNode = rightNode; 
} 
} 
统计方法实现如下： 
public static Map<Character, Integer> statistics(char[] charArray) { 
Map<Character, Integer> map = new HashMap<Character, Integer>(); 
for (char c : charArray) { 
Character character = new Character(c); 
if (map.containsKey(character)) { 
map.put(character, map.get(character) + 1); 
} else { 
map.put(character, 1); 
} 
} 
return map; 
} 
构建树 
private static Tree buildTree(Map<Character, Integer> statistics, 
List leafs) { 
Character[] keys = statistics.keySet().toArray(new Character[0]); 
PriorityQueue priorityQueue = new PriorityQueue(); 
for (Character character : keys) { 
Node node = new Node(); 
node.chars = character.toString(); 
node.frequence = statistics.get(character); 
priorityQueue.add(node); 
leafs.add(node); 
} 
int size = priorityQueue.size(); 
for (int i = 1; i <= size - 1; i++) { 
Node node1 = priorityQueue.poll(); 
Node node2 = priorityQueue.poll(); 
Node sumNode = new Node(); 
sumNode.chars = node1.chars + node2.chars; 
sumNode.frequence = node1.frequence + node2.frequence; 
sumNode.leftNode = node1; 
sumNode.rightNode = node2; 
node1.parent = sumNode; 
node2.parent = sumNode; 
priorityQueue.add(sumNode); 
} 
Tree tree = new Tree(); 
tree.root = priorityQueue.poll(); 
return tree; 
} 
编码 
public static String encode(String originalStr, 
Map<Character, Integer> statistics) { 
if (originalStr == null || originalStr.equals("")) { 
return ""; 
} 
char[] charArray = originalStr.toCharArray(); 
List leafNodes = new ArrayList(); 
buildTree(statistics, leafNodes); 
Map<Character, String> encodInfo = buildEncodingInfo(leafNodes); 
StringBuffer buffer = new StringBuffer(); 
for (char c : charArray) { 
Character character = new Character(c); 
buffer.append(encodInfo.get(character)); 
} 
return buffer.toString(); 
} 
private static Map<Character, String> buildEncodingInfo(List leafNodes) { 
Map<Character, String> codewords = new HashMap<Character, String>(); 
for (Node leafNode : leafNodes) { 
Character character = new Character(leafNode.getChars().charAt(0)); 
String codeword = ""; 
Node currentNode = leafNode; 
do { 
if (currentNode.isLeftChild()) { 
codeword = "0" + codeword; 
} else { 
codeword = "1" + codeword; 
} 
currentNode = currentNode.parent; 
} while (currentNode.parent != null); 
codewords.put(character, codeword); 
} 
return codewords; 
} 
解码 
public static String decode(String binaryStr, 
Map<Character, Integer> statistics) { 
if (binaryStr == null || binaryStr.equals("")) { 
return ""; 
} 
char[] binaryCharArray = binaryStr.toCharArray(); 
LinkedList binaryList = new LinkedList(); 
int size = binaryCharArray.length; 
for (int i = 0; i < size; i++) { 
binaryList.addLast(new Character(binaryCharArray[i])); 
} 
List leafNodes = new ArrayList(); 
Tree tree = buildTree(statistics, leafNodes); 
StringBuffer buffer = new StringBuffer(); 
while (binaryList.size() > 0) { 
Node node = tree.root; 
do { 
Character c = binaryList.removeFirst(); 
if (c.charValue() == '0') { 
node = node.leftNode; 
} else { 
node = node.rightNode; 
} 
} while (!node.isLeaf()); 
buffer.append(node.chars); 
} 
return buffer.toString(); 
} 
测试以及比较 
public static void main(String[] args) { 
String oriStr = "Huffman codes compress data very effectively: savings of 20% to 90% are typical, " 
+ "depending on the characteristics of the data being compressed. 中华崛起"; 
Map<Character, Integer> statistics = statistics(oriStr.toCharArray()); 
String encodedBinariStr = encode(oriStr, statistics); 
String decodedStr = decode(encodedBinariStr, statistics); 
System.out.println("Original sstring: " + oriStr); 
System.out.println("Huffman encoed binary string: " + encodedBinariStr); 
System.out.println("decoded string from binariy string: " + decodedStr); 
System.out.println("binary string of UTF-8: " 
+ getStringOfByte(oriStr, Charset.forName("UTF-8"))); 
System.out.println("binary string of UTF-16: " 
+ getStringOfByte(oriStr, Charset.forName("UTF-16"))); 
System.out.println("binary string of US-ASCII: " 
+ getStringOfByte(oriStr, Charset.forName("US-ASCII"))); 
System.out.println("binary string of GB2312: " 
+ getStringOfByte(oriStr, Charset.forName("GB2312"))); 
} 
public static String getStringOfByte(String str, Charset charset) { 
if (str == null || str.equals("")) { 
return ""; 
} 
byte[] byteArray = str.getBytes(charset); 
int size = byteArray.length; 
StringBuffer buffer = new StringBuffer(); 
for (int i = 0; i < size; i++) {                        byte temp = byteArray[i];                       buffer.append(getStringOfByte(temp));           }               return buffer.toString();       }       public static String getStringOfByte(byte b) {          StringBuffer buffer = new StringBuffer();               for (int i = 7; i >= 0; i--) { 
byte temp = (byte) ((b >> i) & 0x1); 
buffer.append(String.valueOf(temp)); 
} 
return buffer.toString(); 
}