Коды Хаффмана и сжатие данных

В задачах нахождения кратчайшего пути и минимального остовного дерева было показано, как жадные алгоритмы позволяют ограничиться определенными частя- ми решения (ребрами графа в этих случаях), основываясь исключительно на от- носительно «недальновидных» соображениях.
А сейчас будет рассмотрена задача, в которой «ограничение» понимается еще свободнее: по сути, жадное правило используется для сокращения размера экземпляра задачи, чтобы эквивалентную меньшую задачу можно было решить посредством рекурсии. Будет доказано, что такая жадная операция «безопасна» в том смысле, что решение меньшего экзем- пляра приводит к оптимальному решению исходной задачи, однако глобальные последствия исходного жадного решения проявляются только при завершении полной рекурсии.

Сама задача относится к одной из базовых тем из области сжатия данных — об- ласти, формирующей технологическую основу цифровой передачи данных.

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

Еще по теме Коды Хаффмана и сжатие данных:

  1. Оцепенение и сжатие
  2. Оцепенение и сжатие
  3. СЛОВЕСНЫЕ УТЕЧКИ И РЕЧЕВЫЕ КОДЫ
  4. СЛОВЕСНЫЕ УТЕЧКИ И РЕЧЕВЫЕ КОДЫ
  5. ГЛАВА ШЕСТАЯ Коды входа в Телос
  6. Глава 21 ПАРНЫЕ КОДЫ И НАВЕДЕННЫЕ ПРОГРАММЫ. ПРИНЦИП АНАЛОГОВ
  7. Григорьев Ю.А., Ревунков Г.И.. Банки данных, 2002
  8. Оценка данных о личности.
  9. 18.4. Права субъекта персональных данных
  10. 3.3.4. Методы обработки и анализа данных
  11. Банк данных
  12. Анализ и интерпретация полученных данных
  13. Анализ и интерпретация полученных данных
  14. Подготовка исходных данных
  15. 4.5. Право изготовителя базы данных
  16. 12.4. Анализ эмпирических данных