哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。给出文件中各个字符出现的频率,求各个字符的哈夫曼编码方案JAVA代码
时间: 2024-02-17 13:03:18 浏览: 31
以下是一个简单的Java实现:
```java
import java.util.PriorityQueue;
import java.util.Map;
import java.util.HashMap;
public class HuffmanEncoding {
private static class Node implements Comparable<Node> {
char c;
int freq;
Node left;
Node right;
public Node(char c, int freq) {
this.c = c;
this.freq = freq;
}
public Node(int freq, Node left, Node right) {
this.freq = freq;
this.left = left;
this.right = right;
}
public boolean isLeaf() {
return left == null && right == null;
}
@Override
public int compareTo(Node other) {
return Integer.compare(freq, other.freq);
}
}
public static Map<Character, String> buildHuffmanEncoding(String text) {
Map<Character, Integer> freqMap = new HashMap<>();
for (char c : text.toCharArray()) {
freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
}
PriorityQueue<Node> pq = new PriorityQueue<>();
for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
pq.offer(new Node(entry.getKey(), entry.getValue()));
}
while (pq.size() > 1) {
Node left = pq.poll();
Node right = pq.poll();
Node parent = new Node(left.freq + right.freq, left, right);
pq.offer(parent);
}
Node root = pq.poll();
Map<Character, String> encodingMap = new HashMap<>();
buildEncodingMap(root, encodingMap, "");
return encodingMap;
}
private static void buildEncodingMap(Node node, Map<Character, String> encodingMap, String encoding) {
if (node.isLeaf()) {
encodingMap.put(node.c, encoding);
} else {
buildEncodingMap(node.left, encodingMap, encoding + "0");
buildEncodingMap(node.right, encodingMap, encoding + "1");
}
}
public static void main(String[] args) {
String text = "hello world";
Map<Character, String> encodingMap = buildHuffmanEncoding(text);
for (Map.Entry<Character, String> entry : encodingMap.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
}
```
该代码首先统计文本中每个字符出现的频率,然后使用优先队列(最小堆)构建哈夫曼树。接着,通过递归遍历哈夫曼树,构建每个字符的编码映射。最后,输出每个字符的编码映射。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)