Расширения

Структура оптимальных префиксных кодов, которые рассматривались в этом разделе, является фундаментальным результатом исследований в области сжа- тия данных. Но также важно понимать, что оптимальность никоим образом не означает, что обнаружен лучший способ сжатия данных в любых обстоятельствах.

Когда оптимального префиксного кода может оказаться недостаточно? Для начала представьте ситуацию с передачей черно-белых изображений: каждое изо- бражение представляет собой массив из 1000 χ 1000 пикселов и каждый пиксел принимает одно из двух значений (для черного или белого цвета). Также будем считать, что типичное изображение состоит почти полностью из белых пикселов: приблизительно 1000 из миллиона пикселов имеют черный цвет, а все остальные белые. При сжатии такого изображения весь метод префиксных кодов практически бесполезен: имеется текст из миллиона символов с двухбуквенным алфавитом {черный, белый}. Получается, что текст уже закодирован с использованием одного бита на букву — минимальной возможной длины в нашей системе кодирования.

Понятно, что такие изображения должны хорошо сжиматься. Интуитивно хотелось бы использовать «часть бита» для каждого из столь многочисленных белых пикселов, даже если каждый черный пиксел будет представляться не- сколькими битами. (В предельном случае отправка списка координат (x,y) всех черных пикселов будет работать эффективнее отправки изображения в виде тек- ста с миллионом битов.) Проблема в том, чтобы определить схему кодирования с четко определенным понятием «части бита». В этой области сжатия данных достигнуты определенные результаты; для подобных ситуаций разработан метод арифметического кодирования, а также ряд других способов.

Второй недостаток префиксных кодов в том виде, в каком они определяются здесь, заключается в том, что они не могут адаптироваться к изменениям в тексте. Снова рассмотрим простой пример. Допустим, мы хотим закодировать вывод про- граммы, которая строит длинную последовательность букв из набора {a, b, с, d}.

Также предположим, что в первой половине последовательности буквы a и b встре- чаются с равной частотой, а буквы с и d не встречаются вообще; во второй половине последовательности буквы с и d встречаются с равной частотой, а буквы a и b не встречаются вообще. В системе кодирования, разработанной в этом разделе, мы стремились организовать сжатие текста с четырехбуквенным алфавитом {a, b, с, d}, с равной частотой букв.

Но в этом примере в действительности частоты остаются стабильными в поло- вине текста, а потом радикально изменяются. Например, следующая схема позво- ляет обойтись всего одним битом на букву, с небольшими затратами на хранение дополнительной информации:

♦ Начать с кодировки, в которой бит 0 представляет а, а бит 1 представляет b.

♦ На середине последовательности вставить инструкцию, которая сообщает: «Кодировка изменяется, с этого момента бит 0 представляет с, а бит 1 пред- ставляет d».

♦ Использовать новую кодировку для оставшейся части последовательности. Суть в том, что небольшие затраты на описание новой кодировки могут мно- гократно окупиться, если они сокращают среднее количество битов на букву в длинном тексте. Методы, изменяющие кодировку внутри потока, называются адаптивными схемами сжатия. Для многих видов данных они приводят к суще- ственным улучшениям по сравнению со статическим методом, который был рас- смотрен выше.

Все эти аспекты дают представление о направлениях, в которых велась работа над сжатием данных. Как правило, существует компромисс между эффектив- ностью метода сжатия и его вычислительной сложностью. В частности, многие усовершенствования только что описанных кодов Хаффмана приводят к соот- ветствующему росту вычислительных затрат, необходимых для получения сжатой версии данных, их декодирования и восстановления исходного текста. Сейчас в области поиска баланса между ними идут активные исследования.

4.9.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Расширения:

  1. ВАРИКОЗНОЕ РАСШИРЕНИЕ ВЕН
  2. Расширение графического метода
  3. Самовоспитание как "расширение" сознания
  4. 3.1. РАСШИРЕНИЕ НЕЙРОЛОГИЧЕСКОГО КОНТАКТА
  5. 3.12.2. Техника расширенного восприятия
  6. Расширение внутреннего кругозора
  7. 7.2.2. Расширение полноты ответа
  8. 7.2.2. Расширение полноты ответа
  9. Метод расширения сознания
  10. 2. Расширение круга наследников по закону в российском наследственном праве