Comments 12
Думаю, стоит указать, что алгоритм Шеннона-Фано для некоторых последовательностей может сформировать неоптимальные коды. У алгоритма Хафмана такого недостатка нет.
Да, забыл об этом упомянуть, спасибо.
Я так понимаю это возникает из-за того, что при построении кода по методу Шеннона-Фано разбиение можно сделать несколькими способами. И на одном из уровней это может привести к неоптимальности кода в целом, т.е. оптимальность на каждом шаге не дает оптимальности всей совокупности.
Я так понимаю это возникает из-за того, что при построении кода по методу Шеннона-Фано разбиение можно сделать несколькими способами. И на одном из уровней это может привести к неоптимальности кода в целом, т.е. оптимальность на каждом шаге не дает оптимальности всей совокупности.
Помнится мы в универе на лабораторных реализовывали шифрование и методом Фано, и методом Хафмана. Если кого-то интересует реализация метода Хафмана на паскале, могу скинуть исходник. Или опубликовать отдельным топиком с комментариями.
>упорядоченные по невозрастанию
Может лучше написать «убыванию», а то первый раз прочитал как раз таки «по возрастанию»
Может лучше написать «убыванию», а то первый раз прочитал как раз таки «по возрастанию»
Объясните, почему Шеннон-Фано может генерировать неоптимальные коды, а Хаффман — нет? Правильно ли я понимаю, что Шеннон-Фано слегка obsolete?
Например, если взять 8 символов с частотами 5,5,5,3,3,3,3,3, то код Хаффмана всем им даст длину 3 бита, а в коде Шеннона-Фано длины будут, соответственно, такими: 2,3,3,3,3,3,4,4. В результате средняя длина символа будет равна 91/30, что больше 3 (при том, что первое деление на две части прошло точно по границе символов). Но «почему» — надо разбираться.
uses crt;
Ностальгия. ТурбоПаскаль. Альма матер. Эх веселое было время :)
Ностальгия. ТурбоПаскаль. Альма матер. Эх веселое было время :)
Двадцать минут втыкал в фразу «упорядоченные по невозрастанию». Моя твоя не понимат. Как-нибудь вот так вот нельзя было написать «Символы первичного алфавита m1 выписывают в порядке убывания вероятностей.» ???(Спасибо ПедиВикии)
Sign up to leave a comment.
Алгоритм Шеннона-Фано