JAVA学习—huffman—2021-06-17
1.由给定的 n 个权值 {w0， w1， w2， …， wn-1}，构造具有 n 棵扩充二叉树的森林 F = { T0， T1， T2， …， Tn-1 }，其中每棵扩充二叉树 TI 只有一 个带权值 wi 的根结点， 其左、右子树均为空。
2.重复以下步骤， 直到 F 中仅剩下一棵树为止：
① 在 F 中选取两棵根结点的权值最小的扩充二叉树，做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
② 在 F 中删去这两棵二叉树。
③ 把新的二叉树加入 F。
package datastructure.tree;import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;
import java.util.stream.Collectors;/*** Huffman tree, encoding, and decoding. For simplicity, only ASCII characters* are supported.* * @author hengyuzuo.*/
public class Huffman {
/*** An inner class for Huffman nodes.*/class HuffmanNode {
/*** The char. Only valid for leaf nodes.*/char character;/*** Weight. It can also be double.*/int weight;/*** The left child.*/HuffmanNode leftChild;/*** The right child.*/HuffmanNode rightChild;/*** The parent. It helps constructing the Huffman code of each character.*/HuffmanNode parent;/********************* * The first constructor******************* */public HuffmanNode(char paraCharacter, int paraWeight, HuffmanNode paraLeftChild,HuffmanNode paraRightChild, HuffmanNode paraParent) {
character = paraCharacter;weight = paraWeight;leftChild = paraLeftChild;rightChild = paraRightChild;parent = paraParent;}// Of HuffmanNode/********************* * To string.******************* */public String toString() {
String resultString = "(" + character + ", " + weight + ")";return resultString;}// Of toString}// Of class HuffmanNode/*** The number of characters. 256 for ASCII.*/public static final int NUM_CHARS = 256;/*** The input text. It is stored in a string for simplicity.*/String inputText;/*** The length of the alphabet, also the number of leaves.*/int alphabetLength;/*** The alphabet.*/char[] alphabet;/*** The count of chars. The length is 2 * alphabetLength - 1 to include* non-leaf nodes.*/int[] charCounts;/*** The mapping of chars to the indices in the alphabet.*/int[] charMapping;/*** Codes for each char in the alphabet. It should have the same length as* alphabet.*/String[] huffmanCodes;/*** All nodes. The last node is the root.*/HuffmanNode[] nodes;/************************ The first constructor.* * @param paraFilename* The text filename.**********************/public Huffman(String paraFilename) {
charMapping = new int[NUM_CHARS];readText(paraFilename);}// Of the first constructor/************************ Read text.* * @param paraFilename* The text filename.**********************/public void readText(String paraFilename) {
try {
inputText = Files.newBufferedReader(Paths.get(paraFilename), StandardCharsets.UTF_8).lines().collect(Collectors.joining("\n"));} catch (Exception ee) {
System.out.println(ee);System.exit(0);} // Of trySystem.out.println("The text is:\r\n" + inputText);}// Of readText/************************ Construct the alphabet. The results are stored in the member variables * charMapping and alphabet.**********************/public void constructAlphabet() {
// Initialize.Arrays.fill(charMapping, -1);// The count for each char. At most NUM_CHARS chars.int[] tempCharCounts = new int[NUM_CHARS];// The index of the char in the ASCII charset.int tempCharIndex;// Step 1. Scan the string to obtain the counts.char tempChar;for (int i = 0; i < inputText.length(); i++) {
tempChar = inputText.charAt(i);tempCharIndex = (int) tempChar;System.out.print("" + tempCharIndex + " ");tempCharCounts[tempCharIndex]++;} // Of for i// Step 2. Scan to determine the size of the alphabet.alphabetLength = 0;for (int i = 0; i < 255; i++) {
if (tempCharCounts[i] > 0) {
alphabetLength++;} // Of if} // Of for i// Step 3. Compress to the alphabetalphabet = new char[alphabetLength];charCounts = new int[2 * alphabetLength - 1];int tempCounter = 0;for (int i = 0; i < NUM_CHARS; i++) {
if (tempCharCounts[i] > 0) {
alphabet[tempCounter] = (char) i;charCounts[tempCounter] = tempCharCounts[i];charMapping[i] = tempCounter;tempCounter++;} // Of if} // Of for iSystem.out.println("The alphabet is: " + Arrays.toString(alphabet));System.out.println("Their counts are: " + Arrays.toString(charCounts));System.out.println("The char mappings are: " + Arrays.toString(charMapping));}// Of constructAlphabet/************************ Construct the tree.**********************/public void constructTree() {
// Step 1. Allocate space.nodes = new HuffmanNode[alphabetLength * 2 - 1];boolean[] tempProcessed = new boolean[alphabetLength * 2 - 1];// Step 2. Initialize leaves.for (int i = 0; i < alphabetLength; i++) {
nodes[i] = new HuffmanNode(alphabet[i], charCounts[i], null, null, null);} // Of for i// Step 3. Construct the tree.int tempLeft, tempRight, tempMinimal;for (int i = alphabetLength; i < 2 * alphabetLength - 1; i++) {
// Step 3.1 Select the first minimal as the left child.tempLeft = -1;tempMinimal = Integer.MAX_VALUE;for (int j = 0; j < i; j++) {
if (tempProcessed[j]) {
continue;} // Of ifif (tempMinimal > charCounts[j]) {
tempMinimal = charCounts[j];tempLeft = j;} // Of if} // Of for jtempProcessed[tempLeft] = true;// Step 3.2 Select the second minimal as the right child.tempRight = -1;tempMinimal = Integer.MAX_VALUE;for (int j = 0; j < i; j++) {
if (tempProcessed[j]) {
continue;} // Of ifif (tempMinimal > charCounts[j]) {
tempMinimal = charCounts[j];tempRight = j;} // Of if} // Of for jtempProcessed[tempRight] = true;System.out.println("Selecting " + tempLeft + " and " + tempRight);// Step 3.3 Construct the new node.charCounts[i] = charCounts[tempLeft] + charCounts[tempRight];nodes[i] = new HuffmanNode('*', charCounts[i], nodes[tempLeft], nodes[tempRight], null);// Step 3.4 Link with children.nodes[tempLeft].parent = nodes[i];nodes[tempRight].parent = nodes[i];System.out.println("The children of " + i + " are " + tempLeft + " and " + tempRight);} // Of for i}// Of constructTree/************************ Get the root of the binary tree.* * @return The root.**********************/public HuffmanNode getRoot() {
return nodes[nodes.length - 1];}// Of getRoot/************************ Pre-order visit.**********************/public void preOrderVisit(HuffmanNode paraNode) {
System.out.print("(" + paraNode.character + ", " + paraNode.weight + ") ");if (paraNode.leftChild != null) {
preOrderVisit(paraNode.leftChild);} // Of ifif (paraNode.rightChild != null) {
preOrderVisit(paraNode.rightChild);} // Of if}// Of preOrderVisit/************************ Generate codes for each character in the alphabet.**********************/public void generateCodes() {
huffmanCodes = new String[alphabetLength];HuffmanNode tempNode;for (int i = 0; i < alphabetLength; i++) {
tempNode = nodes[i];// Use tempCharCode instead of tempCode such that it is unlike// tempNode.// This is an advantage of long names.String tempCharCode = "";while (tempNode.parent != null) {
if (tempNode == tempNode.parent.leftChild) {
tempCharCode = "0" + tempCharCode;} else {
tempCharCode = "1" + tempCharCode;} // Of iftempNode = tempNode.parent;} // Of whilehuffmanCodes[i] = tempCharCode;System.out.println("The code of " + alphabet[i] + " is " + tempCharCode);} // Of for i}// Of generateCodes/************************ Coding the given string.* * @param paraString* The given string.**********************/public String coding(String paraString) {
String resultCodeString = "";int tempIndex;for (int i = 0; i < paraString.length(); i++) {
// From the original char to the location in the alphabet.tempIndex = charMapping[(int) paraString.charAt(i)];// From the location in the alphabet to the code.resultCodeString += huffmanCodes[tempIndex];} // Of for ireturn resultCodeString;}// Of coding/************************ Coding the given string.* * @param paraString* The given string.**********************/public String decoding(String paraString) {
String resultCodeString = "";HuffmanNode tempNode = getRoot();for (int i = 0; i < paraString.length(); i++) {
if (paraString.charAt(i) == '0') {
tempNode = tempNode.leftChild;System.out.println(tempNode);} else {
tempNode = tempNode.rightChild;System.out.println(tempNode);} // Of ifif (tempNode.leftChild == null) {
System.out.println("Decode one:" + tempNode);// Decode one char.resultCodeString += tempNode.character;// Return to the root.tempNode = getRoot();} // Of if} // Of for ireturn resultCodeString;}// Of decoding/************************ The entrance of the program.* * @param args* Not used now.**********************/public static void main(String args[]) {
Huffman tempHuffman = new Huffman("D:/minfan/temp/huffmantext-small.txt");tempHuffman.constructAlphabet();tempHuffman.constructTree();HuffmanNode tempRoot = tempHuffman.getRoot();System.out.println("The root is: " + tempRoot);System.out.println("Preorder visit:");tempHuffman.preOrderVisit(tempHuffman.getRoot());tempHuffman.generateCodes();String tempCoded = tempHuffman.coding("abcdb");System.out.println("Coded: " + tempCoded);String tempDecoded = tempHuffman.decoding(tempCoded);System.out.println("Decoded: " + tempDecoded);}// Of main}// Of class Huffman