Интернет магазин китайских планшетных компьютеров

Компьютеры - Сжатие без потерь - Техника сжатия без потерь

В общих чертах смысл сжатия без потерь таков. В исходных данных находят какую-либо закономерность и с учётом этой закономерности генерируют вторую последовательность, которая полностью описывает исходную. Например, для кодирования двоичных последовательностей, в которых много нулей и мало единиц, мы можем использовать такую замену:

00 → 0
01 → 10
10 → 110
11 → 111

В таком случае шестнадцать битов

00 01 00 00 11 10 00 00

будут преобразованы в тринадцать битов

0 10 0 0 111 110 0 0

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

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

Статистические модели алгоритмов для текста включают:

• Преобразование Барроуза — Уилера
• LZ77 и LZ78
• LZW

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

• Алгоритм Хаффмана
• Арифметическое кодирование