Допустим, у меня есть массивная строка из одного символа, скажем, x. Мне нужно использовать кодировку Хаффмана. Кодировка Хаффмана представляет собой полностью бинарное дерево. Так как же создать код Хаффмана только для одного символа, если нам вообще не нужны два листа?
Код Хаффмана для одного символа?
Ответы (2)
ответ jbr в порядке; это просто более длинная версия.
Хаффман предназначен для создания последовательности битов минимальной длины, которая содержит всю информацию в исходной последовательности символов, предполагая, что декодер уже знает набор символов. Если есть только один символ, входные данные не содержат никакой информации, кроме его длины.
В форматах данных на основе Хаффмана длина обычно кодируется отдельно, а не как часть самой битовой последовательности, закодированной по Хаффману. Таким образом, декодер односимвольного кода Хаффмана имеет всю информацию, необходимую для восстановления входных данных, без необходимости считывания чего-либо из битовой последовательности, закодированной Хаффманом. тогда логично, что выход кодера Хаффмана должен иметь длину 0 бит.
Если у вас нет длины, закодированной отдельно, то у вас должен быть символ для представления конца последовательности, чтобы декодер знал, когда прекратить чтение. Тогда ваше дерево Хаффмана будет иметь 2 узла, и вы не столкнетесь с этим особым случаем.
person
Community
schedule
15.03.2014
Если у вас есть только один символ, вам нужен только 1 бит на символ. Таким образом, вам действительно не нужно ничего делать, кроме как подсчитать количество битов и перевести каждый в свой символ.
person
jbr
schedule
15.03.2014
Я понимаю это, но мой код дал сбой для тестового примера с одним символом. Безопасно ли предположить, что алгоритм Хаффмана НЕ предназначен для одиночных символов?
- person JavaDeveloper; 16.03.2014
Я бы сказал так. На самом деле в этом нет смысла, так как кратчайшая возможная кодировка — это просто символы плюс длина строки.
- person jbr; 16.03.2014
