Попробуйте упаковать

    Методы сжатия информации часто делят на два класса: с потерями (такие способы применяются, например, для упаковки изображений) и без потерь [1—4]. В первом случае при сжатии часть исходной информации отбрасывается либо изменяется. После таких операций полностью воспроизвести исходные данные уже не представляется возможным. Во втором случае их можно восстановить в первоначальном виде. (Разумеется, методы первой группы нельзя использовать, например, для сжатия файлов программ.)
    Одна из первых — и весьма распространенных — схем сжатия без потерь реализуется с помощью алгоритма Хаффмана.
    Текстовые файлы, с которыми пользователи персональных компьютеров встречаются практически ежедневно, состоят из алфавитноцифровых символов и “невидимых” кодов управления (перевод строки, возврат каретки и т.п.). Каждый такой символ в таблице кодов ASCII представлен одним байтом, и при подобном кодировании частота, с которой символы встречаются в тексте, не учитывается. Алгоритм Хаффмана основан на довольно простом принципе: символы заменяются кодовыми последовательностями различной длины — чем чаще употребляется символ, тем короче должна быть кодовая последовательность (алгоритм Хаффмана называют еще кодированием символами переменной длины). Так, в английском тексте часто встречающимся буквам “A”, “E”, “T” можно поставить в соответствие последовательности из трех бит, а буквам “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 — “групповое” кодирование) первоначально разрабатывался специально для хранения графической информации. Метод основан на представлении последовательности одинаковых байтов в виде двух величин [1, 6]. Одна из них равна количеству повторяющихся символов, а другая представляет собой код этого символа. Например, строка из семи букв “А”, трех букв “В” и четырех букв “С” (АААААААВВВСССС) может быть записана в виде 7А3В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 // Информатика, № 46/99.
    4. Васильев А. Сжатие изображений: вчера, сегодня, завтра // Hard‘n’Soft, № 4/2001.
    5. Юкин В. Операция BWT, или Новые методы сжатия // Hard‘n’Soft, № 4/2001.
    6. Шниер М. Толковый словарь компьютерных технологий: Пер. с англ. Киев: ДиаСофт, 2000.
    7. Мостицкий И.Л. Новейший англо-русский толковый словарь по современной электронной технике. М.: ЛУЧШИЕ КНИГИ, 2000.
    8. Пройдаков Э.М., Теплицкий Л.А. Англо-русский толковый словарь по вычислительной технике, Интернету и программированию. Изд. 2-е, испр. и доп. М.: Издательско-торговый дом “Русская редакция”, 2000.

TopList