Компрессор данных

Сжатие без потерь (англ. Lossless data compression) — метод сжатия информации, при использовании которого закодированная информация может быть восстановлена с точностью до бита. При этом оригинальные данные полностью восстанавливаются из сжатого состояния. Этот тип сжатия принципиально отличается от сжатия данных с потерями. Для каждого из типов цифровой информации, как правило, существуют свои оптимальные алгоритмы сжатия без потерь.

Сжатие данных без потерь используется во многих приложениях. Например, оно используется в популярном файловом формате Gzip. Оно также используется как компонент в сжатии с потерями.

Сжатие без потерь используется, когда важна идентичность сжатых данных оригиналу. Обычный пример — исполняемые файлы и исходный код. Некоторые графические файловые форматы, такие как PNG или TIFF,

Техника сжатия без потерь

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

Многоцелевые алгоритмы сжатия отличаются тем, что способны уменьшать широкий диапазон данных — исполняемые файлы, файлы данных, тексты, графику и т. д., и применяются в архиваторах. Специализированные же алгоритмы рассчитаны на некоторый тип файлов (текст, графику, звук и т. д.), зато сжимают такие файлы намного сильнее. Например: архиваторы сжимают звук примерно на треть (в 1,5 раза), в то время как

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

Статистические модели алгоритмов для текста (или текстовых бинарных данных, таких как исполняемые файлы) включают:

• Преобразование Барроуза — Уилера (блочно-сортирующая пре-обработка, которая делает сжатие более эффективным)
• (используется LZW

Алгоритмы кодирования через генерирование битовых последовательностей:

• Алгоритм Хаффмана (также используется Арифметическое кодирование

Методы сжатия без потерь

Полный список смотрите в Категория:Сжатие данных

Многоцелевые

• Кодирование длин серий — простая схема, дающая хорошее сжатие данных, которые содержат много повторяющихся значений
• LZW — используется в gif и во многих других.
• Deflate — используется в gzip, усовершенствованной версии zip и как часть процесса сжатия PNG.
• 7-zip.

Сжатие аудио

• Apple Lossless — ALAC (Apple Lossless Audio Codec)
• Audio Lossless Coding — также известен как MPEG-4 ALS
• Direct Stream Transfer — DST
• Dolby TrueHD
• DTS-HD Master Audio
•  — FLAC
• Meridian Lossless Packing — Monkey's Audio — Monkey’s Audio APE
• OptimFROG
• Shorten — SHN
• TTA — True Audio Lossless
• WMA Lossless — Windows Media Lossless

Сжатие графики

• ABO — Adaptive Binary Optimization
• GIF — (без потерь только для изображений содержащих менее 256 цветов)
• JPEG 2000 — (включает сжатие без потерь; также, испытан Sunil Kumar, профессором университета штата Сан-Диего)
• PGF — Progressive Graphics File (сжатие с/без потерь)
• PNG — Portable Network Graphics
• Qbit Lossless Codec — фокусируется на intra-frame («одна картинка») сжатии без потерь

Сжатие видео

• Animation codec
• CamStudio Video Codec
• CorePNG
• FFV1
• Huffyuv
• Qbit Lossless Codec
• SheerVideo
• TSCC — TechSmith Screen Capture Codec

Сжатие текстов

• PPM — архиватор HA (автор Harry Hirvola), использующий алгоритм PPM, известен высокой степенью сжатия на текстовых файлах; по этому параметру он превосходит даже

Примеры алгоритмов

• Семейство алгоритмов RLE (Run-length encoding — Кодирование длин серий)

Примеры форматов и их реализаций

• универсальные — Zip, RAR, GZip,
• звук — , Monkey’s Audio (APE), , TTE, LA (LosslessAudio), RealAudio Lossless,
• изображения — PNG
• видео —

  См. также

  • Сжатие данных с потерями

  Ссылки

  • Lossless кодирование видео в Linux