JAVA技巧：使用哈弗曼编码实现压缩软件

会计考友 · 发表于 2012-8-4 12:28:23

使用哈弗曼编码实现压缩软件
1.什么是哈夫曼树？
哈夫曼树是一种最优二叉树，它的最利益表此刻它的的带权路径长度最小。（结点的带权路径长度为：结点的路径长度乘以结点的权值，树的带权路径长度为所有叶子结点带权路径长度之和）
2.什么是哈弗曼编码？
从哈弗曼树的根结点起头，按照左子树分配代码“0”，右子树分配代码“1”的轨则，直到叶子结点为止，每个叶子结点的哈弗曼编码就是纲要结点起头，一向到该叶子结点为止，把途中经由的代码按挨次串起来就OK了。
3.什么是哈弗曼压缩？
Huffman（哈夫曼）算法在上世纪五十年月初提出来了，它是一种无损压缩体例，在压缩过程中不会丢失踪信息熵，而且可以证实 Huffman 算法在无损压缩算法中是最优的。 Huffman 道榔撇，实现起来也不坚苦，在此刻的主流压缩软件获得了普遍的应用。对应用轨范、主要资料等绝对不许可信息丢失踪的压缩场所， Huffman 算法长短常好的选择。
哈夫曼压缩，一般用来压缩文本和轨范文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。是以，在文件中呈现频率高的符号，使用短的位序列，而那些很少呈现的符号，则用较长的位序列。
有了以上的根基概念，我们就可以脱手实现哈弗曼压缩软件了！
4.哈弗曼压缩软件的实现：
在文件中，所有的数据都是以字节的形式存在的，一个字节是8位，所以所有可能呈现的字节在0——256之间（不搜罗256），所以，第一步要做的工作就是，把文件所有的字节的呈现频率统计出来，并用频率做为权值生成一棵哈弗曼树：
Java代码
int［］ ByteCount = new int［256］;//字节频率统计
InputStream fis = new FileInputStream（pathName_former）;
InputStream bis = new BufferedInputStream（fis）;//建树文件输入流
while（bis.available（）》0）{
int tmp = bis.read（）;
ByteCount［tmp］++;
}//统计频率
//机关哈弗曼树
hfmTree hfm = new hfmTree（ByteCount）;
Java代码
public hfmTree（int［］ rank）{//按照频率机关哈弗曼树
//把频率不为零的字节插手节点优先级队列
PriorityQueue nodes = new java.util.PriorityQueue（）;
for（int i=0;i
if（rank［i］！=0）{
nodes.add（new hfmNode（rank［i］，i））;
}
}
//机关哈弗曼树
while（nodes.size（）！=1）{
hfmNode node_1 = nodes.poll（）;//1
hfmNode node_2 = nodes.poll（）;//2
hfmNode addNode = new hfmNode（node_1.getRank（）+node_2.getRank（），0）;
addNode.setLeft（node_1）;
addNode.setRight（node_2）;
nodes.add（addNode）;

}

会计考友 · 发表于 2012-8-4 12:28:24

</p>

root = nodes.poll（）;
}//机关函数（correct）
接下来，要做的就是获得0——256之间每个字节所对应的哈弗曼编码，用一个String［］ Code = new Code［256］保留下来Java代码//获得编码
private void getStrByte（hfmNode node，String s）{
if（node.getLeft（）==null&&node.getRight（）==null）{
Code［node.getData（）］ = s;//获得编码字符串
}
if（node.getLeft（）！=null）{
getStrByte（node.getLeft（），s+“0”）;
}//左零 if（node.getRight（）！=null）{
getStrByte（node.getRight（），s+“1”）;
}//右1
}
然后就是把每个字节的编码长度打入文件：Java代码//先将0-255的编码长度打到文件里
for（int i=0;i
if（Code［i］==null||Code［i］==“”）{
Code［i］ = “”;
bos.write（0）;
}else{
bos.write（Code［i］.length（））;
}
}
接下来就是，将每个字节的编码打入文件（这里需要吧8个长度的01串转换成一个byte打入文件）：Java代码//把每个字节的编码表打到文件里
int i = 0;//第i个字节
int count = 0;//满8打一，计数器
String writeCode = “”;//写入的8位编码
String allCode = “”;//所有待写入的编码
String inCode = “”;
while（i《256||count》=8）{
if（count》=8）{//满8
writeCode = allCode.substring（0，8）;//前8位
count-=8;
allCode = allCode.substring（8）;
bos.write（changeString（writeCode））;//写入一个字节
}else{
count+=Code［i］.length（）;
allCode+=Code［i］;
inCode+=Code［i］;
i++;//严重错误发生地
}
}
//如不美观不满8位的
if（allCode.length（）》0）{
int len = 8-allCode.length（）;//补零
for（int j=0;j
allCode+=“0”;

}

会计考友 · 发表于 2012-8-4 12:28:25

</p>inCode+=allCode;
bos.write（changeString（allCode））;
}
最后就是把文件中的所有字节按照这种哈弗曼的编码体例保留到文件中，过程近似于上一步（在最后打入末尾补入的0的个数，主若是为了便利解压缩）：Java代码//编码表输出完毕，将文件中的字节按照这种编码体例压缩
InputStream ins = new FileInputStream（pathName_former）;
InputStream buf = new BufferedInputStream（ins）;//建树输入流
count = 0;
writeCode = “”;
allCode = “”;

while（buf.available（）》0||count》=8）{
if（count》=8）{//满8
writeCode = allCode.substring（0，8）;//前8位
count-=8;
allCode = allCode.substring（8）;
bos.write（changeString（writeCode））;//写入一个字节
}else{
int data = http://www.examw.com/java/zhuangye/157582/buf.read（）;
count+=Code［data］.length（）;
allCode+=Code［data］;
}
}
//如不美观不满8位的
if（allCode.length（）》0）{
int len = 8-allCode.length（）;//补零
for（int j=0;j
allCode+=“0”;
}
bos.write（changeString（allCode））;
bos.write（len）;//补入了几个0
}else{
bos.write（0）;//补入了0个0
}
到这里，整个压缩过程根基完成了，解压缩就是压缩的逆过程，在此不再赘述，所有的操作都保留在附上源代码中。

		自动登录	找回密码
密码			立即注册

[其他] JAVA技巧：使用哈弗曼编码实现压缩软件

JAVA技巧：使用哈弗曼编码实现压缩软件

JAVA技巧：使用哈弗曼编码实现压缩软件