Теория информации говорит нам о том, что можно уменьшить занимаемый данными объем путем их кодирования. В примере с разреженной матрицей мы сжали представление номера столбца с 32 до 16 бит, а затем и до 8 бит. На заре эры персональных компьютеров я написал программу, которая тратила большую часть времени на чтение и запись длинных последовательностей десятичных чисел. Я изменил программу так, чтобы кодировать две десятичные цифры а и b в одном байте (вместо обычных двух), вычисляя значение этого байта по формуле с = 10 * а + Ь. Затем исходные цифры можно было восстановить двумя операциями:
а = с / 10
b = с % 10
Эта простая схема вдвое уменьшила время ввода и вывода данных, а заодно позволила вдвое сократить размер файла с данными, который стал умещаться на одной дискете вместо прежних двух. Таким образом, кодирование может уменьшить объем памяти, занимаемый записями, но записи уменьшенного объема могут требовать больше времени на кодирование и декодирование (см. задачу 6 в конце главы).
Теория информации позволяет сжать поток записей, передаваемый по какому- либо каналу, такому как поток чтения/записи файла или сетевое соединение. Запись звука с уровнем качества компакт-диска требует двух каналов с 16-разрядным представлением уровня и частотой дискретизации 44 100 Гц. Одна секунда в этом представлении занимает 176 400 байт. Стандарт MP3 позволяет сжимать типичные звуковые файлы (в особенности музыку) во много раз. В задаче 10 вам предлагается определить эффективность некоторых широко используемых форматов представления текста, изображений, звуков и т. п. Некоторые программисты снабжают свои программы специальными алгоритмами сжатия. В разделе 13.8 (глава 13) данной книги описано сжатие файла с 75 000 английских слов до объема 52 Кбайт.
Главная
Каталог файлов
