哈夫曼树编码

Question

我之前问过的哈夫曼树还有另一个问题！这是代码：

package huffman;

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Huffman {

    public ArrayList<Frequency> fileReader(String file)
    {
        ArrayList<Frequency> al = new ArrayList<Frequency>();
        Scanner s;
        try {

            s = new Scanner(new FileReader(file)).useDelimiter("");
            while (s.hasNext())
            {
                boolean found = false;
                int i = 0;
                String temp = s.next();
                while(!found)
                {


                    if(al.size() == i && !found)
                    {
                        found = true;
                        al.add(new Frequency(temp, 1));
                    }
                    else if(temp.equals(al.get(i).getString()))
                    {
                        int tempNum = al.get(i).getFreq() + 1;
                        al.get(i).setFreq(tempNum);
                        found = true;
                    }
                    i++;

                }



            }
        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        return al;
    }
    public Frequency buildTree(ArrayList<Frequency> al)
    {
        Frequency r = al.get(1);
        PriorityQueue<Frequency> pq = new PriorityQueue<Frequency>();
        for(int i = 0; i < al.size(); i++)
        {
            pq.add(al.get(i));          
        }
        /*while(pq.size() > 0)
        {
            System.out.println(pq.remove().getString());
        }*/

        for(int i = 0; i < al.size() - 1; i++)
        {   
           Frequency p = pq.remove(); 
           Frequency q = pq.remove();
           int temp = p.getFreq() + q.getFreq();
           r = new Frequency(null, temp);
           r.left = p; 
           r.right = q;
           pq.add(r);  // put in the correct place in the priority queue
        }
        pq.remove(); // leave the priority queue empty
        return(r); // this is the root of the tree built

    }

    public void inOrder(Frequency top)
    {
        if(top == null)
        {
            return;
        }
        else
        {
            inOrder(top.left);
            System.out.print(top.getString() +", ");
            inOrder(top.right);
            return;
        }
    }
    public void printFreq(ArrayList<Frequency> al)
    {
        for(int i = 0; i < al.size(); i++)
        {
            System.out.println(al.get(i).getString() + "; " + al.get(i).getFreq());
        }
    }

}

现在需要做的是我需要创建一个方法，该方法将搜索树以查找特定字符的二进制代码（011001 等）。最好的方法是什么？我想也许我会在树中进行正常搜索，就好像它是一个 AVL 树，如果它较大，则向右，如果较小，则向左。

但是因为节点不使用整数双精度等，而是仅使用包含字符作为字符串或 null 的对象来表示它不是叶子而只是根。另一种选择是按顺序运行以找到我正在寻找的叶子，但同时我如何确定我是向右走很多次还是向左走很多次才能获得角色。

package huffman;

public class Frequency implements Comparable  {
    private String s;
    private int n;
    public Frequency left;
    public Frequency right;

    Frequency(String s, int n)
    {
        this.s = s;
        this.n = n;
    }
    public String getString()
    {
        return s;
    }
    public int getFreq()
    {
        return n;
    }
    public void setFreq(int n)
    {
        this.n = n;
    }
    @Override
    public int compareTo(Object arg0) {
        Frequency other = (Frequency)arg0;

        return n < other.n ? -1 : (n == other.n ? 0 : 1);
    }
}

我想做的是找到实际到达每个字符的二进制代码。因此，如果我尝试对 aabbbcccc 进行编码，我将如何创建一个字符串来保存二进制代码，左转为 0，右转为 1。

令我困惑的是，因为您无法确定任何内容在哪里是因为树明显不平衡，无法确定角色是在你所在位置的右侧还是左侧。因此，您必须搜索整个树，但如果到达的节点不是您要查找的节点，则必须回溯到另一个根以到达其他叶子。

Answer 1

遍历哈夫曼树节点，得到一个像 {'a': "1001", 'b': "10001"} 等映射。您可以使用这个映射来获取特定字符的二进制代码。

如果您需要反向执行，只需将其作为状态机处理即可：

state = huffman_root
for each bit
    if (state.type == 'leaf')
        output(state.data);
        state = huffman_root
    state = state.leaves[bit]

老实说，我没有查看您的代码。如何处理这棵奇特的树应该是很明显的。

Answer 2

请记住，如果你有 1001，你永远不会有 10010 或 10011。所以你的基本方法看起来像这样（伪代码）：

if(input == thisNode.key) return thisNode.value
if(input.endsWith(1)) return search(thisNode.left)
else return search(thisNode.right)

我没有阅读你的程序来弄清楚如何集成它，但这是霍夫曼的关键要素简而言之编码

尝试这样的事情 - 你正在尝试找到令牌。因此，如果您想查找“10010”的字符串，您可以执行 search(root,"10010")

String search(Frequency top, String token) {
    return search(top,token,0);
}

// depending on your tree, you may have to switch top.left and top.right
String search(Frequency top, String token, int depth) {
    if(token.length() == depth) return "NOT FOUND";
    if(token.length() == depth - 1) return top.getString();
    if(token.charAt(depth) == '0') return search(top.left,token,depth+1);
    else return search(top.right,token,depth+1);

}

Answer 3

当我尝试霍夫曼编码编码树时，我考虑了两个选择。

选项 1：使用基于指针的二叉树。我对其中的大部分内容进行了编码，然后觉得，要从叶子追踪树以找到编码，我需要父指针。否则，就像本文中提到的那样，您对树进行搜索，这并不是立即找到编码的解决方案。基于指针的树的缺点是，树中的每个节点都必须有 3 个指针，我认为这太多了。遵循指针的代码很简单，但比选项 2 中的代码更复杂。

选项 2：使用基于数组的树来表示将在运行中用于编码和解码的编码树。所以如果你想要一个字符的编码，你可以在数组中找到该字符。非常简单，我用了一张桌子，就在那里我得到了叶子。现在我追踪到数组中索引 1 处的根。我为父级执行 (current_index / 2) 。如果子索引是父索引/2，则为左索引，否则为右索引。

选项 2 很容易编写代码，尽管数组可以有空格。我认为它的性能比基于指针的树更好。除了识别根和叶之外，现在是索引问题而不是对象类型问题。 ;) 如果您必须发送您的树，这也将非常有用！？

另外，在解码霍夫曼代码时，您不会搜索 (root, 10110) 。您只需在编码比特流中遍历树，根据您的比特向左或向右移动，当您到达叶子时，就输出字符。

希望这有帮助。

Harisankar Krishna Swamy（示例)

Answer 4

我猜你的作业要么已经完成，要么已经很晚了，但这也许会对其他人有所帮助。

其实很简单。您创建一棵树，其中 0 向右，1 向左。阅读流将引导您浏览树。当你击中一片叶子时，你会发现一封信并从头开始。就像glowcoder所说，非叶节点上永远不会有字母。该树还涵盖了每个可能的位序列。因此，无论输入的编码如何，以这种方式导航始终有效。

不久前，我有一个像你一样编写霍夫曼编码器/解码器的作业，我写了一篇博客文章，其中包含 Java 代码和更长的解释： http://www.byteauthor.com/2010/09/huffman-coding-in-java/

PS。大多数解释都是用尽可能少的位数序列化霍夫曼树，但编码/解码算法在源中非常简单。

Answer 5

下面是一个 Scala 实现：http://blog.flotsam。 nl/2011/10/huffman-coding-done-in-scala.html