Кодирование Шеннона — Фано
Этот калькулятор по таблице вероятностей символов выдает коды Шеннона — Фано
Эта страница существует благодаря следующим персонам
 | Timur
|
Anton
|
Немного теории по кодированию Шеннона — Фано можно найти сразу под калькулятором.
Кодирование Шеннона — Фано
Таблица вероятности символов
| Имя | Значение | ||
|---|---|---|---|
Кодирование Шеннона — Фано
Кодирование Шеннона — Фано получило свое наименование в области сжатия данных благодаря авторам Клоду Шеннону и Роберту Фано. Данный способ кодирования информации представляет собой технику создания префиксного кода, основанного на наборе символов и их вероятностей (оценочных или измеренных). Этот код не вполне оптимален, в том смысле, что он не дает минимально возможной длинны кода, как, например Код Хаффмана.
При кодировании методом Шеннона — Фано, символы распределяются в порядке от наиболее вероятных к наименее вероятным и затем разделяются на два набора, чьи суммарные вероятности максимально приближены друг к другу. Далее формируется первый разряд кода всех символов: символы из первого набора получают двоичный "0", символы из второго — "1". Процесс деления на две части и получения следующих разрядов повторяется для полученных наборов аналогичным образом, до тех пор, пока в полученном наборе не остается по одному символу. Когда набор уменьшается до одного символа — код символа полностью сформирован.
Этот алгоритм производит довольно эффективный код переменной длины, когда наборы имеют одинаковую суммарную вероятность. Единственный бит, отличающий их друг от друга используется с максимальной эффективностью.
Однако, метод Шеннона — Фано не всегда дает оптимального префиксного кода; набор вероятностей {0.35, 0.17, 0.17, 0.16, 0.15} - один из примеров, по которому будет сформирован неоптимальный код этим способом.
По этой причине, код Шеннона — Фано почти никогда не используется. Код Хаффмана — почти такой же простой с точки зрения вычислительной сложности, но он производит наиболее короткий по длине код.1
Комментарии