Всегда ли оптимально кодирование Хаффмана?

9

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

information-theory data-compression Кава
источник
В общем «нет». Для средних данных частота каждого символа будет> 1, и лучше использовать кодирование Хаффмана, а не коды фиксированной длины
@arunmoezhi Не могли бы вы привести пример, который я привел выше? Частота каждого символа больше 1, но фиксированная длина является более оптимальной.
Этот пример интересный. Но можете ли вы предоставить такой сценарий с вероятностями каждого символа вместо частоты и убедиться, что вероятности всех символов добавлены к 1
@arunmoezhi Я включил вероятности персонажей, и они суммируют до 1.

Ответы:

4

Энтропия H(A)для этой проблемы есть 1.998. Кодирование Хаффмана и кодирование с фиксированной длиной для этой задачи имеет среднюю длину кодового слова как 2. И к вашему сведению, кодирование, которое вы получили, используя кодировку Хаффмана, неверно. Huffman Encoding также создает коды, похожие на фиксированную длину для этой проблемы. Он использует жадный подход. Так aчто не получает код, а 0получает 00. Переработать дерево, которое вы генерируете, используя кодирование Хаффмана. Дерево, которое вы должны получить:введите описание изображения здесь

arunmoezhi
источник
Благодарю вас. Не могли бы вы предоставить какое-то доказательство того, что кодирование Хаффмана всегда более оптимально, чем фиксированная длина, или, по крайней мере, отсылаете меня к одному из них?
1
Вы можете обратиться к Introduction to Algorithmsпо CLRS. В главе о которой greedy algorithmsвы можете получить формальное доказательство Huffman algorithm. Это длинное доказательство и требует терпения, чтобы прочитать.
8

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

сурьма
источник
Что вы подразумеваете под "приближенным распределением населения"?
3
Существует теоретическое истинное распространение сообщения, которое можно гипотетически отправить. В идеале каждое сообщение должно быть закодировано таким образом, который пропорционален логарифму его вероятности, но поскольку коды Хаффмана представляют собой целое число битов, что неявно соответствует вероятностям, которые являются степенями двух. Отсюда и приближение. Посмотрите теорему Шеннона о кодировании.
8

Да, это всегда оптимально.

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

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

Это также охватывает другие методы, которые обеспечивают более высокое сжатие (работа вне пространства, для которого оптимален код Хаффмана).

Кейд Ру
источник