用java jdk1.8代码实现:输入一段文本,计算其中每一个字符的 huffman 编码,输出编码后文本的长度。
时间: 2023-02-06 19:16:56 浏览: 201
这里是一个示例代码,它接受一个字符串作为输入,并输出每个字符的 huffman 编码以及编码后文本的长度。
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public class HuffmanEncoder {
private static class Node implements Comparable<Node> {
char ch;
int freq;
Node left;
Node right;
Node(char ch, int freq) {
this.ch = ch;
this.freq = freq;
}
Node(Node left, Node right) {
this.left = left;
this.right = right;
this.freq = left.freq + right.freq;
}
public int compareTo(Node other) {
return this.freq - other.freq;
}
}
public static Map<Character, String> buildCodeTable(String text) {
// 统计每个字符的频率
Map<Character, Integer> freqMap = new HashMap<>();
for (int i = 0; i < text.length(); i++) {
char ch = text.charAt(i);
freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1);
}
// 构建 huffman 树
PriorityQueue<Node> heap = new PriorityQueue<>();
for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
heap.offer(new Node(entry.getKey(), entry.getValue()));
}
while (heap.size() > 1) {
Node left = heap.poll();
Node right = heap.poll();
heap.offer(new Node(left, right));
}
Node root = heap.poll();
// 构建编码表
Map<Character, String> codeTable = new HashMap<>();
buildCodeTable(root, "", codeTable);
return codeTable;
}
private static void buildCodeTable(Node node, String code, Map<Character, String> codeTable) {
if (node.left == null && node.right == null) {
codeTable.put(node.ch, code);
return;
}
buildCodeTable(node.left, code + "0", codeTable);
buildCodeTable(node.right, code + "1", codeTable);
}
public static int encode(String text) {
Map<Character, String> codeTable = buildCodeTable(text);
// 编码文本
int encodedLen = 0;
for (int i = 0; i < text.length(); i++) {
char ch = text.charAt(i);
阅读全文