|
Попробуйте упаковать
Методы сжатия информации часто делят на два класса: с потерями (такие способы применяются, например, для упаковки изображений) и без потерь [1—4]. В первом случае при сжатии часть исходной информации отбрасывается либо изменяется. После таких операций полностью воспроизвести исходные данные уже не представляется возможным. Во втором случае их можно восстановить в первоначальном виде.(Разумеется, методы первой группы нельзя использовать, например, для сжатия файлов программ.)
Одна из первых — и весьма распространенных — схем сжатия без потерь реализуется с помощью алгоритма Хаффмана.
Текстовые файлы, с которыми пользователи персональных компьютеров встречаются практически ежедневно, со стоят из алфавитно-цифровых символов и «невидимых» кодов управления (перевод строки, возврат каретки и т.п.). Каждый такой символ в таблице кодов ASCII представлен одним байтом, и при подобном кодировании частота, с которой символы встречаются в тексте, не учитывается. Алгоритм Хаффмана основан на довольно простом принципе: символы заменяются кодовыми последовательностями различной длины — чем чаще употребляется символ, тем короче должна быть кодовая последовательность (алгоритм Хаффмана называют еще кодированием символами переменной длины). Так, в английском тексте часто встречающимся буквам «А», «Е», «Т» можно поставить в соответствие последовательности из трех бит, а буквам «J», «Q», «Z» — последовательности из восьми бит [1]. В одних вариантах реализации алгоритма Хаффмана употребляются готовые кодовые таблицы (здесь можно вспомнить азбуку Морзе), а в других кодовая таблица строится только на основе статистического анализа информации.
Алгоритм Лемпеля — Зива (LZ), предложенный в 1977 году, основан
на поиске и кодировании избыточной информации. Однако тут кодируются не отдельные символы, как в алгоритме Хаффмана, а последовательности символов. На его основе потом было создано множество методов сжатия информации (LZ-алгоритмы). Программа, реализующая LZ-алгоритм, просматривает данные и выполняет статистический анализ для построения |
своей кодовой таблицы или словаря (методы сжатия этой группы употребляются, например, в утилитах PKZIP, WinZIP, ARJ, LHARC и некоторых других программах-упаковщиках) [1, 3—5]. Через несколько лет появился усовершенствованный вариант алгоритма — алгоритм Лемпеля — Зива - Уэлча (LZW). В 1987 году на основе алгоритма LZW в компании CompuServe был создан формат GIF (Graphics Interchange Format — формат обмена графическими файлами) [4, 6—8]. Алгоритм RLE (Run Length Encoding—»групповое» кодирование) первоначально разрабатывался специально для хранения графической информации. Метод основан на представлении последовательности одинаковых байтов в виде двух величин.
Одна из них равна количеству повторяющихся символов, а другая представляет собой код этого символа. Например, строка из семи букв «А», трех букв «В» и четырех букв «С» (АААААААВВВСССС) может быть записана в виде 7АЗВ4С, что дает существенное сокращение ее длины. Данный метод применяется, в частности, для сжатия файлов графического формата PCX. Усовершенствованный алгоритм RLE используется в одном из вариантов формата TIFF и в формате TGA. В начале 1990-х годов Объединенной группой экспертов в области фотографии (Joint Photographic Experts Group, JPEG) была предложена схема сжатия, которая впоследствии получила всеобщее признание как стандартный метод сжатия неподвижных изображений. Он получил название JPEG. В основе алгоритма лежит известная математическая операция — дискретное преобразование Фурье, с |
помощью которого на основании выбранного «коэффициента качества» определяется требуемое соотношение сжатия и потерь изображения [4, 6]. Кодирование по Хаффману вместе с RLE употребляется как составная часть алгоритма — для дополнительного сжатия изображения.
JPEG уже 10 лет используется как основной алгоритм сжатия графической информации с потерями. К примеру, когда появились первые графические браузеры (программы просмотра web-страниц), JPEG стал главным методом сжатия для сети Интернет, а после появления цифровых фотокамер он стал широко применяться в этих устройствах.
Существуют и другие алгоритмы упаковки, в том числе специальные алгоритмы сжатия движущихся изображений. В 1990-м году появились первые компьютерные алгоритмы фрактального сжатия изображений [4]. В 1994 году впервые было дано описание быстро завоевывающего сейчас популярность алгоритма сжатия информации на основе преобразования Бэрроуза — Уилера (Burrows — Wheeler Transform, BWT) [5]. Еще одним перспективным направлением является сжатие на основе так называемых нейронных сетей...
Литература
1. Борзенко А.Е., Федоров А.Г. Мультимедиа для всех. Изд. 2-е. М.: КомпьютерПресс, 1996.
2. Фафенбергер Б., Уолл Д. Толковый словарь по компьютерным технологиям и Internet: Пер. с англ. Изд. 6-е. Киев: Диалектика. 1996.
3. PKZIP и PKUNZIP // Информатика, Ns 46/99.
4. Васильев А. Сжатие изображений: вчера, сегодня, завтра // Hard'n'Soft, № 4/2001.
5. Юкин В. Операция BWT, или Новые методы сжатия // Hard'n'Soft, №4/2001.
6. Шниер М. Толковый словарь компьютерных технологий: Пер. с англ. Киев: ДиаСофт, 2000.
7. Мостицкий И.Л. Новейший англо-русский толковый словарь по современной электронной технике. М.: ЛУЧШИЕ КНИГИ, 2000.
8. Пройдаков Э.М., Теплицкий Л.А. Англо-русский толковый словарь по вычислительной технике, Интернету и программированию. Изд. 2-е, испр. и доп. М.: Издательско-торговый дом «Русская редакция», 2000. |
