Фано. b) Развесим
Фано.
b)
Развесим на обоих приведенных деревьях Фано, в порядке поступления, элементы 26-символьного алфавита {A .. Z}. Закодируйте, используя каждое из деревьев, символьную строку HAMLET и определите соответствующие коэффициенты сжатия.
Код, построенный в согласии с условием Фано, принято называть префиксным. Если упаковать ASCII текст с помощью префиксного кода, то дальнейшая распаковка полученной двоичной последовательности осуществляется без потерь.
Алгоритм распаковки, как легко заметить, имеет линейную трудоемкость - O(N), диктуемую входной последовательностью. При чтении из нее очередного бита мы выбираем на кодовом дереве соответствующую ветвь из текущего узла; достигнув же терминальной вершины, помещаем висящий в ней символ в выходной текст и вновь возвращаемся к корню.
<<< Предыдущий урок Следующий урок >>>
| Новости | Регистрация | Курсы | Карта сайта | Контактная информация |
Курс 1
Глава Z
Простые геометрические задачи. Задача
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
