我们可以使用 Tries 来解码霍夫曼代码吗

Question

给定一组字符及其对应的哈夫曼编码字符串。我们可以使用尝试来解码它们吗？

我有以下 class 这说明了我的方法。我确实在 Internet 上尝试了一些测试用例，但我对我的发现并不完全满意。

这是我在互联网上找到的一个测试用例 'geeksforgeeks' 并且它对应的编码字符串在 main 方法中作为我的搜索函数的参数给出。这个测试用例似乎工作正常。有人可以解释为什么我们可以或为什么我们不能使用尝试吗？

public class HuffmanDecode {
    static class Code {
        Character c;
        Code[] children;
        boolean isEnd;
        public Code(){
            this.c = null;
            this.children = new Code[2];
            this.isEnd = false;
            for(int i = 0 ; i < 2; i++){
                children[i] = null;
            }
        }
    }

    static Code root;
    static StringBuilder str = new StringBuilder();

    public static void buildTree(String input, Code current, char ch){
        for(int i = 0 ; i < input.length() ; i++){
            char curr = input.charAt(i);
            int index = curr - '0';
            if(current.children[index] == null){
                current.children[index] = new Code();
            }
            current = current.children[index];
        }

        current.isEnd = true;
        current.c = ch;
    }

    public static String search(String input, Code current){
        for(int i = 0 ; i < input.length(); i++){
            char curr = input.charAt(i);
            int index = curr - '0';
            if(current!=null && current.isEnd){
                str.append(current.c);
                current = root;
                i--;
            }
            else if(current.children[index]!=null && !current.isEnd){
                current = current.children[index];
            }

        }
        if(current!=null && current.isEnd)str.append(current.c);
        return str.toString();
    }
    public static void main(String[] args) {
        HuffmanDecode obj = new HuffmanDecode();
        HashMap<Character, String> map = new HashMap<>();
        root = new Code();
        map.put('e',"10");
        map.put('f',"1100");
        map.put('g',"011");
        map.put('k',"00");
        map.put('o',"010");
        map.put('r',"1101");
        map.put('s',"111");

        map.forEach((key, value)->{
            obj.buildTree(value,root,key);
        });
        search("01110100011111000101101011101000111",root);
        System.out.println(str.toString());
    }
}

Answer 1

是的，只要它是二叉树，就可以使用 Trie 将字符编码和解码为位表示。没有二进制结构的 trie 将不可解码，因为在解析 trie 中每个节点的潜在字符值时，可能存在最终无法访问的字符，因为它们与由 trie 结构中更高层的节点表示的字符。例如，如果B用代码001表示，C用代码001111表示，解码算法就没有办法到达代表字母C的节点，因为它将return 每当它到达父值 B 时。这将使得无法解码任何包含字母 C 的语句，因此使非二进制特里树在编码或解码一组霍夫曼编码字符时无效。然而，给定一个二元树，代表一个字符的每个节点将被表示为该树中的一个叶值，这意味着每个编码字符都将有一个 "prefix code" 确保在其任何父节点中都没有字符表示 - - 从而确保字符表示可以通过解码算法达到。

我们可以使用 Tries 来解码霍夫曼代码吗

Can we use Tries to Decode a Huffman code

java

decoding

huffman-code

data-structures