Кодирование Шеннона — Фано
Этот калькулятор по таблице вероятностей символов выдает коды Шеннона — Фано
Эта страница существует благодаря следующим персонам
 | Timur
|
Anton
|
Этот материал распространяется на условиях лицензии Creative Commons Attribution/Share-Alike License 3.0 (Unported). Это означает, что вы можете размещать этот контент на своем сайте или создавать на его основе собственный (в том числе и в коммерческих целях), при условии сохранения оригинального лицензионного соглашения. Кроме того, Вы должны отметить автора этой работы, путем размещения HTML ссылки на оригинал работы https://planetcalc.ru/8168/. Пожалуйста оставьте без изменения все ссылки на других авторов данной работы или работы, на основе которой создана данная работа (если таковые имеются в спроводительном тексте).
Немного теории по кодированию Шеннона — Фано можно найти сразу под калькулятором.
Кодирование Шеннона — Фано
Таблица вероятности символов
| Имя | Значение | ||
|---|---|---|---|
| А | 25 | ||
| Б | 25 | ||
| В | 20 | ||
| Г | 15 | ||
| Д | 10 | ||
| Е | 5 |
Кодирование Шеннона
| Символ | Код |
|---|---|
| Б | 01 |
| А | 00 |
| В | 10 |
| Г | 110 |
| Д | 1110 |
| Е | 1111 |
Кодирование Шеннона — Фано
Кодирование Шеннона — Фано получило свое наименование в области сжатия данных благодаря авторам Клоду Шеннону и Роберту Фано. Данный способ кодирования информации представляет собой технику создания префиксного кода, основанного на наборе символов и их вероятностей (оценочных или измеренных). Этот код не вполне оптимален, в том смысле, что он не дает минимально возможной длинны кода, как, например Код Хаффмана.
При кодировании методом Шеннона — Фано, символы распределяются в порядке от наиболее вероятных к наименее вероятным и затем разделяются на два набора, чьи суммарные вероятности максимально приближены друг к другу. Далее формируется первый разряд кода всех символов: символы из первого набора получают двоичный "0", символы из второго — "1". Процесс деления на две части и получения следующих разрядов повторяется для полученных наборов аналогичным образом, до тех пор, пока в полученном наборе не остается по одному символу. Когда набор уменьшается до одного символа — код символа полностью сформирован.
Этот алгоритм производит довольно эффективный код переменной длины, когда наборы имеют одинаковую суммарную вероятность. Единственный бит, отличающий их друг от друга используется с максимальной эффективностью.
Однако, метод Шеннона — Фано не всегда дает оптимального префиксного кода; набор вероятностей {0.35, 0.17, 0.17, 0.16, 0.15} - один из примеров, по которому будет сформирован неоптимальный код этим способом.
По этой причине, код Шеннона — Фано почти никогда не используется. Код Хаффмана — почти такой же простой с точки зрения вычислительной сложности, но он производит наиболее короткий по длине код.1
Комментарии