Каковы алгоритмы сжатия данных?

Алгоритмы сжатия данных

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

Принципы сжатия данных

В основе любого метода сжатия лежит простой логический принцип. Допустим, элементы, которые встречаются довольно часто, кодируются коротко, а те, которые встречаются реже - обозначают длинными кодами. Значит, для хранения данных потребуется места меньше, чем для представления кодов одной длины: подробнее об этом можно узнать на http://pmbk.ru.

Running –простейший алгоритм. Например, строка текста имеет в конце много пробелов, то есть избыточность информации очевидна. Чтобы сжать строку следует сжать пробелы, упаковав их по методу повторения символов. Таким образом, первый байт фактически остается пробелом, а второй указывает на то, что при восстановлении строки следует развернуть предыдущий файл.

Huffman. Несмотря на то, что изначально кажется, что создать файл меньшего размера из исходного без исключения повторов или кодировки последовательности - нереальная задача, алгоритм Хоффмана доказывает обратное. Входной файл следует читать два раза: первый раз подсчитываются частоты вхождения символов , второй – кодировка.

LZW – алгоритм кодирования последовательность символов, которые не одинаковые. При повторении строк в файле, их можно закодировать в таблицу. Преимущество такого алгоритма – отсутствие необходимости включения таблицы кодировки в сжатые файлы. В отличие от алгоритма Хоффмана, сжатие LZW – однопроходная операция.

Сжатие без потерь: основные методы

Основными вариантами построения алгоритмов сжатия являются следующие группы:

1. Преобразование потока. Происходит описание новых несжатых данных через обработанные. Кодирование символов осуществляется исключительно на основе уже обработанных данных. Второе и последующие вхождения подстроки следует заменить ссылками на первое вхождение.

2. Статическое сжатие. В данной группе могут использоваться блочные и адаптивные методы. При блочном сжатии статистика блока данных исчисляется отдельно и добавляется к уже сжатому блоку (арифметическое кодирование). В случае с адаптивным сжатием вероятности вычисления новых данных основываются на данных, уже обработанных при кодировании.

3. Преобразование блока. Данный метод сжатия основан на следующем действии: входящая информация разбивается поблочно, а затем трансформируется в единое целое. Иногда методы с перестановкой блоков могут уменьшить объем данных. Тем не менее, подобная обработка улучшает структуру данных.

Виды сжатия данных

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

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