Сжатие данных
Материал из Википедии — свободной энциклопедии
Сжатие данных — процедура перекодирования данных, производимая с целью уменьшения их объёма. Применяется для более рационального использования устройств хранения и передачи данных.
Сжатие бывает без потерь (когда возможно восстановление исходных данных без искажений) или с потерями (восстановление возможно с незначительными искажениями). Сжатие без потерь используется при обработке компьютерных программ и данных. Сжатие с потерями обычно применяется для сокращения объёма звуковой, фото- и видеоинформации, оно значительно эффективнее сжатия без потерь.
Сжатие основано на устранении избыточности информации, содержащейся в исходных данных. Примером избыточности является повторение в тексте фрагментов (например, слов естественного или машинного языка). Подобная избыточность обычно устраняется заменой повторяющейся последовательности более коротким значением (кодом). Другой вид избыточности связан с тем, что некоторые значения в сжимаемых данных встречаются чаще других, при этом возможно заменять часто встречающиеся данные более короткими кодами, а редкие — более длинными (вероятностное сжатие). Сжатие данных, не обладающих свойством избыточности (например, случайный сигнал или шум), невозможно. Также, обычно невозможно сжатие зашифрованной информации.
Содержание |
[править] Алгоритмы сжатия текстов/файлов неизвестного формата
Имеется 2 основных подхода к сжатию файлов неизвестного формата.
- На каждом шаге алгоритма сжатия либо следующий символ помещается как есть (с специальным флагом помечающим, что он не сжат), либо указываются границы слова из предыдущего куска, которое совпадает с следующими символами файла. Разархивирование файлов сжатых таким образом выполняется очень быстро, поэтому эти алгоритмы используются для создания самораспаковывающихся программ.
- Для каждой последовательности в каждый момент времени собирается статистика её встречаемости в файле. На её основе вычисляется вероятность значений для очередного символа. После этого можно применять арифметическое кодирование или кодирование Хаффмана для замены часто встречающихся последовательностей на более короткие, а редко встречающихся — на более длинные.
[править] Библиография
- Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео Диалог-МИФИ, 2002 г., 384 стр. ISBN 5-86404-170-X 3000 экз.