用java编写代码,要求用给定的字符集和频度统计数据建立哈夫曼树,并实现下列报文的编码和译码:'THIS PROGAM IS MY FAVORITE'并输出每个字母(包括空格)的编码
时间: 2024-02-06 07:13:02 浏览: 95
好的,我理解了你的问题。首先,让我们来看看建立哈夫曼树的步骤:
1. 统计每个字符的出现频率。
2. 将出现频率作为权值,将每个字符看作一个节点,构建一棵初始的只包含叶子节点的二叉树。
3. 选择两个权值最小的节点,将它们合并为一个新节点,并将新节点的权值设置为两个子节点的权值之和。将这个新节点插入到二叉树中,重复这个过程,直到所有节点都被合并到一起,形成一棵完整的哈夫曼树。
下面是用Java实现哈夫曼编码和译码的代码,其中包括了构建哈夫曼树、生成编码表和对给定文本进行编码和译码等功能:
```java
import java.util.*;
class HuffmanNode implements Comparable<HuffmanNode>{
char c;
int freq;
HuffmanNode left;
HuffmanNode right;
public HuffmanNode(char c, int freq){
this.c = c;
this.freq = freq;
}
public boolean isLeaf(){
return left == null && right == null;
}
@Override
public int compareTo(HuffmanNode o) {
return this.freq - o.freq;
}
}
public class HuffmanEncoding {
private Map<Character, String> encodingTable = new HashMap<>();
private void buildEncodingTable(HuffmanNode root, String code){
if (root.isLeaf()){
encodingTable.put(root.c, code);
return;
}
buildEncodingTable(root.left, code + "0");
buildEncodingTable(root.right, code + "1");
}
public void encode(String text){
// step 1: build frequency table
Map<Character, Integer> freqTable = new HashMap<>();
for (char c : text.toCharArray()){
freqTable.put(c, freqTable.getOrDefault(c, 0) + 1);
}
// step 2: construct initial binary tree
PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();
for (Map.Entry<Character, Integer> entry : freqTable.entrySet()){
pq.offer(new HuffmanNode(entry.getKey(), entry.getValue()));
}
// step 3: build Huffman tree
while (pq.size() > 1){
HuffmanNode left = pq.poll();
HuffmanNode right = pq.poll();
HuffmanNode parent = new HuffmanNode('\0', left.freq + right.freq);
parent.left = left;
parent.right = right;
pq.offer(parent);
}
// step 4: build encoding table
HuffmanNode root = pq.peek();
buildEncodingTable(root, "");
// step 5: encode text
StringBuilder sb = new StringBuilder();
for (char c : text.toCharArray()){
sb.append(encodingTable.get(c));
}
System.out.println("Encoded text: " + sb.toString());
// step 6: decode text
StringBuilder decodedText = new StringBuilder();
HuffmanNode curNode = root;
for (char c : sb.toString().toCharArray()){
if (c == '0'){
curNode = curNode.left;
} else {
curNode = curNode.right;
}
if (curNode.isLeaf()){
decodedText.append(curNode.c);
curNode = root;
}
}
System.out.println("Decoded text: " + decodedText.toString());
// step 7: print encoding table
System.out.println("Encoding table:");
for (Map.Entry<Character, String> entry : encodingTable.entrySet()){
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
public static void main(String[] args) {
HuffmanEncoding huffmanEncoder = new HuffmanEncoding();
huffmanEncoder.encode("THIS PROGRAM IS MY FAVORITE");
}
}
```
上述代码中,我们首先构建了一个哈夫曼节点类 `HuffmanNode`,其中包含字符、出现频率、左子节点和右子节点等属性。在 `HuffmanEncoding` 类中,我们实现了哈夫曼编码和译码的所有步骤。
我们首先通过 `buildFrequencyTable` 方法来统计每个字符的出现频率,然后构建了一个初始的只包含叶子节点的二叉树。接着,我们通过不断合并两个权值最小的节点来构建哈夫曼树,在这个过程中同时生成了编码表。最后,我们使用编码表对给定文本进行编码,并使用哈夫曼树对编码后的二进制串进行译码,得到原始的文本。
最后,我们输出了每个字符(包括空格)的编码表。
阅读全文