Уэлча), Хаффмана. Особенности применения алгоритма Хаффмана в факсимильной связи

Методы сжатия информации часто делят на два класса: с потерями (такие способы применяются, например, для упаковки изображений) и без потерь [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 (GraphicsInterchangeFormat — формат обмена графическими файлами) [4, 6 — 8].
Алгоритм RLE (RunLengthEncoding— “групповое” кодирование) первоначально разрабатывался специально для хранения графической информации. Метод основан на представлении последовательности одинаковых байтов в виде двух величин [1, 6]. Одна из них равна количеству повторяющихся символов, а другая представляет собой код этого символа. Например, строка из семи букв “А”, трех букв “В” и четырех букв “С” (АААААААВВВСССС) может быть записана в виде 7А3В4С, что дает существенное сокращение ее длины. Данный метод применяется, в частности, для сжатия файлов графического формата PCX. Усовершенствованный алгоритм RLE используется в одном из вариантов формата TIFF и в формате TGA.
В начале 1990-х годов Объединенной группой экспертов в области фотографии (JointPhotographicExpertsGroup, JPEG) была предложена схема сжатия, которая впоследствии получила всеобщее признание как стандартный метод сжатия неподвижных изображений. Он получил название JPEG. В основе алгоритма лежит известная математическая операция — дискретное преобразование Фурье, с помощью которого на основании выбранного “коэффициента качества” определяется требуемое соотношение сжатия и потерь изображения [4, 6]. Кодирование по Хаффману вместе с RLE употребляется как составная часть алгоритма — для дополнительного сжатия изображения.
JPEG уже 10 лет используется как основной алгоритм сжатия графической информации с потерями. К примеру, когда появились первые графические браузеры (программы просмотра web-страниц), JPEG стал главным методом сжатия для сети Интернет, а после появления цифровых фотокамер он стал широко применяться в этих устройствах.
Существуют и другие алгоритмы упаковки, в том числе специальные алгоритмы сжатия движущихся изображений. В 1990-м году появились первые компьютерные алгоритмы фрактального сжатия изображений [4]. В 1994 году впервые было дано описание быстро завоевывающего сейчас популярность алгоритма сжатия информации на основе преобразования Бэрроуза — Уилера (Burrows — Wheeler Transform, BWT) [5]. Еще одним перспективным направлением является сжатие на основе так называемых нейронных сетей...