大文件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 |
分享到:
相关推荐
在C语言下实现哈弗曼树的创建并进行哈弗曼编码,同时输出哈弗曼编码。
本程序主要实现了构造哈弗曼树 统计字符频率 编码 解码
这是用C++编写的哈弗曼树的解码与编码,课程设计。自己做的,很完善,希望大家会喜欢。
用C语言实现的哈弗曼树的解码以及编码,读入文件编码后保存为另外一个文件。
把最小的两个概率相加合并成新的概率,与剩余的概率组成新的概率集合; 对新的概率集合重新排序,再次把其中最小的两个概率相加,组成新的概率集合。如此重复进行,直到最后两个概率的和为1; 分配码字:码字分配...
该程序为数据结构上机内容,希望对数据结构在学者能够有所帮助。
用哈弗曼树对文件进行编码和译码 哈弗曼 数据结构 编码 译码 哈弗曼 数据结构 编码 译码
visual studio C语言实现哈弗曼树的创建,编码,解码
哈夫曼树的编码与解码 兼有菜单功能 能将编码表和哈夫曼树正确展示出来
译码过程是根据构建的Huffman树和相应的Huffman编码,从H树的根出发,逐个读取Huffman编码,若当前二进制码=‘0’,则走左子树,否则走右子树,一旦到达H树的叶结点,便译出相应叶结点中的字符,重复上述过程直到...
c++数据结构中的哈夫曼树技术,编码解码的核心内容,数据传输的基础。
哈弗曼编解码(C++),动态建立哈弗曼树,逆向求得编码…………………………………………
哈弗曼树实现 Huffman实现 哈夫曼实现 c++实现 使用方法 getCode:一个map, int> 的对象,该对象表示对ascii文件的统计数据,一个map, pair, int> > 的对象,该对象是编码后各个字符的对应的编码以及该编码的长度 ...
1.构造哈夫曼树及哈夫曼编码:从终端读入字符集大小n、n个字符以及n个对应的权值,建立哈夫曼树;利用已经建好的哈夫曼树求每个叶结点的哈夫曼编码,并保存。 2.编码:利用已构造的哈夫曼编码对“明文”文件中的...
计算机编程 数据结构 哈弗曼树代码 #include #include int n,m; const int infinity=32767; struct chtype { char ch; int k; }; struct node { int weight; int plink,llink,rlink; };
1. 将提供的字符串(自定义字符串)进行排序,获取各个字符的权重; 2. 将字符及对应的权重放入树节点(node)...6. 利用创建的哈夫曼树得到编码; 用递归得到叶子节点,由叶子节点追溯到根节点,得到编码后反转顺序;
哈弗曼树的构造与编码,对txt文件内的文件进行编码、解码
包括哈弗曼的编码与解码,还有哈夫曼树的输出,注释详细,很容易看懂。
课程设计时做的哈弗曼编码。可以对小型的TXT文件进行编码和解码。希望大家支持。