java将一段英文短文中各字符(包括标点符号)的统计出的频率值,自动生成01哈夫曼编码,并将该短文编码成01编码;
时间: 2024-04-01 21:34:36 浏览: 77
java实现哈夫曼算法
5星 · 资源好评率100%
以下是Java代码示例,可以实现将输入的英文短文进行哈夫曼编码处理,并输出编码后的01序列:
```java
import java.util.PriorityQueue;
import java.util.Scanner;
class Node implements Comparable<Node> {
char ch;
int freq;
Node left, right;
Node(char ch, int freq, Node left, Node right) {
this.ch = ch;
this.freq = freq;
this.left = left;
this.right = right;
}
public int compareTo(Node other) {
return this.freq - other.freq;
}
public boolean isLeaf() {
return left == null && right == null;
}
}
public class HuffmanEncoder {
private String[] codeTable = new String[256];
private Node root;
public void encode(String text) {
int[] freq = new int[256];
for (int i = 0; i < text.length(); i++) {
freq[text.charAt(i)]++;
}
PriorityQueue<Node> pq = new PriorityQueue<>();
for (int i = 0; i < 256; i++) {
if (freq[i] > 0) {
pq.offer(new Node((char) i, freq[i], null, null));
}
}
while (pq.size() > 1) {
Node left = pq.poll();
Node right = pq.poll();
Node parent = new Node('\0', left.freq + right.freq, left, right);
pq.offer(parent);
}
root = pq.poll();
createCodeTable(root, "");
StringBuilder sb = new StringBuilder();
for (int i = 0; i < text.length(); i++) {
sb.append(codeTable[text.charAt(i)]);
}
System.out.println("Encoded text: " + sb.toString());
}
private void createCodeTable(Node node, String code) {
if (node.isLeaf()) {
codeTable[node.ch] = code;
return;
}
createCodeTable(node.left, code + "0");
createCodeTable(node.right, code + "1");
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the text to encode:");
String text = sc.nextLine();
HuffmanEncoder encoder = new HuffmanEncoder();
encoder.encode(text);
}
}
```
代码中使用了Node类来存储每个字符及其出现次数,并使用PriorityQueue来维护节点,以便于构建哈夫曼树。在构建哈夫曼树的过程中,使用了贪心策略,每次选取频率最小的两个节点进行合并。构建完成后,使用递归的方式生成每个字符的编码,并将编码存储在codeTable数组中。最后,使用编码表将原始文本编码成01序列,并输出结果。
阅读全文