Эффективный поиск по дереву Хаффмана при запоминании пройденного пути

Question

В качестве последующего вопроса, связанного с моим вопрос относительно эффективного способа хранения дерева Хаффмана Мне было интересно, каков был бы самый быстрый и эффективный способ поиска в двоичном дереве (на основе выходных данных кодирования Хаффмана) и сохранения пути, пройденного к определенному узлу.

Это то, что у меня сейчас есть:

• Добавить корневой узел в очередь
• пока очередь не пуста, извлеките элемент из очереди
  • проверьте, действительно ли это то, что мы ищем
    • ДА:Следуйте указателю head обратно к корневому узлу, в то время как на каждом посещаемом нами узле мы проверяем, является ли он левым или правым, и отмечаем это.
    • вырваться из поиска
  • поставить в очередь левый и правый узлы

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

В этом случае я также получаю все пути вправо / влево в обратном порядке, например, если мы проследим за заголовком до корня и обнаружим, что от корня это right, left, left, мы получим left, left, right.или 001 в двоичном формате, когда то, что я ищу, - это получить 100 эффективным способом.

Также было предложено сохранить путь от root до узла в виде отдельного значения внутри узла, однако это не сработало бы, если бы у нас когда-либо было дерево, размер которого превышал бы количество битов, которое могла бы содержать переменная, созданная нами для этой цели, и в этот момент хранение данных также заняло бы огромные объемы памяти.

Answer 1

Создайте словарь value -> bit-string, который дал бы вам самый быстрый поиск.

Если значения имеют известный размер, вы, вероятно, можете обойтись просто массивом битовых строк и искать значения по их индексу.

Answer 2

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