哈弗曼树与编码解码

大文件M包含许多字符，它们是'a','b','c','d','e','f','g'中的一个，每个富裕唯一编码

1.使用了优先级队列Heap

2.定义接口PriorityQueue

3。改程序限定在祖父记得256个字符之内，每个字符在ArrayList数组中都有一个对应的位置，例如，’B‘，该字符的信息被存储在索引(int)'B'处，即66.详见代码和附件

code:

package Exercize;

public interface PriorityQueue<E> {

	int size() ;
	boolean isEmpty() ;
	void add(E element) ;
	E getMin() ;
	E removeMin() ;
}


package HUffman;

import Exercize.Heap ;
import Exercize.PriorityQueue; 
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;

public class Huffman {

	public final static int SIZE = 256 ;
	
	protected Entry[] leafEntries ;  //以字符ASC||为索引的数组
	protected PriorityQueue<Entry> pq ;
	
	public Huffman(){
	 
		Entry entry ;
		leafEntries = new Entry[SIZE] ;
		for(int i = 0; i < SIZE; i ++)
		{
			leafEntries[i] = new Entry() ;
			entry = leafEntries[i] ;
			entry.freq = 0 ;
			entry.left = null ;
			entry.right = null ;
			entry.parent = null ;
		}
		pq = new Heap<Entry>() ;
		
	}
	
	public void updateFrequencies(String line){
		Entry entry ;
		for(int j = 0; j < line.length(); j ++)
		{
			entry = leafEntries[(int)(line.charAt(j))] ;
			entry.freq ++ ;
		}
		entry = leafEntries[(int)'\r'] ;  //保证消息原来的行结构在解码过程中保持不变
		entry.freq ++ ;
	}
	
	 
	//首先填充leafEntries对象，然后在此基础上填充优先级队列,按照频率递增的顺序插入
	public void createPQ() throws IOException {
		 
		Entry entry ;		 		 
		for(int i = 0 ; i  < SIZE ; i ++){
			 entry = leafEntries[i] ;
			 if(entry.freq > 0)
				 pq.add(entry) ;
		}
	}
		 
	//频率最低的字符优先删除组成树的节点
	public void createHuffmanTree(){
		Entry left, 
			  right, 
			  sum ;
		while(pq.size() > 1){
			left = pq.removeMin() ;
			left.code = "0" ;
			
			right = pq.removeMin() ;
			right.code = "1" ;
			
			sum = new Entry() ;
			sum.parent = null ;
			sum.freq = left.freq + right.freq ;
			sum.left = left ; 
			sum.right = right ;
			left.parent = sum ;
			right.parent = sum ;
			
			pq.add(sum) ;    //将左右子节点的频率之和成为其父节点，并添加到优先级队列中
		}
	}
	
	//解码
	public void calculateHuffmanCodes()
	{
        	String code;
        	Entry entry;
        	for (int i = 0; i < SIZE; i++)
        	{
            		code = "";
            		entry = leafEntries [i];
            		if (entry.freq > 0)
            		{
                		while (entry.parent != null)
                 		{
                      			code = entry.code + code;   
                      			entry = entry.parent;       
                 		} // while                		
				        leafEntries [i].code = code;
            		} // if
        	} // for
	} // calculateHuffmanCodes

	public String getCodes()
	{
        	Entry entry;

        	String codes = new String();

        	for (int i = 0; i < SIZE; i++)
        	{
            		entry = leafEntries [i];
            		if (entry.freq > 0)
                		codes += (char)i + " " + entry.code + "\n";
        	} // for
        	return codes;
	} // method getCodes

 
    public String getEncodedLine (String line)
    {
        Entry entry;

        String encodedLine = new String();

        for (int j = 0; j < line.length(); j++)
        {
            	entry = leafEntries [(int)(line.charAt (j))];
            	encodedLine += entry.code;
        } // for
        entry = leafEntries [(int)'\r'];
        encodedLine += entry.code;
        return encodedLine;
	} // method getEncodedLine


} // class Huffman


class Entry implements Comparable<Entry> 
{
    	int freq;

    	String code;

    	char id;

    	Entry left,
              right,
              parent;

    	public int compareTo (Entry entry) 
    	{
        	return freq - entry.freq;
    	} // compareTo

} // class Entry


	 
package HUffman;

import java.io.*;

public class HuffmanTester
{

	protected BufferedReader fileReader;
	protected PrintWriter fileWriter;
	protected Huffman huffman;
	protected String inFilePath;

 	public HuffmanTester()
	{
        	huffman = new Huffman();
 	} // default constructor

	public PrintWriter openFiles()
	{
		final String IN_FILE_PROMPT =
          		"\nPlease enter the path for the input file: ";

      		final String OUT_FILE_PROMPT =
          		"\nPlease enter the path for the output file: ";

      		BufferedReader keyboardReader = new BufferedReader(new InputStreamReader (System.in));
                                          	
      		String outFilePath,
                       line;

      		boolean pathsOK = false;

      		while (!pathsOK)
      		{
          		try
          		{
              			System.out.print (IN_FILE_PROMPT);
              			inFilePath = keyboardReader.readLine();
              			fileReader= new BufferedReader(new FileReader (inFilePath));           		  	
              			System.out.print (OUT_FILE_PROMPT);
              			outFilePath = keyboardReader.readLine();
              			fileWriter = new PrintWriter (new FileWriter (outFilePath));
              			pathsOK = true;	
          		} // try
          		catch (IOException e)
          		{
              		System.out.println (e);
          		} // catch
        	} // while !pathOK
		return fileWriter;
	} // method openFiles


	 
	public void createEncoding()
	{
     		String line;

        	try
        	{
            		while (true)
            		{
                		line = fileReader.readLine();
                		if (line == null)
                    			break;
                		huffman.updateFrequencies (line);
            		} // while
            		fileReader.close(); // re-opened in saveEncodedMessage
            		huffman.createPQ();
            		huffman.createHuffmanTree();
            		huffman.calculateHuffmanCodes();
        	} // try
        	catch (IOException e)
        	{
            		System.out.println (e);
        	} // catch IOException
	} // method createEncoding

 
	public void saveEncodedMessage()
	{
        	String line;

        	try
        	{
           			fileWriter.print (huffman.getCodes());
            		fileWriter.println ("**"); // to separate codes from encoded message
            		fileReader = new BufferedReader (new FileReader (inFilePath));

            		while (true)
            		{
                		line = fileReader.readLine();
                		if (line == null)
                    			break;
                		fileWriter.println (huffman.getEncodedLine (line));
            		} // while            	
        	} // try
        	catch (IOException e)
        	{
            		System.out.println (e);
        	} // catch IOException
	} // method saveEncodedMessage

} // class HuffmanTester



package HUffman;
import java.io.*;
public class HuffmanTesterMain {
 
	public static void main(String[] args) {
		PrintWriter writer = null;
	       
  		try
  		{
       		HuffmanTester tester = new HuffmanTester();
       
       		writer = tester.openFiles();
       		tester.createEncoding();
			tester.saveEncodedMessage();
   		} // try
   		finally
   		{
       		writer.close();
		} // finally	


	}

}

 

输入字符的存储结构:

频率

编码

字符

parent

left

right