Книга: Фундаментальные алгоритмы и структуры данных в Delphi
Сжатие с минимальной избыточностью
Сжатие с минимальной избыточностью
Теперь, когда в нашем распоряжении имеется класс потока битов, им можно воспользоваться при рассмотрении алгоритмов сжатия и восстановления данных. Мы начнем с исследования алгоритмов кодирования с минимальной избыточностью, а затем рассмотрим более сложное сжатие с применением словаря.
Мы приведем подробное описание трех алгоритмов кодирования с минимальной избыточностью: кодирование Шеннона-Фано (Shannon-Fano), кодирование Хаффмана (Huffman) и сжатие с применением скошенного дерева (splay tree compression), однако рассмотрим реализации только последних двух алгоритмов (алгоритм кодирования Хаффмана ни в чем не уступает, а кое в чем даже превосходит алгоритм кодирования Шеннона-Фано). При использовании каждого из этих алгоритмов входные данные анализируются как поток байтов, и различным значениям байтов тем или иным способом присваиваются различные последовательности битов.
- Сжатие с использованием словаря
- Глава 11. Сжатие данных.
- Сжатие LZ77
- Сжатие файлов NTFS
- Отправка с минимальной MTU
- 2.27. Сжатие строк
- 11. Меньше copy — меньше и вздору, или Избыточность текста и сжатие файла
- Сжатие данных
- Сжатие видео во Flash. Кодеки On2 VP6 и Sorenson Spark
- 4.7.1 Сжатие в PPP
- Спецификация минимальной функциональной совместимости
- 3.2. Размеры и сжатие файлов