Мой друг сказал мне, что он существует, но я никогда не смог его найти, не уверен, что он лжет, но мне очень интересно, как работает доказательство. (Да, я один из тех людей, которые узнали о кодировке Хаффмана из телешоу в Силиконовой долине, извините)Существует ли математическое доказательство того, что кодирование Хаффмана является наиболее эффективным алгоритмом сжатия без потерь?
Ответ: это не так, и вопрос неуместен. :-)
Вот вид высокого уровня. Алгоритмы сжатия без потерь обеспечивают обратимое отображение возможных документов для сжатия, сжатых документов. Документы можно рассматривать как строки бит. Существует 2^n возможных документов с n битами. Существует 2^n возможных сжатых документов с n битами. Поэтому принцип pidgin-hole гласит, что для каждого документа, который хранится более эффективно, некоторые другие возможные документы должны храниться менее эффективно.
Так как же возможно сжатие? Это возможно, потому что, хотя все документы возможны, они не одинаково вероятны. Таким образом, хороший алгоритм сжатия будет хранить вероятные документы очень эффективно, а маловероятные - неэффективно. Но тогда вопрос заключается в том, какие документы эффективны. Ответ на этот вопрос: «Это зависит». И ответ на вопрос, насколько хорош алгоритм сжатия, также будет зависеть.
Предположим, что вы берете набор случайных документов, составленных из набора символов, которые независимо отображаются с разными вероятностями. Кодирование Хаффмана дает наиболее эффективный возможный алгоритм сжатия.
Теперь предположим, что вы принимаете множество случайных предложений, которые могут быть написаны на английском языке? Кодирование Хаффмана ограничено просмотром необработанных частот. Он не использует тот факт, что некоторые комбинации букв появляются очень часто. Другие кодировки, которые могут использовать это, теперь будут работать лучше.
Теперь предположим, что вы взяли набор документов, которые могут быть созданы вашей камерой. Это не похоже на текст, и разные методы кодирования будут работать лучше.
Так бывают случаи, когда Хаффман лучше. Случаи, где это не так. И вопрос неубедительный, поскольку это зависит от того, какие документы могут быть вероятными?
Оптимальность кодирования Хаффмана зависит не только от характеристик несжатых данных (источника), но и от «кода каждого входного символа самостоятельно, используя целое число выходных символов» - альтернативы: сжатие строк (сразу несколько входных символов), арифметическое кодирование строк кодирования. – greybeard
(Dang! Я, должно быть, пропустил «pidgin-hole» в последний раз :) – greybeard
Это не самый эффективный метод сжатия без потерь. Арифметическое кодирование превосходит его для начала. Поскольку он не является самым эффективным, нет никаких доказательств того, что он есть. Я считаю, что это код optimal при использовании целого числа бит на символ, возможно, это доказательство, о котором говорил ваш друг.
Proof of Optimality of Huffman Codes, CSC373 Spring 2009.
Это доказывает промежуточные теоремы и приходит:
теоремы 3Алгоритм
HUF(A,f)вычисляет оптимальное дерево для частотfи алфавитA.
http://www.cs.utoronto.ca/~brudno/csc373w09/huffman.pdf –
Это возможно. Это зависит от типа сжимаемых данных. –
Это наиболее эффективный возможный алгоритм, учитывая, что входные символы независимы и одинаково распределены, а кодированные символы должны быть целыми числами. Если закодированные символы не обязательно должны быть целым числом бит, у вас есть арифметическое кодирование.Если входные символы не являются независимыми и одинаково распределены, то ни Хаффман, ни арифметическое кодирование не являются оптимальными. – immibis