Расширенный код Хаффмана

Question

У меня есть домашнее задание: найти кодовые слова для символов в любом алфавите. Он говорит, что я должен использовать двоичный код Хаффмана для групп из трех символов. Что именно это значит? Я использую обычный Хаффман на [алфавит] ^ 3? Если да, то как мне узнать разницу между 3 символами в группе?

Answer 1

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

Так, например, если ваш алфавит состоит из a, b и c, вместо генерации кодировки для каждого из них по отдельности, вы должны создать кодировку для aaa, aab , aac и т. Д. Каждая из этих строк будет рассматриваться как отдельный символ в алгоритме Хаффмана; Вы можете отличить их друг от друга, просто сравнивая их. Если вам нужно принять ввод произвольной длины, вам также нужно будет включить в свой алфавит символы, представляющие собой строки длиной 1 или 2. Например, если вы кодируете строку aabacab, вам необходимо разбить ее в символы aab, aca и b.

Помогает ли это ответить на ваш вопрос? Я не совсем уверен, что вы ищете, поэтому, пожалуйста, не стесняйтесь редактировать свой вопрос или ответ в комментарии, если это ничего не прояснило.

Answer 2

Пища для размышлений: как насчет более коротких строк и перестановок «границ блоков»? Как насчет 1 и 2 символьных строк? Вы просто подсчитываете 3, 6, 9, 12, ... символов во входном тексте, а затем обнуляете любые неравные длины в конце?

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

Возможно, попробовать все перестановки из 3 символов, сохранив наиболее часто используемые, а затем попытаться найти подходящую для пробелов длиной 1 и 2 символа? Хм, звучит так, как будто это может быть очень медленно, но выполнимо, используя некоторый рекурсивный подход деления и счетчика: вытащите длинную строку длины блока N, затем вернитесь к кодированию пробелов как длины N - 1.

Боюсь, больше вопросов, чем ответов.