用java代码实现:输入一段文本,计算其中每一个字符的 huffman 编码,输出编码后文本的长度。
时间: 2023-02-06 13:20:34 浏览: 61
可以使用 Java 的 `java.util.PriorityQueue` 和 `java.util.Map` 来实现 Huffman 编码。
下面是一个示例代码:
```java
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
public class HuffmanEncoding {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String text = sc.nextLine();
// 统计每个字符出现的次数
int[] charFrequency = new int[256];
for (char c : text.toCharArray()) {
charFrequency[c]++;
}
// 创建哈夫曼树
Node root = buildHuffmanTree(charFrequency);
// 生成哈夫曼编码表
Map<Character, String> codes = new HashMap<>();
generateHuffmanCodes(root, "", codes);
// 编码文本并计算长度
int length = 0;
for (char c : text.toCharArray()) {
length += codes.get(c).length();
}
System.out.println("编码后文本的长度为:" + length);
}
// 内部类:哈夫曼树节点
private static class Node implements Comparable<Node> {
char c;
int frequency;
Node left;
Node right;
Node(char c, int frequency) {
this.c = c;
this.frequency = frequency;
}
@Override
public int compareTo(Node other) {
return this.frequency - other.frequency;
}
}
// 构建哈夫曼树
private static Node buildHuffmanTree(int[] charFrequency) {
PriorityQueue<Node> queue = new PriorityQueue<>();
for (int i = 0; i < charFrequency.length; i++) {
if (charFrequency[i] > 0) {
queue.offer(new Node((char) i, charFrequency[i]));
}
}
while (queue.size() > 1) {
Node left = queue.poll();
Node right = queue.poll();
Node parent = new Node('\0', left.frequency + right.frequency);
parent.left = left;
parent.right = right;
queue.offer(parent);
}
return queue.poll();
}
// 生成哈夫曼编码表
private static void generateHuffmanCodes(Node