Java实现哈夫曼压缩与解压缩的方法
哈夫曼编码是一种有效的无损压缩算法，常用于压缩文本文件等数据。本文将详细介绍如何使用Java实现哈夫曼压缩与解压缩的方法。
哈夫曼压缩
1. 构建哈夫曼树
首先需要构建一个哈夫曼树，该树的每个叶子节点都代表一个字符，并且每个叶子节点的编码都是唯一的。构建哈夫曼树的过程如下：
- 统计给定文本中每个字符出现的频率。
- 将字符频率作为权值构建一棵小根堆（优先队列）。
- 从堆中取出两个权值最小的节点，并将它们合并为一棵树，并将根节点的权值设置为两个子节点的权值之和。
- 将新生成的树作为一个节点重新加入堆中。
- 重复以上步骤，直到堆里只剩下一个节点，即树的根节点。
2. 获取字符编码
在构建哈夫曼树之后，需要根据该树计算出每个叶子节点的编码。对于树中的每个节点，左子节点的编码是当前节点的编码加上字符0，右子节点的编码是当前节点的编码加上字符1。可以使用深度优先遍历的方式，递归地计算出所有叶子节点的编码。
3. 压缩数据
获取字符编码之后，可以根据编码将数据进行压缩。将每个字符替换成它的编码，最终得到一个由0和1组成的二进制字符串。由于Java中没有二进制字符串类型，可以使用StringBuilder类来实现。
以下是具体的Java代码示例：
import java.util.*;
public class HuffmanCompressor {
private static class Node implements Comparable<Node> {
public int value;
public char ch;
public Node left;
public Node right;
public Node(int value, char ch) {
this.value = value;
this.ch = ch;
}
public Node(int value) {
this.value = value;
}
public boolean isLeaf() {
return left == null && right == null;
}
@Override
public int compareTo(Node other) {
return Integer.compare(value, other.value);
}
}
public static String compress(String data) {
int[] freqTable = new int[256];
for (int i = 0; i < data.length(); i++) {
freqTable[data.charAt(i)]++;
}
PriorityQueue<Node> pqueue = new PriorityQueue<>();
for (int i = 0; i < freqTable.length; i++) {
if (freqTable[i] > 0) {
pqueue.offer(new Node(freqTable[i], (char) i));
}
}
while(pqueue.size() > 1) {
Node left = pqueue.poll();
Node right = pqueue.poll();
Node parent = new Node(left.value + right.value);
parent.left = left;
parent.right = right;
pqueue.offer(parent);
}
Node root = pqueue.poll();
Map<Character, String> codeTable = new HashMap<>();
getCodeTable(root, "", codeTable);
StringBuilder encodedData = new StringBuilder();
for (int i = 0; i < data.length(); i++) {
encodedData.append(codeTable.get(data.charAt(i)));
}
return encodedData.toString();
}
private static void getCodeTable(Node node, String code, Map<Character, String> codeTable) {
if (node == null) {
return;
}
if (node.isLeaf()) {
codeTable.put(node.ch, code);
}
getCodeTable(node.left, code + "0", codeTable);
getCodeTable(node.right, code + "1", codeTable);
}
}
哈夫曼解压缩
1. 构建哈夫曼树
哈夫曼解压缩需要用到与压缩相同的哈夫曼树，因此需要先构建哈夫曼树。步骤与压缩时相同，将编码和字符对应关系调换即可。
2. 解码数据
将二进制编码的数据根据哈夫曼编码进行解码。从树的根节点开始，依次读取每一个二进制位，如果是0，则移动到当前节点的左子节点，如果是1，则移动到当前节点的右子节点，直到遇到叶子节点。当遇到叶子节点时，将该节点的字符存储下来，并从根节点重新开始处理下一个编码。
以下是具体的Java代码示例：
public class HuffmanDecompressor {
private static class Node {
public char ch;
public Node left;
public Node right;
public Node(char ch) {
this.ch = ch;
}
public boolean isLeaf() {
return left == null && right == null;
}
}
public static String decompress(String data, Node root) {
StringBuilder decodedData = new StringBuilder();
Node curr = root;
for (int i = 0; i < data.length(); i++) {
if (data.charAt(i) == '0') {
curr = curr.left;
} else if (data.charAt(i) == '1') {
curr = curr.right;
}
if (curr.isLeaf()) {
decodedData.append(curr.ch);
curr = root;
}
}
return decodedData.toString();
}
}
示例
示例1：压缩文件
下面的代码示例演示如何使用上面的HuffmanCompressor类将文件（已存在的test.txt文件）压缩并写入到新文件test.gz中，并解压缩到解压缩文件test_decoded.txt。
import java.io.*;
import java.nio.file.Files;
public class Main {
public static void main(String[] args) throws IOException {
String filePath = "test.txt";
String compressedFilePath = "test.gz";
String decompressedFilePath = "test_decoded.txt";
// 读取源文件
byte[] dataBytes = Files.readAllBytes(new File(filePath).toPath());
String data = new String(dataBytes);
// 压缩
String compressedData = HuffmanCompressor.compress(data);
// 将压缩后的数据写入到文件
FileOutputStream fos = new FileOutputStream(compressedFilePath);
byte[] compressedBytes = compressedData.getBytes("UTF-8");
fos.write(compressedBytes);
fos.close();
// 从压缩文件中读取数据
String compressedDataFromFile = new String(Files.readAllBytes(new File(compressedFilePath).toPath()), "UTF-8");
// 解压缩
String decompressedData = HuffmanDecompressor.decompress(compressedDataFromFile, getHuffmanTree(data));
// 将解压缩后的数据写入到文件
FileOutputStream fos2 = new FileOutputStream(decompressedFilePath);
byte[] decompressedBytes = decompressedData.getBytes("UTF-8");
fos2.write(decompressedBytes);
fos2.close();
}
private static HuffmanDecompressor.Node getHuffmanTree(String data) {
int[] freqTable = new int[256];
for (int i = 0; i < data.length(); i++) {
freqTable[data.charAt(i)]++;
}
PriorityQueue<HuffmanCompressor.Node> pqueue = new PriorityQueue<>();
for (int i = 0; i < freqTable.length; i++) {
if (freqTable[i] > 0) {
pqueue.offer(new HuffmanCompressor.Node(freqTable[i], (char) i));
}
}
while(pqueue.size() > 1) {
HuffmanCompressor.Node left = pqueue.poll();
HuffmanCompressor.Node right = pqueue.poll();
HuffmanCompressor.Node parent = new HuffmanCompressor.Node(left.value + right.value);
parent.left = left;
parent.right = right;
pqueue.offer(parent);
}
return pqueue.poll();
}
}
示例2：压缩字符串
以下代码演示如何使用上面的HuffmanCompressor类将字符串压缩并解压缩。
public class Main {
public static void main(String[] args) {
String data = "Hello, World!";
String compressedData = HuffmanCompressor.compress(data);
String decompressedData = HuffmanDecompressor.decompress(compressedData, getHuffmanTree(data));
System.out.println("原始数据：" + data);
System.out.println("压缩后的数据：" + compressedData);
System.out.println("解压缩后的数据：" + decompressedData);
}
private static HuffmanDecompressor.Node getHuffmanTree(String data) {
int[] freqTable = new int[256];
for (int i = 0; i < data.length(); i++) {
freqTable[data.charAt(i)]++;
}
PriorityQueue<HuffmanCompressor.Node> pqueue = new PriorityQueue<>();
for (int i = 0; i < freqTable.length; i++) {
if (freqTable[i] > 0) {
pqueue.offer(new HuffmanCompressor.Node(freqTable[i], (char) i));
}
}
while(pqueue.size() > 1) {
HuffmanCompressor.Node left = pqueue.poll();
HuffmanCompressor.Node right = pqueue.poll();
HuffmanCompressor.Node parent = new HuffmanCompressor.Node(left.value + right.value);
parent.left = left;
parent.right = right;
pqueue.offer(parent);
}
return pqueue.poll();
}
}
希望这些示例能够帮助您更好地了解如何使用Java实现哈夫曼压缩和解压缩。
本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：java实现哈夫曼压缩与解压缩的方法 - Python技术站
微信扫一扫 
支付宝扫一扫 