用java编写:利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。 【基本要求】 一个完整的系统应具有以下功能: (1)I:初始化(Initialization)。从终端读入字符集大小n , 以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中。 (2)E:编码(Encoding)。利用已建好的哈夫曼树(如不在内存,则从文件hfmTree中读人),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。 (3)D: 译码(Decoding)。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码,结果存入文件TextFile中。 (4)P:打印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上,每行 50 个代码。同时将此字符形式的编码文件写入文件 CodePrin 中。 (5)T:打印哈夫曼树(Tree printing)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。
时间: 2024-02-03 15:15:12 浏览: 86
用JAVA实现霍夫曼编码
很好,这是一个比较实际的问题,需要进行一定的编码和解码操作。我可以为你提供一个基本的框架,你可以在此基础上进行完善和改进。以下是代码实现:
```java
import java.io.*;
import java.util.*;
public class Huffman {
// 哈夫曼树节点
static class Node {
char ch; // 字符
int freq; // 权值
Node left, right; // 左右子树
public Node(char ch, int freq, Node left, Node right) {
this.ch = ch;
this.freq = freq;
this.left = left;
this.right = right;
}
}
// 哈夫曼编码表
static Map<Character, String> encodeTable = new HashMap<>();
static Map<String, Character> decodeTable = new HashMap<>();
// 读取字符集和权值
static void readFreqs(Scanner sc, int[] freqs) {
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
char ch = sc.next().charAt(0);
int freq = sc.nextInt();
freqs[ch] = freq;
}
}
// 构建哈夫曼树
static Node buildHuffmanTree(int[] freqs) {
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.freq));
for (char i = 0; i < freqs.length; i++) {
if (freqs[i] > 0) {
pq.offer(new Node(i, freqs[i], null, null));
}
}
while (pq.size() > 1) {
Node left = pq.poll();
Node right = pq.poll();
pq.offer(new Node('\0', left.freq + right.freq, left, right));
}
return pq.poll();
}
// 生成哈夫曼编码表
static void generateCodeTable(Node root, String code) {
if (root.left == null && root.right == null) {
encodeTable.put(root.ch, code);
decodeTable.put(code, root.ch);
} else {
generateCodeTable(root.left, code + "0");
generateCodeTable(root.right, code + "1");
}
}
// 编码文件
static void encodeFile(String inputFile, String outputFile) throws IOException {
try (Scanner sc = new Scanner(new File(inputFile));
BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile))) {
while (sc.hasNextLine()) {
String line = sc.nextLine();
for (int i = 0; i < line.length(); i++) {
char ch = line.charAt(i);
String code = encodeTable.get(ch);
bw.write(code);
}
bw.newLine();
}
}
}
// 解码文件
static void decodeFile(String inputFile, String outputFile) throws IOException {
try (Scanner sc = new Scanner(new File(inputFile));
BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile))) {
while (sc.hasNextLine()) {
String code = sc.nextLine();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < code.length(); ) {
int j = i + 1;
while (!decodeTable.containsKey(code.substring(i, j))) {
j++;
}
char ch = decodeTable.get(code.substring(i, j));
sb.append(ch);
i = j;
}
bw.write(sb.toString());
bw.newLine();
}
}
}
// 打印代码文件
static void printCodeFile(String inputFile, String outputFile) throws IOException {
try (Scanner sc = new Scanner(new File(inputFile));
BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile))) {
while (sc.hasNextLine()) {
String code = sc.nextLine();
while (!code.isEmpty()) {
int j = Math.min(50, code.length());
bw.write(code.substring(0, j));
bw.newLine();
code = code.substring(j);
}
}
}
}
// 打印哈夫曼树
static void printHuffmanTree(Node root, String outputFile) throws IOException {
try (BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile))) {
printHuffmanTree(root, "", bw);
}
}
static void printHuffmanTree(Node root, String prefix, BufferedWriter bw) throws IOException {
if (root.left == null && root.right == null) {
bw.write(prefix + root.ch);
bw.newLine();
} else {
printHuffmanTree(root.left, prefix + "0", bw);
printHuffmanTree(root.right, prefix + "1", bw);
}
}
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int[] freqs = new int[256];
System.out.print("请输入字符集大小n: ");
readFreqs(sc, freqs);
Node root = buildHuffmanTree(freqs);
generateCodeTable(root, "");
printHuffmanTree(root, "TreePrint.txt");
System.out.print("请输入要编码的文件路径: ");
String inputFile = sc.next();
encodeFile(inputFile, "CodeFile.txt");
printCodeFile("CodeFile.txt", "CodePrint.txt");
System.out.print("请输入要解码的文件路径: ");
String codeFile = sc.next();
decodeFile(codeFile, "TextFile.txt");
}
}
```
我来简要解释一下代码逻辑:
1. 定义了一个 `Node` 类表示哈夫曼树节点,包含字符、权值和左右子树。
2. 定义了两个哈夫曼编码表 `encodeTable` 和 `decodeTable`,用于存储字符和对应的编码以及编码和对应的字符。
3. 定义了 `readFreqs` 方法,用于从终端读入字符集大小和对应的权值。
4. 定义了 `buildHuffmanTree` 方法,用于构建哈夫曼树。
5. 定义了 `generateCodeTable` 方法,用于生成哈夫曼编码表。
6. 定义了 `encodeFile` 方法,用于编码文件。
7. 定义了 `decodeFile` 方法,用于解码文件。
8. 定义了 `printCodeFile` 方法,用于打印代码文件。
9. 定义了 `printHuffmanTree` 方法,用于打印哈夫曼树。
10. 在 `main` 方法中,先读入字符集和构建哈夫曼树,然后生成编码表和打印哈夫曼树,接着编码文件并打印代码文件,最后解码文件。
这个实现只是一个基本框架,你可以根据具体需求进行改进和完善。比如,可以加入文件压缩的功能,或者使用更高效的哈夫曼编码算法等。
阅读全文