用Java代码实现哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。给出文件中各个字符出现的频率,求各个字符的哈夫曼编码方案。
时间: 2024-02-17 08:04:54 浏览: 70
好的,这是一个非常有趣的问题。首先,我们需要构建哈夫曼树来生成编码。这里提供一个使用Java实现哈夫曼编码的例子:
```java
import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
public class HuffmanEncoder {
private static class Node {
char c;
int freq;
Node left;
Node right;
}
public static void main(String[] args) {
String input = "hello world";
Node root = buildHuffmanTree(input);
Map<Character, String> codes = generateCodes(root);
System.out.println(codes);
String encoded = encode(input, codes);
System.out.println(encoded);
String decoded = decode(encoded, root);
System.out.println(decoded);
}
private static Node buildHuffmanTree(String input) {
Map<Character, Integer> freqMap = new HashMap<>();
for (char c : input.toCharArray()) {
freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
}
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.freq));
for (char c : freqMap.keySet()) {
Node n = new Node();
n.c = c;
n.freq = freqMap.get(c);
pq.offer(n);
}
while (pq.size() > 1) {
Node left = pq.poll();
Node right = pq.poll();
Node parent = new Node();
parent.freq = left.freq + right.freq;
parent.left = left;
parent.right = right;
pq.offer(parent);
}
return pq.poll();
}
private static Map<Character, String> generateCodes(Node root) {
Map<Character, String> codes = new HashMap<>();
generateCodes(root, "", codes);
return codes;
}
private static void generateCodes(Node node, String code, Map<Character, String> codes) {
if (node == null) {
return;
}
if (node.left == null && node.right == null) {
codes.put(node.c, code);
return;
}
generateCodes(node.left, code + "0", codes);
generateCodes(node.right, code + "1", codes);
}
private static String encode(String input, Map<Character, String> codes) {
StringBuilder sb = new StringBuilder();
for (char c : input.toCharArray()) {
sb.append(codes.get(c));
}
return sb.toString();
}
private static String decode(String input, Node root) {
StringBuilder sb = new StringBuilder();
Node node = root;
for (char c : input.toCharArray()) {
if (c == '0') {
node = node.left;
} else if (c == '1') {
node = node.right;
}
if (node.left == null && node.right == null) {
sb.append(node.c);
node = root;
}
}
return sb.toString();
}
}
```
在这个例子中,我们首先构建了一个哈夫曼树,然后使用树来生成每个字符的编码。最后,我们使用这些编码来压缩原始输入并解码压缩后的输入以获得原始输入。
阅读全文