Алгоритмы сжатия, использующие исключение повторов
Алгоритмы сжатия, использующие исключение повторов (RLE = Run-Length Encoding) чрезвычайно просты и ориентированы на быстрое сжатие данных, содержащих много идущих подряд одинаковых символов.
В основу алгоритмов RLE положен принцип выявления групп подряд идущих одинаковых символов и замены их структурой, в которой указывается код символа и число повторов, т.е. группа идущих подряд одинаковых символов заменяется на пару кодов вида <код символа; число 13 повторов>. Максимальное число одинаковых символов, которое можно закодировать одной такой парой, определяется длиной кода числа повторов.
В качестве примера рассмотрим реализацию RLE а графическом формате PCX. Группа повторяющихся байтов заменяется на байт-счетчик и байт данных. В байте-счетчике старшие два бита содержат единицы, в младших шести битах хранится число повторов. Неповторяющиеся значения, меньшие 0C0h = 0C016 = 110000002, записываются в сжатые данные без изменений. Для неповторяющихся значений, больших 0C016 = 110000002, (т.е. с двумя единицами в старших разрядах) такой подход недопустим, так как при распаковке такой байт будет восприниматься как байт-счетчик повторов. Поэтому такие байты при записи в сжатый поток предваряются байтом-счетчиком с числом повторов, равным единице (11000001 = С116).
Проблему при сжатии алгоритмами RLE представляют данные, содержащие незначительное количество повторяющихся символов. К одиночным символам также приходится добавлять счетчик повторов, что вместо сжатия дает увеличение объема данных. Поэтому в практических реализациях алгоритмы RLE несколько усложняются, чтобы уменьшить увеличение объема сжатых данных в случае не очень подходящих данных.
Пример. Сжатие
Исходные данные: 01BD2F154FDBE01015FDEO1ED1001A0A 10 1C 61 EF 01 D0 11 33 33 33 33 33 33 33 34
Последовательно проверяем каждый байт, и формируем сжатый поток согласно алгоритму RLE.
01 – первый байт исходных данных. Следующий за ним байт BD, это означает, что первый байт не входит в цепочку повторяющихся байтов.
Старшие два бита байта 01 не равны единицам. Следовательно, первый байт исходных данных переписываем в сжатый поток без изменений.
BD 2F 15 4F – следующие за первым байты, аналогично первому, переписываем в сжатый поток без изменения.
Два следующих байта DB16=110110112 и E016=111000002 – это байты, старшие два бита которых содержат единицы. Поэтому, эти байты, при записи в сжатый поток, предваряем байтами-счетчиками, с числом повторов равным единице (C116=110000012).
10 15 – эти байты не содержат единицы в старших битах и не входят в цепочку повторяющихся байтов. Переписываем их в сжатый поток без изменения.
Два следующих бита FD16=111111012 E016=111000002 – это байты, старшие два бита которых содержат единицы. Поэтому, эти байты, при записи в сжатый поток, предваряем байтами-счетчиками, с числом повторов равным единице (C116=110000012).
1E – этот байт не содержит единиц в старших битах и не входит в цепочку повторяющихся байтов. Переписываем его в сжатый поток без изменения.
Следующий байт D116=110100012 – это байт, старшие два бита которого содержат единицы. Поэтому, этот байт, при записи в сжатый поток, предваряем байтом-счетчиком, с числом повторов равным единице (C116=110000012).
00 1A 0A 10 1C 61 – эти байты не содержат единицы в старших битах и не входят в цепочку повторяющихся байтов. Переписываем их в сжатый поток без изменения.
Следующий байт EF16=111011112 – это байт, старшие два бита которого содержат единицы. Поэтому, этот байт, при записи в сжатый поток, предваряем байтом-счетчиком, с числом повторов равным единице (C116=110000012).
01 – этот байт не содержит единиц в старших битах и не входит в цепочку повторяющихся байтов. Переписываем его в сжатый поток без изменения.
Следующий байт D016=110100002 – это байт, старшие два бита которого содержат единицы. Поэтому, этот байт, при записи в сжатый поток, предваряем байтом-счетчиком, с числом повторов равным единице (C116=110000012).
11 – этот байт не содержит единиц в старших битах и не входит в цепочку повторяющихся байтов. Переписываем его в сжатый поток без изменения.
Далее идёт группа повторяющихся байтов 33 33 33 33 33 33 33, её заменяем на байт-счетчик и байт данных C7 33.
Последний байт 34 не содержит единицы в старших битах, переписываем его в сжатые данные без изменения.
Сжатые данные: 01 BD 2F 15 4F C1 DB C1 E0 10 15 C1 FD C1 EO 1E C1 D1 00 1A 0A 10 1C 61 C1 EF 01 C1 D0 11 C7 33 34
Пример 2 выполнения РАСПАКОВКА
Сжатые данные: 01 10 11 A2 B2 C2 D2 C1 FF D3 21
Последовательно проверяем каждый байт.
01 10 11 А2 B2 – не являются байтами-счетчиками, их записываем в распакованные данные без изменения.
Следующий байт С216=110000102 – это байт-счетчик (с числом повторов равным двум), байт значения которого D2. В распакованные данные записываем D2 D2.
Затем идет С1 – это байт-счетчик (с числом повторов равным единице), байт значения которого FF. В распакованные данные записываем FF.
D3 – это байт-счетчик (т.к. D316=110100112, с числом повторов равным 0100112=1910), байт, значение которого 21. В распакованные данные записываем девятнадцать раз байт 21.
Распакованные данные: 01 10 11 A2 B2 D2 D2 FF 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21