需要用给定的字符集和频度表,如T:80,H:47其余字母的频度随机生成
时间: 2024-02-06 21:13:03 浏览: 88
好的,那么我们可以在构建哈夫曼编码树之前,先根据给定的字符集和频度表生成一个包含所有字符及其对应频度的哈希表,然后在生成哈夫曼编码树时,只考虑哈希表中出现过的字符。
下面是修改后的代码:
```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, Map<Character, Integer> freqTable){
// step 1: filter out characters not in freqTable
Map<Character, Integer> filteredFreqTable = new HashMap<>();
for (char c : text.toCharArray()){
if (freqTable.containsKey(c)){
filteredFreqTable.put(c, freqTable.get(c));
}
}
// step 2: construct initial binary tree
PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();
for (Map.Entry<Character, Integer> entry : filteredFreqTable.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()){
if (freqTable.containsKey(c)){
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) {
Map<Character, Integer> freqTable = new HashMap<>();
freqTable.put('T', 80);
freqTable.put('H', 47);
Random rand = new Random();
for (char c = 'A'; c <= 'Z'; c++){
if (!freqTable.containsKey(c)){
freqTable.put(c, rand.nextInt(50) + 1); // 生成1到50之间的随机数
}
}
freqTable.put(' ', rand.nextInt(50) + 1); // 空格也加入频度表
HuffmanEncoding huffmanEncoder = new HuffmanEncoding();
huffmanEncoder.encode("THIS PROGRAM IS MY FAVORITE", freqTable);
}
}
```
在上述代码中,我们首先根据给定的字符集和频度表构建了一个哈希表 `freqTable`,然后使用随机数生成了剩余字母的频度,并将其加入到哈希表中。在对文本进行编码时,我们只考虑哈希表中出现过的字符。
注意,由于我们使用了随机数生成剩余字母的频度,所以每次运行程序时,生成的哈夫曼编码树和编码表都可能会有所不同。
阅读全文