Что такое сжатие данных без потерь?

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

Некоторые распространенные типы файлов, в которых используется сжатие данных без потерь, включают в себя компьютерные архивы zip и компьютерные zip-файлы International Business Machines (IBM), основанные на Unix-компьютерах. Также используются форматы файлов изображений, такие как формат графического обмена (GIF), файлы переносимой сетевой графики (PNG) и растровые изображения (BMP). Алгоритмы сжатия данных также различаются в зависимости от типа сжимаемого файла, с общими вариациями для текстовых, аудио и исполняемых программных файлов.

Две основные категории алгоритмов сжатия данных без потерь основаны на статистической модели входных данных и модели отображения битовых строк в файле данных. Используются стандартные статистические алгоритмы: преобразование Барроуза-Уилера (BWT), алгоритм Абрахама Лемпеля и Якоба Зива (LZ77), опубликованный в 1977 году, и метод прогнозирования с помощью частичного сопоставления (PPM). Часто используемые алгоритмы отображения включают алгоритм кодирования Хаффмана и арифметическое кодирование.

Некоторые из алгоритмов сжатия данных без потерь являются инструментами с открытым исходным кодом, а другие являются собственностью и запатентованы, хотя срок действия патентов на некоторые из них также истек. Это может привести к тому, что методы сжатия иногда применяются к неправильному формату файла. Из-за того, что некоторые методы сжатия данных несовместимы друг с другом, хранение смешанных файлов часто может ухудшить компонент файла. Например, файл изображения со сжатым текстом может показывать ухудшение читаемости текста после восстановления. Сканеры и программное обеспечение, которые используют грамматическую индукцию, могут извлечь смысл из текста, хранящегося вместе с файлами изображений, применяя так называемый скрытый семантический анализ (LSA).

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