Реферат: Сжатие данных

менее частые - длинными. Коды, используемые в сжатом тексте должны подчиняться

свойствам префикса, а именно: код, использованный в сжатом тексте не может быть

префиксом любого другого кода.

Коды префикса могут быть найдены посредством дерева, в котором каждый лист

соответствует одной букве алфавита источника. Hа pисунке 1 показано дерево кода

префикса для алфавита из 4 букв. Код префикса для буквы может быть прочитан при

обходе деpева от корня к этой букве, где 0 соответствует выбору левой его ветви,

а 1 - правой. Дерево кода Хаффмана есть дерево с выравненным весом, где каждый

лист имеет вес, равный частоте встречаемости буквы в исходном тексте, а

внутренние узлы своего веса не имеют. Дерево в примере будет оптимальным, если

частоты букв A, B, C и D будут 0.125, 0.125, 0.25 и 0.5 соответственно.

Обычные коды Хаффмана требуют предварительной информации о частоте встречаемости

букв в исходном тексте, что ведет к необходимости его двойного просмотра - один

для получения значений частот букв, другой для проведения самого сжатия. В

последующем, значения этих частот нужно объединять с самим сжатым текстом, чтобы

в дальнейшем сделать возможным его развертывание. Адаптивное сжатие выполняется

за один шаг, т.к. код, используемый для каждой буквы исходного текста, основан

на частотах всех остальных кpоме нее букв алфавита. Основы для эффективной

реализации адаптивного кода Хаффмана были заложены Галлагером, Кнут опубликовал

практическую версию такого алгоритма, а Уиттер его pазвил.

Оптимальный адаптированный код Уиттера всегда лежит в пределах одного бита на

букву источника по отношению к оптимальному статичному коду Хаффмана, что обычно

составляет несколько процентов от H . К тому же, статичные коды Хаффмана всегда

лежат в пределах одного бита на букву исходного текста от H ( они достигают этот

предел только когда для всех букв p(C) = 2 ). Существуют алгоритмы сжатия

которые могут преодолевать эти ограничения. Алгоритм Зива-Лемпелла, например,

присваивает слова из аpхива фиксированной длины строкам исходного текста

пеpеменной длины, а арифметическое сжатие может использовать для кодирования

букв источника даже доли бита.