Как пройти через дерево Хаффмана и получить доступ к сохраненным персонажам? - PullRequest
Новая
       53

Как пройти через дерево Хаффмана и получить доступ к сохраненным персонажам?

0 голосов
/ 11 октября 2018

Я пытаюсь создать простую программу, которая будет принимать строковый ввод, генерировать узлы для каждого символа, генерировать дерево Хаффмана из этих узлов, создавать хэш-карту, отображающую символы в их закодированные биты, и печатать ввод, используя хеш-картув кодировании Хаффмана.

До сих пор я был успешным.Следующее, что я хотел сделать, это распаковать сжатую строку.Мой подход состоял в том, чтобы использовать дерево Хаффмана таким образом, чтобы начиная с корня, если есть ветвь, я посмотрю на первый сжатый бит, если он равен нулю (0), то он перейдет к левой ветви иесли это один (1), он перейдет к правой ветви.Продолжая таким образом, для каждой ветви следующее значение сжатого бита будет учитываться каждый раз, пока не будет достигнут последний узел, а символ, сохраненный в узле, сохранен.Моя программа работает нормально, однако при вызове функции возвращается пустое строковое значение.

При поиске ответов я обнаружил, что кто-то пробовал подобный подход и добился успеха, однако это не такдело для меня. Расшифровка дерева Хаффмана

Это мой текущий код.Массив строк содержит сжатую строку, разбитую на отдельные символы.

private  String generateHashTreeHelper(HuffmanTree t, String path, String[] arr) {
            int i = 0;
            while(i < arr.length){
                if(t.isLeaf()){
                    path = path + t.c;
                }
                else{
                    if(arr[i] == "0"){
                        generateHashTreeHelper(t.leftBranch, path + t.leftBranch.c, arr); 
                    }
                    else if(arr[i] == "1"){
                        generateHashTreeHelper(t.rightBranch, path + t.rightBranch.c, arr); 
                    }
                }
                i++;
            }
            return path;
        }

1 Ответ

0 голосов
/ 11 октября 2018

Я перевел код из C ++ примера в точности как это было.Это должно выглядеть примерно так: 

 public String decode(HuffmanTree root, String encodedString)
 {
        StringBuilder res = new StringBuilder();
        HuffmanTree node = root;
        Char[] characters = encodedString.toCharArray();

        for (int i = 0; i < characters.length; ++i) {
            if (characters[i].equals("0")) { // left child
                node = node.getLeft();
            } else { // rigth child
                node = node.getRight();
            }

            if (node.is_leaf() == true) {
                res.append(node.letter);
                node = root;
            }
        }

        return res.toString();
 }

И, конечно, я предполагаю, что у вас есть класс HuffmanTree и все необходимые методы, которые были использованы в этом коде.

...