用java代码完成以下实验:1、输入一段100—200字的英文短文,存入一文件a中。 2、写函数统计短文出现的字母个数n及每个字母的出现次数。 3、写函数以字母出现次数作权值,用固定数组构建Haffman树(n个叶子),给出每个字母的Haffman编码。 4、用每个字母编码对原短文进行编码,码文存入文件b中。 5、用Haffman树对b中码文进行译码,结果存入文件c中,比较a,c是否一致,以检验编码、译码的正确性。
时间: 2023-06-19 11:04:43 浏览: 81
以下是Java代码实现,包括了对文件的读写操作、Huffman编码和解码实现:
```java
import java.io.*;
import java.util.*;
public class HuffmanCoding {
private static String INPUT_FILE = "a.txt";
private static String OUTPUT_FILE = "b.txt";
private static String DECODED_FILE = "c.txt";
public static void main(String[] args) {
try {
// 读取输入文件
String input = readFile(INPUT_FILE);
System.out.println("原文:\n" + input + "\n");
// 统计每个字符的出现次数
Map<Character, Integer> frequencyMap = getFrequencyMap(input);
System.out.println("字符出现频率:\n" + frequencyMap + "\n");
// 构建Huffman树
HuffmanTree huffmanTree = new HuffmanTree(frequencyMap);
// 获取每个字符的Huffman编码
Map<Character, String> encodingMap = huffmanTree.getEncodingMap();
System.out.println("Huffman编码:\n" + encodingMap + "\n");
// 对原文进行编码,输出到文件b中
String encoded = encode(input, encodingMap);
writeFile(OUTPUT_FILE, encoded);
System.out.println("编码结果已写入文件b.txt");
// 对编码后的文本进行解码,输出到文件c中
String decoded = decode(encoded, huffmanTree.getRoot());
writeFile(DECODED_FILE, decoded);
System.out.println("解码结果已写入文件c.txt");
// 比较原文和解码后的文本是否一致
if (input.equals(decoded)) {
System.out.println("编码、解码成功!");
} else {
System.out.println("编码、解码失败!");
}
} catch (IOException e) {
e.printStackTrace();
}
}
// 读取文件内容
private static String readFile(String filename) throws IOException {
BufferedReader br = new BufferedReader(new FileReader(filename));
StringBuilder sb = new StringBuilder();
String line;
while ((line = br.readLine()) != null) {
sb.append(line);
}
br.close();
return sb.toString();
}
// 写入文件内容
private static void writeFile(String filename, String content) throws IOException {
BufferedWriter bw = new BufferedWriter(new FileWriter(filename));
bw.write(content);
bw.close();
}
// 统计字符出现频率
private static Map<Character, Integer> getFrequencyMap(String input) {
Map<Character, Integer> frequencyMap = new HashMap<>();
for (char c : input.toCharArray()) {
frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
}
return frequencyMap;
}
// Huffman编码
private static String encode(String input, Map<Character, String> encodingMap) {
StringBuilder sb = new StringBuilder();
for (char c : input.toCharArray()) {
sb.append(encodingMap.get(c));
}
return sb.toString();
}
// Huffman解码
private static String decode(String encoded, HuffmanNode root) {
StringBuilder sb = new StringBuilder();
HuffmanNode node = root;
for (char c : encoded.toCharArray()) {
if (c == '0') {
node = node.getLeft();
} else {
node = node.getRight();
}
if (node.isLeaf()) {
sb.append(node.getCharacter());
node = root;
}
}
return sb.toString();
}
// Huffman树
private static class HuffmanTree {
private final HuffmanNode root;
public HuffmanTree(Map<Character, Integer> frequencyMap) {
PriorityQueue<HuffmanNode> queue = new PriorityQueue<>();
for (Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) {
queue.offer(new HuffmanNode(entry.getKey(), entry.getValue()));
}
while (queue.size() > 1) {
HuffmanNode left = queue.poll();
HuffmanNode right = queue.poll();
queue.offer(new HuffmanNode(left, right));
}
root = queue.poll();
}
public Map<Character, String> getEncodingMap() {
Map<Character, String> encodingMap = new HashMap<>();
StringBuilder sb = new StringBuilder();
buildEncodingMap(root, sb, encodingMap);
return encodingMap;
}
private void buildEncodingMap(HuffmanNode node, StringBuilder sb, Map<Character, String> encodingMap) {
if (node.isLeaf()) {
encodingMap.put(node.getCharacter(), sb.toString());
return;
}
sb.append('0');
buildEncodingMap(node.getLeft(), sb, encodingMap);
sb.deleteCharAt(sb.length() - 1);
sb.append('1');
buildEncodingMap(node.getRight(), sb, encodingMap);
sb.deleteCharAt(sb.length() - 1);
}
public HuffmanNode getRoot() {
return root;
}
private static class HuffmanNode implements Comparable<HuffmanNode> {
private final char character;
private final int frequency;
private final HuffmanNode left;
private final HuffmanNode right;
public HuffmanNode(char character, int frequency) {
this.character = character;
this.frequency = frequency;
this.left = null;
this.right = null;
}
public HuffmanNode(HuffmanNode left, HuffmanNode right) {
this.character = '\0';
this.frequency = left.frequency + right.frequency;
this.left = left;
this.right = right;
}
public char getCharacter() {
return character;
}
public int getFrequency() {
return frequency;
}
public HuffmanNode getLeft() {
return left;
}
public HuffmanNode getRight() {
return right;
}
public boolean isLeaf() {
return left == null && right == null;
}
@Override
public int compareTo(HuffmanNode o) {
return Integer.compare(frequency, o.frequency);
}
}
}
}
```
注意:上述代码中,Huffman编码的实现采用了递归方式,可能会在处理较长的文本时出现Stack Overflow异常。可以将递归改成迭代方式来解决此问题。