`

java的huffman实现

 
阅读更多

需求分析

从一个文件中读取数据,统计文件的每个字节出现的频数,根据不同的这些频数构建赫夫曼树并实现编码译码分别保存到新的文件中。编码文件为原文件+“.ext”,译码文件为编码文件+“.txt”

养成良好习惯:每个小功能的实现都需要及时进行测试,第一个功能没写好就不要往下写,不然到时候出了错都没办法找原因。

流程分析

先从文件中初始化数据,用map来保存名值对。Byte对应出现次数。

根据map创建树的节点。

根据节点创建赫夫曼树。

根据赫夫曼树进行编码。

根据编码和源文件内容对其进行编码并保存到文件中。

从已编码的文件中读取数据进行译码并保存到文件中。

最终产生的文件和原文件是一模一样的即算成功。

搭建框架

1、需要创建节点类。

节点类需要以下属性:
int intWeight;//
频数

Byte byteData;// 字节内容

Tree parent;// 父节点

Tree lchild;

Tree rchild;

Int intFlag = -1;// 保存该节点编码,初始化为-1,树根为-1,左子树为0,右子树为1(便于编码)

 

 

构建好了需求,开始写好类

 

public class Tree{
	int weight; // 重复出现次数
	Byte data; // 字节内容-128~127
	Tree parent;
	Tree lchild;
	Tree rchild;
	int flag = -1;// 初始化该点编码为-1,到时候如果被变成左孩子,赋值为0.右孩子赋值为1

	public Tree(Byte data, int weight) {
		this.data = data;
		this.weight = weight;
	}

	public String toString() {
		return data + "\t 权值:" + weight;
	}
}

2、从文件中读取数据,构建HashMap<Byte, Integer> map

 

 

 

首先,我们需要选择合适的输入流,在这里,我们可以用FileInputStreamBufferedInputStream。从文件中读取字节,并统计每个字节的次数并putmap中,如果在map中已经存在,则取出map中该名对应的值,并对其加1.首先需要判断空文件的处理。具体操作如下:

 

int t = bis.read();// 字节
			if (t == -1) {// 空文件的处理
				new FileOutputStream(new File(str + ".ext")).close();
				return null;
			}

while (t != -1) {
				byte b = (byte) t;
				if (map.containsKey(b)) {
					int v = (int) map.get(b);
					v++;
					map.put(b, v);
				} else {
					map.put(b, 1);
				}
				t = bis.read();
			}

return map;

 

 

3、根据map创建节点

在这里,我们为了方便之后建树的时候要找到权值最小的两个节点,所以我们直接用一个排序队列来保存节点。当然,这个排序队列需要我们自己写好排序规则。

先遍历map取出数据,创建Tree对象。再将其加到queueNode里面去。

4、根据节点创建树

由于队列中的Tree都是根据权值进行了排序的,每次取出队列中最前面两个,链接好节点与节点之间的关系。并初始化该节点对应的编码。

Tree tree1 = queueNode.poll();

                            Tree tree2 = queueNode.poll();

                            Tree tree3 = new Tree(null, tree1.weight + tree2.weight);

                            tree3.lchild = tree1;

                            tree3.rchild = tree2;

 

                            tree1.flag = 0;// 标记左边的元素为0,编码时候为0

                            tree2.flag = 1;// 标记右边为1

 

                            tree1.parent = tree3;

                            tree2.parent = tree3;

                            queueNode.add(tree3);

 

5、根据树进行编码

左边为0,右边为1,如果只有一个点,则编码为0。并将每个字节对应的编码信息存到HashMap<Byte, String> mapCode中。

 

如果只有一个节点,直接mapCode.put(root.data, "0");

 

否则,用递归来进行编码。代码如下:

 

public void enCoding(Tree parent, Tree child, String str,
			HashMap<Byte, String> mapCode) {
		// 递归找到叶子节点,字符串加上其flag值(构建树的时候初始化为0和1了)
		if (child != null) {
			if (child.flag != -1) {// 不是根节点
				str += child.flag;
			}
			enCoding(child, child.lchild, str, mapCode);
			enCoding(child, child.rchild, str, mapCode);
		} else {
			// 将字节与编码的对应关系存入mapCode中
			mapCode.put(parent.data, str);
		}
	}

 

 

6、根据编码对原文件进行编码并保存

在这里,我们需要保存编码表到文件,到时候译码可不一定还能找到原文件对其先编码。

所以我们选择ObjectOutputStream。先将mapCode写到文件,之后再写编码后的数据。

代码为:

oos.writeObject(mapCode);

oos.flush();

 

接下来如何编码呢?

先从文件中一个一个字节的读出来,然后再去编码表进行搜索。将搜索到的记录保存到临时存储这些编码的String中间。如果String长度超过了8,就可以将其变成一个字节保存出去了。一边读,一边编码,一边保存。(在这里,和线程中提到的生产消费模型很相似。)到最后,就会发现一个问题,如果我的编码最后没满8位岂不是最后就编不了了?所以,我们最后要进行一次判断,如果我的string长度最后大于0小于8,那么我就在后面补0直到长度为8,并在最后将补0的数目写到文件结尾。

 

经过这些步骤,就保存好了。

 

String st = "";
// 保存文件中每个字节的编码
int t = bis.read();// 字节
while (t != -1) {
	byte b = (byte) t;
	st += mapCode.get(b);
	while (st.length() > 8) {
将string转为byte保存出去
st = st.substring(8);
	}
t = bis.read();
}
int len = st.length();
int count = 0;
if (len > 0) {
	count = 8 - len;// 得到补0个数
将最后这个字节保存到文件中
}
bos.write(count);

 

 

7、从编码文件中读取文件对其译码

如何实现译码呢?最简单的就是和保存编码文件一样,从文件中先读取一段byte,将其转为字符串,然后在编码表中找对应的byte。匹配成功就将其写到文件中。

所以在写译码的方法时,我们需要用到编码文件中的编码表,需要用到需要翻译的字符串,还要用一个数组来保存译出来的byte

我们可以每读一个字节就将其转为8位的string01串),如果string长度超过256(最坏的情况编码长度最大不超过256),我们就对其进行译码,译码得到的字节临时存在一个数组中。然后译码一次完成之后,保存数组中的字节,并清空数组,清除字符串中翻译出来了的字符。继续读数据,如果再超过256,再译码,就这样不断循环。最后翻译完毕。

框架如下:
<!--[if !supportLineBreakNewLine]-->
<!--[endif]-->

 

public String deCoding(HashMap<Byte, String> mapCode, String string,
			ArrayList<Byte> data) {
String str = "";
	HashMap<String, Byte> map = new HashMap<String, Byte>();
//先得到编码与字节的名值对
	Set<Byte> keys = mapCode.keySet();
	for (Byte bt : keys) {
		map.put(mapCode.get(bt), bt);
	}
for (int i = 0; i < string.length(); i++) {
		str += string.charAt(i) - 48;
		// System.out.println(str);
		if (map.containsKey(str)) {
得到对应字节保存到数组
字符串剪掉这一段
i = -1重新开始寻找
}
}
return string;
}

 

 

8、到这里基本功能都已经实现了,现在需要一个文件选择器,选择文件对其编码译码。

 

用一个窗口,在上面增加文件选择器。选择文件进行操作。

 

测试

 

经过多次测试,两者都对同一个不同大小文件测试,都是建树版效率更高,尤其是编码平均长了的时候。

 

对于同一个1899125字节的文件,用编码表压缩297454字节,用建树版压缩298324字节,大了1kb左右

 

对于一个144,262,144 字节的压缩文件再次压缩,编码表版增肥4755字节,建树版增肥14634字节,多占用近10kb

 



 

 

 

总结

在译码的时候,不仅可以根据编码表进行译码,也可以根据树进行译码(这个也实现了)。

经过测试,建树译码效率高很多,但是存储的是排序的队列,所以占用空间大一点。

程序中没超过8为就写数据,没超过256就开始译码有效解决了打文件的问题。但是如果有一个文件,某个字节出现的次数已经超过了int的表示范围,就会有问题了。

 

在窗口中,加入文本框,输入一串文字,在进行编码的时候,有效的利用这串文字进行编码就可以作为一个加密软件了。毕竟赫夫曼的压缩效果一般都不明显。

 

 

 String与byte互相转换参考:http://479001499.iteye.com/admin/blogs/2094257

  • 大小: 19.8 KB
  • 大小: 19.9 KB
分享到:
评论

相关推荐

    Huffman编码的java实现

    在Java环境下实现Huffman编码,我们需要理解以下几个关键概念: 1. **字符频率统计**:首先,我们需要统计输入文本中各个字符的出现频率。这个过程可以通过遍历文本并使用HashMap或数组来存储每个字符及其对应的...

    huffman编码java实现

    在压缩包中,`huffman`可能是源代码文件夹,包含了实现哈夫曼编码的Java源文件,如`HuffmanTree.java`(定义哈夫曼树的类)、`HuffmanCoding.java`(处理编码和解码的类)等。这些源代码提供了详细的实现细节,可以...

    Huffman压缩解压java实现

    在Java中实现Huffman编码,需要理解其基本原理并运用数据结构和算法。 一、Huffman编码原理 1. 频率统计:首先,对输入文本中的每个字符出现的次数进行统计,得到一个字符频率表。 2. 构建Huffman树:通过一个...

    huffman:Java Huffman实现

    通过理解以上知识点,并结合提供的“huffman-master”压缩包中的代码,你可以深入学习和实践Java如何实现霍夫曼编码算法。这个压缩包可能包含了示例代码、测试用例和相关的文档,对于学习和理解霍夫曼编码的实现过程...

    Huffman编码的JAVA实现算法(源代码)

    而`HuffmanTree`可能是Java实现Huffman编码的源代码文件,其中可能包括了字符频率计算、最小堆实现、Huffman树构建、编码表生成、编码与解码等关键功能。 总之,Huffman编码是数据压缩领域的一个重要技术,它通过...

    基于Huffman编码压缩软件(java实现)

    本篇文章将深入探讨基于Huffman编码的Java实现,分析其工作原理并解析提供的Java源代码。 Huffman编码的核心思想是通过建立一个带权路径长度最短的二叉树(也称为Huffman树),为每个字符分配唯一的二进制码,使得...

    java实现huffman算法

    java实现huffman算法 ~可以在控制台输入字符串编码~

    Java编写的Huffman实现的文本压缩和解压

    Java编写的Huffman实现的文本压缩和解压。可以压缩小于2MB的,大了也可以只是时间很长。解压缩实现的不好只能解压小于100KB的。欢迎大家下载。还有只能对文本文件进行操作。由于huffman所发本身就有问题所以如果压缩...

    Huffman 压缩解压缩 Java实现

    在Java中实现Huffman编码,主要涉及以下几个关键步骤: 1. **统计字符频率**:首先,我们需要读取输入的ASCII文档,统计每个字符出现的次数。这通常通过创建一个HashMap来存储字符及其对应的频率。 2. **构建...

    HuffmanCode_java.rar_HuffmanCode_java_huffman java_huffman 文本_hu

    《哈夫曼编码在Java中的实现与应用》 哈夫曼编码(Huffman Coding)是一种高效的数据压缩算法,尤其适用于文本压缩。它基于字符出现频率,构建最优的二叉树结构,使得高频字符的编码较短,低频字符的编码较长,从而...

    java实现huffman编码解码

    本程序利用Java实现以下功能: 1、读取一行或多行数据,统计出现的所有字母的出现次数 2、构造huffman树 3、生成出现字母的编码表 4、对输入的数据进行编码输出 5、输入编码结果,对编码结果进行解码,得到原来的...

    huffman编码和反编码的java实现

    哈夫曼编码(Huffman Coding)是一种数据压缩算法,它基于字符出现频率构建最优的前缀树(也称为哈夫曼树),进而实现对原始数据的高效编码和解码。在Java中实现哈夫曼编码和反编码主要包括以下几个步骤: 1. **...

    JDBC与Java数据库程序设计_0.rar_JAVA数据库_java huffman_java 数据库_jdbc_数据库程序

    在Java中,我们可以使用BitSet类或者自定义的数据结构实现Huffman编码。这种编码方法主要用于文本数据的压缩,通过构建一棵Huffman树,对出现频率高的字符赋予较短的二进制码,从而达到压缩的目的。 至于"数据库...

    HuffmanCode_huffman编码java_huffman_

    3. `HuffmanTree.java`:定义`HuffmanTree`类,包括哈夫曼树的构建、编码和解码方法。 4. `main`类(如`Main.java`):程序入口,读取输入数据,调用`HuffmanTree`类的方法进行编码和解码。 在实际应用中,数据通常...

    HuffmanCoding-Java

    在这个名为"HuffmanCoding-Java"的项目中,开发者使用Java语言实现了哈夫曼编码和解码的功能,虽然提到可以使用游程编码(Run-Length Encoding)进行后续处理,但目前代码中并未包含这部分内容。 哈夫曼编码的基本...

    Huffman编码实现(Eclipse环境,Java语言)

    下面我们将深入探讨Huffman编码的原理以及如何用Java进行实现。 首先,我们需要理解Huffman树的构建过程。Huffman树是一种特殊的二叉树,也称为最小带权路径长度树(Minimum Weighted Path Length Tree)。它的构建...

    谈如何用Java语言实现Huffman编码.pdf

    "谈如何用Java语言实现Huffman编码" Huffman编码是一种高效的变长编码技术,广泛应用于文本、图像、视频压缩和通信等领域。Java语言作为一种流行的面向对象的程序设计语言,可以用来实现Huffman编码。下面,我们将...

    Huffman文件加密解密Java实现

    在这个“Huffman文件加密解密Java实现”项目中,开发者提供了一个完整的Java程序,能够实现对文本文件进行Huffman编码和解码。以下是该项目可能涉及的关键知识点: 1. **Huffman树的构建**:首先,我们需要统计输入...

    Huffman的Java实现

    在Java环境下实现哈夫曼编码,通常会涉及以下几个关键步骤: 1. **统计字符频率**:首先,我们需要统计输入数据中各个字符出现的频率。这可以通过遍历整个输入字符串或二进制流完成,用哈希表记录每个字符及其对应...

Global site tag (gtag.js) - Google Analytics