Хаффман кодирует один символ без таблицы поиска - PullRequest
Новая
       6

Хаффман кодирует один символ без таблицы поиска

0 голосов
/ 09 февраля 2019

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

Я написал следующий код, который работает неправильно.Проблема в том, что я не знаю, как заставить его остановиться после получения правильного результата.Он продолжает добавлять код после достижения правильного конечного узла. 

string lookup(HuffNode* root, char c, string prevCode, string direction){
  string currentCode = prevCode + direction;
  if(!root->isLeaf()){
    currentCode = lookup(root->getLeft(), c, currentCode, "0");
    currentCode = lookup(root->getRight(), c, currentCode, "1");
  }else{
    if(root->getChar() == c){
      return currentCode;
    }else{
      return prevCode;
    }
  }

  return currentCode;
}

string encodeChar(HuffNode* trie, char c){
  return lookup(trie, c, "", "");
}

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

1 Ответ

0 голосов
/ 09 февраля 2019

Было бы ужасно неэффективно искать хороший кусок дерева каждый раз, когда вы хотите создать код.На самом деле вы должны составить таблицу кодов для каждого символа.

В любом случае вам нужно собрать код в одну строку, которая передается по ссылке.Не возвращайте строку.(Это будет там, когда все будет сделано в строке, которая была первоначально передана по ссылке.) Вместо этого верните true или false, если символ был найден в листе.Затем, когда вы вызываете lookup() в каждой ветви, посмотрите, вернет ли она значение true.Если это так, немедленно верните true.Для каждого вызова добавьте соответствующий бит в строку (0 или 1).Если он возвращает false для второй ветви, удалите добавленный бит и верните false.

Тогда исходный вызов вернет true, если найдет символ, и строка будет иметь код.Если он возвращает false, символа не было ни в одном из листьев, и строка будет пустой.

...