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

ПОПРОБУЙТЕ

УПАКОВАТЬ

Методы сжатия информации час­то делят на два класса: с потерями (такие способы применяются, напри­мер, для упаковки изображений) и без потерь [1—4]. В первом случае при сжатии часть исходной инфор­мации отбрасывается либо изменя­ется. После таких операций полнос­тью воспроизвести исходные данные уже не представляется возможным. Во втором случае их можно восста­новить в первоначальном виде. (Ра­зумеется, методы первой группы нельзя использовать, например, для сжатия файлов программ.)

Одна из первых — и весь­ма распространенных — схем сжатия без потерь реализу­ется с помощью алгоритма Хаффмана.

Текстовые файлы, с которыми пользо­ватели персональных компьютеров встречаются практически ежедневно, состоят из алфавитно-цифровых символов и "невидимых" кодов управления (перевод строки, возврат каретки и т.п.). Каждый такой символ в (таблице кодов ASCII пред­ставлен одним байтом, и при подобном кодировании частота, с которой символы встречаются в тексте, не учитывается. Алгоритм Хаффмана основан на довольно простом принципе: символы заменяются кодовыми последовательностями различной дли­ны — чем чаще употребляется сим­вол, тем короче должна быть кодовая последовательность (алгоритм Хаффмана называют еще кодирова­нием символами переменной длины). Так, в английском тексте часто встре­чающимся буквам "А", "Е", "Т" можно поставить в соответствие после­довательности из трех бит, а буквам "J", "Q", "Z" — последовательности из восьми бит [1]. В одних вариантах реализации алгоритма Хаффмана упот­ребляются готовые кодовые таблицы (здесь можно вспомнить азбуку Мор­зе), а в других кодовая таблица стро­ится только на основе статистическо­го анализа информации.

Алгоритм Лемпеля — Зива (LZ), предложенный в 1977 году, основан на поиске и кодировании избыточ­ной информации. Однако тут коди­руются не отдельные символы, как в алгоритме Хаффмана, а последова­тельности символов. На его основе потом было создано множество ме­тодов сжатия информации (LZ-алго- ритмы). Программа, реализующая LZ-алгоритм, просматривает данные и выполняет статистический анализ для построения своей кодовой таб­лицы или словаря (методы сжатия этой группы употребляются, напри­мер, в утилитах PKZIP, WinZlP, ARJ, LHARC и некоторых других про­граммах-упаковщиках) [1, 3—5].

Через несколько лет появил­ся усовершенствованный вариант алгоритма — ал­горитм Лемпеля — Зива - Уэлча (LZW). В 1987 году на основе алгоритма LZW в компании Compu­Serve был создан формат GIF (Gra­phics Interchange Format — формат обмена графическими файлами) [4, 6—8].

Алгоритм RLE (Run Length Encoding — "групповое" кодирование) первоначально разрабатывался спе­циально для хранения графической информации. Метод основан на представлении последовательности одинаковых байтов в виде двух ве­личин [1, 6]. Одна из них равна ко­личеству повторяющихся символов, а другая представляет собой код это­го символа. Например, строка из семи букв "А", трех букв "В" и четы­рех букв "С" (АААААААВВВСССС) может быть записана в виде 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 Tran­sform, 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.