10.7. Понятие о сжатии информации

В теории кодирования рассматривают сжатие без потери информации и сжатие с потерей информации, когда эта потеря несущественна, то есть когда потерянной информацией можно пренебречь [26, 36]. В настоящее время для кодирования буквенно-цифровой информации применяют так называемый американский стандартный код ASCII, когда используется байт, например, для кодирования каждой буквы или символа. В обычном тексте частота появления букв различная. Поэтому для сжатия текста можно закодировать часто встречающиеся символы более короткой последовательностью битов (менее 8), а редко встречающиеся символы могут кодироваться и более чем восемью битами. Кроме того, в обычном тексте, как правило, встречается менее чем 2⁸=256 символов. Если кодировать не буквы, а слова, то двумя байтами можно закодировать 2¹⁶=65536 слов. Этого более чем достаточно, ведь, как правило, в слове больше двух букв. Сейчас переходят на двухбайтное кодирование.

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

На учете этих факторов основаны алгоритмы группового кодирования.

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