{20, 20, 20, 20, 99, 68, 31,
40, 40, 40, 40, 40, 40, 40, 40, . .
который можно кодировать следующим образом:
{4, 20, -3, 99, 68, 31, 8, 40, . . . }, откуда видно, что значение 20 встречается 4 раза, затем идет 3 неповторяющихся значения 99, 68 и 31, за которыми, в свою очередь, следует 8 чисел 40. В приведенном примере кодирования первые 15 байт входного файла сжимаются в 8 байт.
КОДИРОВАНИЕ LZW
Метод кодирования, разработанный Лемпелем (Lempel), Зивом (Ziv) и Уэлшем (Welch), является модификацией ранних алгоритмов распознавания шаблонов LZ, LZ77 и LZ78. В схеме LZW повторяющиеся шаблоны в файле изображения заменяются кодом. Например, следующий список из 12 значений содержит два вхождения каждого шаблона {128, 96} и {200, 30, 10}:
{128, 96, 200, 30, 10, 128, 96, 50, 240, 200, 30, 10, . . . }.
Два данных шаблона можно заменить кодами cl и с2, а оставшийся шаблон {50, 240} соотнести с кодом сЗ. При этом 12 первых значений входного файла сокращаются до следующих 5 байт.
{cl, с2, cl, сЗ, с2, . . . }
1049
Альтернативно любую неповторяющуюся последовательность значений, такую как {50, 240}, можно записать в сжатом файле без присвоения кода.
По сути, алгоритм Ь2\¥ выполняет поиск повторяющихся последовательностей и строит таблицу таких последовательностей вместе с кодами, присвоенными им. Получающиеся таким образом схемы кодирования называются замещающими алгоритмами или алгоритмами со словарем. Впоследствии сжатый файл декодируется по кодовой таблице.
ДРУГИЕ МЕТОДЫ -ЖАТИЯ НА О-НОВЕ РА-ПОЗНАВАНИЯ ШАБЛОНОВ
-хемы распознавания шаблонов можно использовать для выделения повторений определенных черно-белых или цветных (ЯОВ) комбинаций в файле изображения. Чтобы еще больше сократить размер файлов изображений, можно обнаружить и закодировать дублирующиеся строки развертки и другие шаблоны. Кроме того, для получения небольших кодированных самоподобных наборов кодов цвета можно использовать фрактальные методы.
КОДИРОВАНИЕ ХАФФМАНА
-жатие файла часто дополнятся кодированием Хаффмана - для записи значений в файле изображения используется код переменной длины. При кодировании Хаффмана самый короткий код присваивается наиболее часто встречающемуся в файле значению, а самый длинный - наименее часто встречающемуся.
Основной принцип алгоритма Хаффмана тот же, что и в азбуке Морзе, в которой буквам алфавита сопоставляются символьные коды переменной длины. Буквам с высокой частотой появления в схеме Морзе присваиваются односимвольные коды, а редко встречающимся - четырехсимвольные коды. Например, буква “Е” кодируется как “точка” (•), буква “Т” кодируется как “тире” (-), а буква “<3” кодируется как четырехсимвольная последовательность из одной точки и трех тире(-- - )*. В коде Хаффмана используются не символьные, а битовые коды переменной длины, которые сопоставляются со значениями в файле изображения и позволяют добиваться больших коэффициентов сжатия.