-Unlicensed-演讲稿.ppt

1、Huffman tree,The reason of the question,Improve the efficiency,The idea of the processes,Count the number of characters Construct Huffman tree Compress and save Decompress and read,Algorithm implementation,1.Construct Huffman tree,public class Node long weight; / the weight of the Node int name; / t

2、he name of the Node, store the value of the Node Node lchild, rchild, parent; Node() / Initialization = -1; this.weight = 0; this.lchild = null; this.rchild = null; this.parent = null; / get the left child of the Node public Node getLeftChild() return this.lchild; ,/ get the right child wi

3、th the given Node public Node getRightChild() return this.rchild; / get the parent of the Node public Node getParent() return this.parent; / get the value of the Node public int getValue() return ; / Check out if the Node is a leaf public boolean isLeaf() return (this.lchild = null) ,public

4、 class HuffmanTree final int leafnum = 256; final int hufnum = 2 * leafnum - 1; final long max = 99999999; Node root; long w = new long256; / Store the weight of the Node int nodeNum; / Store the num of the total leaves private Node tree = new Nodehufnum; HuffmanTree(long weight) / Initialization th

5、is.w = weight; this.tree = getTree(); root = treetree.length -1; ,public Node getTree() nodeNum = 0; for (int i = 0; i 256; i+) / if the weight of the bytes is not 0,then creat a tree node if (wi != 0) nodeNum+; treenodeNum - 1 = new Node(); treenodeNum - 1.name = i; treenodeNum - 1.weight = wi; / C

6、reat huffman tree, the same as the codes in the book ,public String getCode() String code = new String256; StringBuffer buf; for (int j = 0; j code.length; j+) codej = ; / Get the code from the Node up to the root int i; Node c, p; for (i = 0; i nodeNum; i+) buf = new StringBuffer(); c = treei; p =

7、treei.parent;,while (p != null) if (p.lchild = c) / if the node is the leafchild of its / parent buf.append(0); else / if the node is the right child of its parent buf.append(1); c = p; p = p.parent; = buf.reverse().toString(); return code; ,2.Count the number of characters Preconditi

8、on complementingclass of Huffman Quote BufferedInputStream,class Reader Private long weigt; private node; private String codes; Reader(String textname) ,import java.io.*; /Read the file and get the huffman tree public class Reader private long weight = new long256; / Cause the numbers are between 0

9、and 255, we use an long array weight to / store the weight of the node private String textName;/ Get the name of the file private Node tree; private String codes;,Reader(String textName) throws IOException this.textName = textName; / Get the content of the file BufferedInputStream input = new Buffer

10、edInputStream( new FileInputStream(textName); int temp; while (temp = input.read() != -1) weighttemp+;/ Count the weight of all the node input.close(); / According to the weights of all the node to / construct the huffman tree HuffmanTree huff = new HuffmanTree(weight); codes = huff.getCode(); tree

11、= huff.getTree(); ,/ Set the name of the file which needs to be read public void setTextName(String textName) this.textName = textName; / Get the name of the file which needs to be read public String getTextName() return textName; / Get the weight of all bytes which are between 0 and 255 public long

12、 getweight() return weight; / Get the huffmantree public Node getHuffmanTree() return tree; / Get the huffmancode public String getHuffmanCode() return codes; ,3.Compression,public class Compress String code = new String256; Node tree; String textName = null; / The name of the file that needs to be

13、compressed String fileName = null; / The name of the compressed file private void creatCompressedFile() throws IOException / Read the file that needs to be compressed,BufferedInputStream input = new BufferedInputStream( new FileInputStream(textName); ObjectOutputStream output = new ObjectOutputStrea

14、m( new FileOutputStream(fileName); / Read the tree of the file output.writeObject(tree); int temp; / store the byte that be read from the file StringBuffer content = new StringBuffer(); / store the content int addLength; / store the length that should be added in the tail,/* According to the code, t

15、ranslate them into the byte */ while (temp = input.read() != -1) content.append(this.codetemp); int length = content.length() 3; for (int i = 0; i length; i+) output.write(B2U(content.substring(0, 8); / write the bytes into the file if (content.length() = 0) addLength = 0; else ,/ Add 0s at the end

16、of the content addLength = 8 - content.length(); for (int i = 0; i addLength; i+) content.append(0); output.write(B2U(content.substring(0, 8); input.close(); output.close(); ,/ Acoording the code, translate them into byte public int B2U(String s) int value = 0; for (int i = 0; i 8; i+) if (s.charAt(

17、i) = 1) value += 0 x1 (7 - i); return value; ,4.Decompression,public class Decompression Node tree = new Node256; String textName = null; Node root; String DecompressTextName; ObjectInputStream input; BufferedOutputStream output;,private void creatDecompressionFile() throws IOException int temp; root = treetree.length - 1; / Get the root Node tempNode = root; / Search from the