2010-01-13 5 views
2

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

ответ

1

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

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

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

+0

Это то, что я подозревал сам, потому что он кажется практичным и повышает эффективность (это то, как написано?), Но я должен получить кодовое слово для каждого символа. Нормальный Я думаю, она должна говорить о символах, которые вводятся, так как она никогда не упоминала других ... никогда. Учитель никогда не упоминал этот метод в классе (и не ответил на мои письма об этом в течение недели), но я, вероятно, просто сделаю это и надеюсь, что он будет стоить, как минимум, половины очков. По крайней мере, теперь я знаю, что я не единственный, кто получает это от вопроса. спасибо большое, и желаю мне удачи! – user249555

+0

Удачи вам в этом! Я знаю, что это может расстраивать, когда ему дается нечеткое задание; хотя, если вам нужна помощь в интерпретации задания, может быть проще, если вы разместите точную формулировку вместо своего собственного перефразирования. (О, и это написано «эффективность», поскольку вы спросили: у вас отсутствует «i»). –

+0

Это был действительно точный перевод с румынского. Я не шучу, у меня было 2 строки текста (вторая строка попросила меня рассчитать среднюю длину слова). Излишне говорить, что я очень разочарован школьной системой здесь. – user249555

0

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

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

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

Другие вопросы Боюсь, что ответов нет.

+0

Арг, я повторил много ответа Брайана, просто заявил по-другому, «вслушиваясь». Спокойной ночи ... – Roboprog

+0

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