请帮我生产哈夫曼编码的Java代码
时间: 2024-11-29 22:33:27 浏览: 3
当然可以。Huffman编码是一种基于频率的最优二进制前缀编码算法,用于数据压缩。以下是简单的Java代码实现Huffman树及其编码过程:
```java
import java.util.*;
class HuffmanNode implements Comparable<HuffmanNode> {
int freq;
char data;
HuffmanNode left, right;
HuffmanNode(int freq, char data) {
this.freq = freq;
this.data = data;
left = null;
right = null;
}
@Override
public int compareTo(HuffmanNode other) {
return Integer.compare(this.freq, other.freq);
}
}
public class HuffmanCoding {
private static void mergeTrees(HuffmanNode[] trees) {
PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();
for (HuffmanNode node : trees) {
if (node != null) {
pq.offer(node);
}
}
while (pq.size() > 1) {
HuffmanNode n1 = pq.poll();
HuffmanNode n2 = pq.poll();
int sum = n1.freq + n2.freq;
pq.offer(new HuffmanNode(sum, (char)0, n1, n2));
}
HuffmanNode huffmanTree = pq.poll(); // 返回根节点
buildCode(huffmanTree, "");
}
private static void buildCode(HuffmanNode node, String code) {
if (node.left == null && node.right == null) { // 叶子节点,添加编码
HuffmanEncoding.codes[node.data] = code;
} else {
buildCode(node.left, code + "0");
buildCode(node.right, code + "1");
}
}
// 使用时,先统计字符频率然后创建Huffman树
public static Map<Character, String> getHuffmanCodes(String input) {
Map<Character, Integer> frequencyMap = new HashMap<>();
for (char c : input.toCharArray()) {
frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
}
HuffmanNode[] trees = frequencyMap.entrySet().stream()
.map(e -> new HuffmanNode(e.getValue(), e.getKey()))
.toArray(HuffmanNode[]::new);
mergeTrees(trees);
return HuffmanEncoding.codes; // 初始化空map后返回
}
public static void main(String[] args) {
String input = "example text";
Map<Character, String> codes = getHuffmanCodes(input);
System.out.println("Example text with Huffman codes: " + input);
for (Map.Entry<Character, String> entry : codes.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
}
// 使用时,在main函数传入需要编码的字符串
```
这段代码首先计算输入字符串的字符频率,然后生成Huffman树并计算每个字符对应的编码。`getHuffmanCodes`函数返回一个字典,其中键是字符,值是它们的Huffman编码。
阅读全文