java - 我在 Huffman 的 Java 编码中遇到了一些逻辑错误
问题描述
这是代码...
public class Huffman_Coding {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter a string to compress: ");
String str = sc.nextLine();
sc.close();
HashString hs = new HashString();
HashMap<Character, Integer> hm = hs.getStringHash(str);
PriorityQueue<Node> pq = new PriorityQueue<Node>();
for (char ch : hm.keySet()) {
pq.add(new Node(null, null, hm.get(ch), ch));
}
System.out.println(pq);
while (pq.size() != 1) {
Node left = pq.poll();
Node right = pq.poll();
Node parent = new Node(left, right, left.freq + right.freq, '\0');
pq.add(parent);
System.out.println(pq);
}
Huffman_Tree ht = new Huffman_Tree();
String ans = "";
ht.inOrder(pq.poll(), ans);
}
}
class Node implements Comparable<Node> {
@Override
public String toString() {
return "Node [freq=" + freq + ", ch=" + ch + "]";
}
Node lptr;
Node rptr;
int freq;
char ch;
Node(Node lptr, Node rptr, int freq, char ch) {
this.freq = freq;
this.lptr = lptr;
this.rptr = rptr;
this.ch = ch;
}
public int compareTo(Node o) {
int comparedvalue = Integer.compare(this.freq, o.freq);
if (comparedvalue != 0)
return comparedvalue;
else
return Integer.compare(this.ch, o.ch);
}
}
boolean isLeaf() {
return this.lptr == null && this.rptr == null;
}
}
class Huffman_Tree {
void inOrder(Node root, String code) {
if (!root.isLeaf()) {
inOrder(root.lptr, code + '0');
inOrder(root.rptr, code + '1');
} else
System.out.println(root.ch + " : " + code);
}
}
在这里,对于输入字符串abccddeeee
,我得到类似:
[Node [freq=1, ch=a], Node [freq=1, ch=b], Node [freq=2, ch=c], Node [freq=2, ch=d], Node [freq=4, ch=e]]
[Node [freq=2, ch= ]]
我很困惑为什么在第二步中节点有'd'是从'e'开始的。这让我在最终编码中出错。为什么 compareTo 方法失败我无法理解。
getHashString 返回一个 Hash,其键为字符,值为频率。
解决方案
我无法弄清楚为什么在轮询元素 ant添加PriorityQueue
新的“合成”元素之后元素的顺序不是预期的,但我认为你可以解决切换到 a 的问题,就像我成功完成的那样TreeSet
TreeSet<Node> pq = new TreeSet<Node>((n1, n2) -> n1.compareTo(n2)); // explicit but unnecessary comparator
并将每次pq.poll()
调用更改为pq.pollFirst()
...
我希望这个解决方法可以帮助你!
编辑
正如您在官方PriorityQueue
文档中看到的那样,* iterator() 方法中提供的迭代器不能保证以任何特定顺序遍历优先级队列的元素。如果您需要有序遍历,请考虑使用 Arrays.sort(pq.toArray()).*
这应该可以解释为什么toString()
方法调用以不同于预期优先级顺序的顺序显示队列元素......
推荐阅读
- android - 如何使用 Android Webview 加载单屏 Web 应用程序?
- python - 使用 Dash plotly 删除响应功能
- c# - Automapper - 如何实现查找
- xml - XSLT:在重新排列 XML 时面临多个父节点的问题
- r - R通过grep搜索将数据附加到df列(每个模式=新列)
- publishing - 如何使用 Adobe Animate 制作 Android App Bundle 以将其发布到谷歌商店?
- r - R:一张图中日期对象的两个折线图
- r - 如何从文件名中获取最新日期
- c# - RazorPages 如何将 GET 参数传递给 OnGet?
- node.js - 尝试在 backeng 中比较密码时出错 - NODE.JS