Кодирование длин серий (англ. Run-length encoding, RLE) или Кодирование повторов - простой алгоритм сжатия данных, который оперирует сериями данных, то есть последовательностями, в которых один и тот же символ встречается несколько раз подряд. При кодировании строка одинаковых символов, составляющих серию, заменяется строкой, которая содержит сам повторяющийся символ и количество его повторов.
Характеристики алгоритма RLE:
Коэффициенты компрессии : Первый вариант: 32, 2, 0,5. Второй вариант: 64, 3, 128/129. (Лучший, средний, худший коэффициенты). Класс изображений : Ориентирован алгоритм на изображения с небольшим количеством цветов: деловую и научную графику. Симметричность: Примерно единица.
Характерные особенности : К положительным сторонам алгоритма, пожалуй, можно отнести только то, что он не требует дополнительной памяти при архивации и разархивации, а также быстро работает. Интересная особенность группового кодирования состоит в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.
Первый вариант алгоритма
Данный алгоритм необычайно прост в реализации. Групповое кодирование - от английского Run Length Encoding (RLE) - один из самых старых и самых простых алгоритмов архивации графики. Изображение в нем (как и в нескольких алгоритмах, описанных ниже) вытягивается в цепочку байт по строкам растра. Само сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт. Замена их на пары <счетчик повторений, значение > уменьшает избыточность данных.
Алгоритм рассчитан на деловую графику - изображения с большими областями повторяющегося цвета. Ситуация, когда файл увеличивается, для этого простого алгоритма не так уж редка. Ее можно легко получить, применяя групповое кодирование к обработанным цветным фотографиям. Для того чтобы увеличить изображение в два раза, его надо применить к изображению, в котором значения всех пикселов больше двоичного 11000000 и подряд попарно не повторяются.
Второй вариант алгоритма
Второй вариант этого алгоритма имеет больший максимальный коэффициент архивации и меньше увеличивает в размерах исходный файл.
Название алгоритм получил по первым буквам фамилий его разработчиков - Lempel , Ziv и Welch .
LZW-алгоритм основан на идее расширения алфавита, что позволяет использовать дополнительные символы для представления строк обычных символов. Используя, например, вместо 8-битовых ASCII-кодов 9-битовые, вы получаете дополнительные 256 символов. Работа компрессора сводится к построению таблицы, состоящей из строк и соответствующих им кодов. Алгоритм сжатия сводится к следующему: программа прочитывает очередной символ и добавляет его к строке. Если строка уже находится в таблице, чтение продолжается, если нет, данная строка добавляется к таблице строк. Чем больше будет повторяющихся строк, тем сильнее будут сжаты данные. Возвращаясь к примеру с телефоном, можно, проведя весьма упрощенную аналогию, сказать, что, сжимая запись 233 34 44 по LZW-методу, мы придем к введению новых строк - 333 и 444 и, выражая их дополнительными символами, сможем уменьшить длину записи.
Характеристики алгоритма LZW: Коэффициенты компрессии : Примерно 1000, 4, 5/7 (Лучший, средний, худший коэффициенты). Сжатие в 1000 раз достигается только на одноцветных изображениях размером кратным примерно 7 Мб. Класс изображений : Ориентирован LZW на 8-битные изображения, построенные на компьютере. Сжимает за счет одинаковых подцепочек в потоке. Симметричность : Почти симметричен, при условии оптимальной реализации операции поиска строки в таблице.
Характерные особенности : Ситуация, когда алгоритм увеличивает изображение, встречается крайне редко. LZW универсален - именно его варианты используются в обычных архиваторах.
Процесс сжатия выглядит достаточно просто. Мы считываем последовательно символы входного потока и проверяем, есть ли в созданной нами таблице строк такая строка. Если строка есть, то мы считываем следующий символ, а если строки нет, то мы заносим в поток код для предыдущей найденной строки, заносим строку в таблицу и начинаем поиск снова.
Особенность LZW заключается в том, что для декомпрессии не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов.
Первый вариант алгоритма
Данный алгоритм необычайно прост в реализации. Кодирование длин повторов - от английского Run Length Encoding (RLE) - один из самых старых и самых простых алгоритмов архивации графики. Изображение в нем (как и в нескольких алгоритмах, описанных ниже) вытягивается в цепочку байтов по строкам растра. Само сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байтов. Замена их на пары <счетчик повторений, значение> уменьшает избыточность данных.
Алгоритм декомпрессии при этом выглядит так:
Initialization(...); do {
byte = ImageFile.ReadNextByte(); if(является счетчиком(byte)) { counter = Low6bits(byte)+1; value = ImageFile.ReadNextByte(); for(i=l to counter)
DecompressedFile.WriteByte(value))
DecompressedFile.WriteByte(byte)) while (UmageFile.EOF ()) ;
В данном алгоритме признаком счетчика (counter) служат единицы в двух верхних битах считанного файла:
Соответственно оставшиеся 6 бит расходуются на счетчик, который может принимать значения от 1 до 64. Строку из 64 повторяющихся байт мы превращаем в 2 байта, т. е. сожмем в 32 раза.
Упражнение. Составьте алгоритм компрессии для первого варианта алгоритма RLE.
Алгоритм рассчитан на деловую графику - изображения с большими областями повторяющегося цвета. Ситуация, когда файл увеличивается, для этого простого алгоритма не так уж редка. Ее можно легко получить, применяя групповое кодирование к обработанным цветным фотографиям. Для того чтобы увеличить изображение в 2 раза, его надо применить к изображению, в котором значения всех пикселов больше двоичного 11000000 и подряд попарно не повторяются.
Упражнение. Предложите 2-3 примера "плохих" изображений для алгоритма RLE. Объясните, почему размер сжатого файла больше размера исходного файла.
Данный алгоритм реализован в формате PCX. См. пример в приложении 2.
Второй вариант алгоритма
Второй вариант этого алгоритма имеет большую максимальную степень сжатия и меньше увеличивает в размерах исходный файл. Алгоритм декомпрессии для него выглядит так:
Initialization(...); do {
byte = ImageFile.ReadNextByte(); counter = Low7bits(byte)+1; if(если признак повтора(byte)) { value = ImageFile.ReadNextByte(); for (i=l to counter)
CompressedFile.WriteByte(value)
for(i«=l to counter) {
value = ImageFile.ReadNextByte(); CompressedFile.WriteByte(value) } } while (! ImageFile.EOFO) ;
Признаком повтора в данном алгоритме является единица в старшем разряде соответствующего байта:
j 0 7 бит___ I Что пропускать I ... Что пропускать I
^ 1 7 бит I Что повторять I
Как можно легко подсчитать, в лучшем случае этот алгоритм сжимает файл в 64 раза (а не в 32 раза, как в предыдущем варианте), в худшем увеличивает на 1/128. Средние показатели степени компрессии данного алгоритма находятся на уровне показателей первого варианта.
(Эч Упражнение. Составьте алгоритм компрессии для второго варианта алгоритма RLE.
Похожие схемы компрессии использованы в качестве одного из алгоритмов, поддерживаемых форматом TIFF, а также в формате TGA.
Характеристики алгоритма RLE:
Степени сжатия: первый вариант: 32, 2, 0,5. Второй вариант: 64, 3, I 128/129. (Лучшая, средняя, худшая степени).
Класс изображений: ориентирован алгоритм на изображения с не-I большим количеством цветов: деловую и научную графику.
Симметричность: примерно единица.
Характерные особенности: к положительным сторонам алгоритма, по-I жалуй, можно отнести только то, что он не требует дополнительной памяти \ при архивации и разархивации, а также быстро работает. Интересная особен-! ность группового кодирования состоит в том, что степень архивации для не-! которых изображений может быть существенно повышена всего лишь за i счет изменения порядка цветов в палитре изображения.
ПРОФИЛЬ При сжатии с помощью алгоритма RLE сначала записывается количество повторений первого символа, затем сам первый символ, затем количество повторений второго символа и т.д. В данном случае весь закодированный файл занимает 4 байта: 011 00100 2 11 000000 2 011 00100 2 11 000001 2 100 A (код 192) 100 Б (код 193) Таким образом, мы сжали файл в 50 раз за счет того, что в нем снова была избыточность - цепочки одинаковых символов. Это сжатие без потерь, потому что, зная алгоритм упаковки, можно восстановить исходные данные из кода. Очевидно, что такой подход будет приводить к увеличению (в 2 раза) объема данных в том случае, когда в файле нет соседних одинаковых символов. Чтобы улучшить результаты RLE-кодирования даже в этом наихудшем случае, алгоритм модифицировали следующим образом. Упакованная последовательность содержит управляющие байты, за каждым управляющим байтом следует один или несколько байтов данных. Если старший бит управляющего байта равен 1, то следующий за управляющим байт данных при распаковке нужно повторить столько раз, сколько записано в оставшихся 7 битах управляющего байта. Если же старший бит управляющего байта равен 0, то надо взять несколько следующих байтов данных без изменения. Сколько именно - записано в оставшихся 7 битах управляющего байта. Например, управляющий байт 1000011 1 2 говорит о том, что следующий за ним байт надо повторить 7 раз, а управляющий байт 00000100 2 - о том, что следующие за ним 4 байта надо взять без изменений. Так последовательность 100011 11 2 11 000000 2 00000010 2 11 000001 2 11 000010 2 повтор 15 A (код 192) 2 Б (код 193) В (код 194) распаковывается в 17 символов: АААААААААААААААБВ. Алгоритм RLE успешно применялся для сжатия рисунков, в которых большие области закрашены одним цветом, и некоторых звуковых данных. Сейчас вместо него применяют более совершенные, но более сложные методы. Один из них (кодирование Хаффмана) мы рассмотрим ниже. Алгоритм RLE используется, например, на одном из этапов кодирования рисунков в формате JPEG. Возможность RLE-сжатия есть также в формате BMP (для рисунков с палитрой 16 или 256 цветов). Лучший способ понять принцип работы алгоритма - потренироваться в его использовании. С сайта автора (http://kpolyakov.narod.ru/prog/compress.htm) можно загрузить бесплатную программу-тренажер, которая предназначена для изучения алгоритма RLE: В левой части окна программы находится текстовый редактор. При нажатии на кнопку введенный текст сжимается с помощью алгоритма RLE, сжатые данные отображаются в виде шестнадцатеричных кодов в правой части окна. Окно в правой части - это тоже редактор, поэтому коды можно изменить и выполнить обратную операцию (распаковку, декомпрессию), нажав на кнопку. Кнопки в верхней части окна позволяют сжимать и восстанавливать файлы на диске. Нужно только учитывать, что программа использует свой собственный формат хранения данных. 6 декабрь 2012 / ИНФОРМАТИКА Контрольные вопросы 1) Оцените максимально достижимый коэффициент сжатия с помощью рассмотренного варианта RLEалгоритма. В каком случае его удастся достичь? 2) Оцените коэффициент сжатия с помощью RLE-алгоритма в худшем случае. Опишите этот худший случай. 3) Придумайте три последовательности, которые невозможно сжать с помощью алгоритма RLE. 4) Постройте последовательности, которые сжимаются алгоритмом RLE ровно в 2 раза, в 4 раза, в 5 раз. Практикум 1) Используя алгоритм RLE, закодируйте последовательность символов BBBBBBACCCABBBBBB Запишите результат в виде шестнадцатеричных кодов (каждый символ кодируется в виде байта, который представлен двумя шестнадцатеричными цифрами). Проверьте полученный результат с помощью программы RLE.
2) Декодируйте последовательность, упакованную с помощью алгоритма RLE (приводятся шестнадцатеричные коды): 01 4D 8E 41 01 4D 8E 41 16. Для определения символов по их шестнадцатеричным кодам используйте таблицу ASCII. Определите количество байтов в исходной и распакованной последовательности и вычислите коэффициент сжатия. Проверьте результат с помощью программы RLE. Предложите два способа проверки. 3) Используя программу RLE, примените RLEсжатие к следующим файлам 1 и найдите для каждого из них коэффициент сжатия. grad_vert.bmp grad_horz.bmp grad_diag.jpg Объясните полученные результаты: почему для двух рисунков в формате BMP одинакового размера коэффициенты сжатия по алгоритму RLE так сильно отличаются; почему не удается сжать рисунки, сохраненные в формате JPEG? Префиксные коды Вспомните азбуку Морзе, в которой для уменьшения длины сообщения используется неравномерный код - часто встречающиеся буквы (А, Е, М, Н, Т) кодируются короткими последовательностями, а редко встречающиеся - более длинными. Такой код можно представить в виде структуры, которая называется деревом: Корень Здесь показано неполное дерево кода Морзе, построенное только для символов, коды которых состоят из одного и двух знаков (точек и тире). Дерево состоит из узлов (черная точка и кружки с символами алфавита) и соединяющих их направленных ребер, стрелки указывают направление движения. Верхний узел (в который не входит ни одна стрелка) называется “корнем” дерева. Из корня и из всех промежуточных узлов (кроме конечных узлов - “листьев”) выходят две стрелки, левая помечена точкой, а правая - знаком “тире”. Чтобы найти код символа, нужно пройти по стрелкам от “корня” дерева к нужному “листу”, выписывая метки стрелок, по которым мы переходим. В дереве нет циклов (замкнутых путей), поэтому код каждого 1 Эти и другие файлы, использующиеся в заданиях практикума, находятся на диске-приложении к этому номеру журнала. символа определяется единственным образом. По этому дереву можно построить такие коды: Е И А – Т – Н – М – – Это неравномерный код, в нем символы имеют коды разной длины. При этом всегда возникает проблема разделения последовательности на отдельные кодовые слова. В коде Морзе она решена с помощью символа-разделителя - паузы. Однако можно не вводить дополнительный символ, если выполняется условие Фано: ни одно из кодовых слов не является началом другого кодового слова. Это позволяет однозначно декодировать сообщение в реальном времени, по мере получения очередных символов. Префиксный код - это код, в котором ни одно кодовое слово не является началом другого кодового слова (условие Фано). Роберт Фано (род. 1917) (nytimes.com) Клод Шеннон (1916–2001) Для использования этой идеи в компьютерной обработке данных нужно было разработать алгоритм построения префиксного кода. Впервые эту задачу решили, независимо друг от друга, американские математики и инженеры Клод Шеннон (в 1948 году) и Роберт Фано (в 1949 году) . Они использовали избыточность сообщений, состоящую в том, что символы в тексте имеют разные частоты встречаемости. В этом случае нужно читать данные исходного файла два раза: на первом проходе определяется частота встречаемости каждого символа, затем строится код с учетом этих данных, и на втором проходе символы текста заменяются на их коды. Алгоритм кодирования, предложенный Шенноном и Фано, получил название кода Шеннона - Фано. Пример 3. Пусть текст состоит только из букв О, Е, Н, Т и пробела. Известно, сколько раз они встретились в тексте: пробел - 179, О - 89, Е - 72, Н - 53 и Т - 50 раз. Следуя методу Шеннона - Фано, делим символы на две группы так, чтобы общее количество найденных в тексте символов первой группы было примерно равно общему количеству символов второй группы. В нашем случае лучший вариант - это объединить пробел и букву Т в первую группу (сумма 179+50 = 229), а остальные символы - во вторую (сумма 89+72+53 = 214). Символы первой группы будут иметь коды, начинающиеся с 0, а остальные - с 1. В первой группе всего два символа, у одного из них, например у пробела, вторая цифра кода будет 0 (и полный код 00), а у второго - 1 (код буквы Т - 01) . 7 декабрь 2012 / ИНФОРМАТИКА
Давным-давно, когда я был ещё наивным школьником, мне вдруг стало жутко любопытно: а каким же волшебным образом данные в архивах занимают меньше места? Оседлав свой верный диалап, я начал бороздить просторы Интернетов в поисках ответа, и нашёл множество статей с довольно подробным изложением интересующей меня информации. Но ни одна из них тогда не показалась мне простой для понимания - листинги кода казались китайской грамотой, а попытки понять необычную терминологию и разнообразные формулы не увенчивались успехом.
Поэтому целью данной статьи является дать представление о простейших алгоритмах сжатия тем, кому знания и опыт пока ещё не позволяют сходу понимать более профессиональную литературу, или же чей профиль и вовсе далёк от подобной тематики. Т.е. я «на пальцах» расскажу об одних из простейших алгоритмах и приведу примеры их реализации без километровых листингов кода.
Сразу предупрежу, что я не буду рассматривать подробности реализации процесса кодирования и такие нюансы, как эффективный поиск вхождений строки. Статья коснётся только самих алгоритмов и способов представления результата их работы.
Для многих гораздо привычней будет видеть эти данные в виде hex-дампа:
0000: 00 00 00 00 00 00 04 02 00 04 04 04 04 04 04 04
0010: 50 50 50 50 00 02 02 02 02 FF FF FF FF FF 00 00
Подумав, мы решили, что хорошо бы для экономии места как-то сжимать такие наборы. Для этого мы проанализировали их и выявили закономерность: очень часто попадаются подпоследовательности, состоящие из одинаковых элементов. Конечно же, RLE для этого подойдёт как нельзя кстати!
Закодируем наши данные, используя свежеполученные знания: 6×0, 4, 2, 0, 7×4, 4×80, 0, 4×2, 5×255, 2×0.
Пришло время как-то представить наш результат в понятном компьютеру виде. Для этого, в потоке данных мы должны как-то отделять одиночные байты от кодируемых цепочек. Поскольку весь диапазон значений байта используется нашими данными, то просто так выделить какие-либо диапазоны значений под наши цели не удастся.
Есть как минимум два выхода из этой ситуации:
Итак, теперь у нас имеется два вида последовательностей: цепочки одиночных элементов (вроде «4, 2, 0») и цепочки одинаковых элементов (вроде «0, 0, 0, 0, 0, 0»). Выделим в «служебных» байтах один бит под тип последовательности: 0 - одиночные элементы, 1 - одинаковые. Возьмём для этого, скажем, старший бит байта.
В оставшихся 7 битах мы будем хранить длины последовательностей, т.е. максимальная длина кодируемой последовательности - 127 байт. Мы могли бы выделить под служебные нужды, допустим, два байта, но в нашем случае такие длинные последовательности встречаются крайне редко, поэтому проще и экономичней просто разбивать их на более короткие.
Получается, в выходной поток мы будем писать сперва длину последовательности, а далее либо одно повторяемое значение, либо цепочку неповторяемых элементов указанной длины.
Первое, что должно броситься в глаза - при таком раскладе у нас есть парочка неиспользуемых значений. Не может быть последовательностей с нулевой длиной, поэтому мы можем увеличить максимальную длину до 128 байт, отнимая от длины единицу при кодировании и прибавляя при декодировании. Таким образом, мы можем кодировать длины от 1 до 128 вместо длин от 0 до 127.
Второе, что можно заметить - не бывает последовательностей одинаковых элементов единичной длины. Поэтому, от значения длины таких последовательностей при кодировании мы будем отнимать ещё единичку, увеличив тем самым их максимальную длину до 129 (максимальная длина цепочки одиночных элементов по-прежнему равна 128). Т.е. цепочки одинаковых элементов у нас могут иметь длину от 2 до 129.
Закодируем наши данные снова, но теперь уже и в понятном для компьютера виде. Будем записывать служебные байты как , где T - тип последовательности, а L - длина. Будем сразу учитывать, что длины мы записываем в изменённом виде: при T=0 отнимаем от L единицу, при T=1 - двойку.
0, , 4, 2, 0, , 4, , 80, , 0, , 2, , 255, , 0
Попробуем декодировать наш результат:
А теперь последний шаг: сохраним полученный результат как массив байт. Например, пара
, упакованная в байт, будет выглядеть вот так:
В итоге получаем следующее:
0000: 84
00 02
04 02 00 85
04 82
80 00
00 82
02 83
FF
0010: 80
00
Таким вот нехитрым образом на данном примере входных данных мы из 32 байт получили 18. Неплохой результат, особенно если учесть, что на более длинных цепочках он может оказаться гораздо лучше.
Дополнительная эффективность может быть достигнута путём использования эвристических методов кодирования. Например, закодируем нашим способом следующую цепочку: «ABBA». Мы получим « , A, , B, , A» - т.е. 4 байта мы превратили в 6, раздули исходные данные аж в полтора раза! И чем больше таких коротких чередующихся разнотипных последовательностей, тем больше избыточных данных. Если это учесть, то можно было бы закодировать результат как « , A, B, B, A» - мы бы потратили всего один лишний байт.
Основная идея заключается в том, чтобы кодировать одинаковые последовательности элементов. Т.е., если во входных данных какая-то цепочка элементов встречается более одного раза, то все последующие её вхождения можно заменить «ссылками» на её первый экземпляр.
Как и остальные алгоритмы этого семейства семейства, LZ77 использует словарь, в котором хранятся встречаемые ранее последовательности. Для этого он применяет принцип т.н. «скользящего окна»: области, всегда находящейся перед текущей позицией кодирования, в рамках которой мы можем адресовать ссылки. Это окно и является динамическим словарём для данного алгоритма - каждому элементу в нём соответствует два атрибута: позиция в окне и длина. Хотя в физическом смысле это просто участок памяти, который мы уже закодировали.
«The compression and the decompression leave an impression. Hahahahaha!»
Вот как она будет выглядеть в памяти (кодировка ANSI):
0000: 54 68 65 20 63 6F 6D 70 72 65 73 73 69 6F 6E 20 The compression
0010: 61 6E 64 20 74 68 65 20 64 65 63 6F 6D 70 72 65 and the decompre
0020: 73 73 69 6F 6E 20 6C 65 61 76 65 20 61 6E 20 69 ssion leave an i
0030: 6D 70 72 65 73 73 69 6F 6E 2E 20 48 61 68 61 68 mpression. Hahah
0040: 61 68 61 68 61 21 ahaha!
Мы ещё не определились с размером окна, но условимся, что он больше размера кодируемой строки. Попробуем найти все повторяющиеся цепочки символов. Цепочкой будем считать последовательность символов длиной более единицы. Если цепочка входит в состав более длинной повторяющейся цепочки, будем её игнорировать.
«The compression and t de leave[ an] i . Hah !»
Для пущей наглядности посмотрим на схему, где видны соответствия повторяемых последовательностей и их первых вхождений:
Пожалуй, единственным неясным моментом здесь будет последовательность «Hahahahaha!», ведь цепочке символов «ahahaha» соответствует короткая цепочка «ah». Но здесь нет ничего необычного, мы использовали кое-какой приём, позволяющий алгоритму иногда работать как описанный ранее RLE.
Дело в том, что при распаковке мы будем считывать из словаря указанное количество символов. А поскольку вся последовательность периодична, т.е. данные в ней повторяются с некоторым периодом, и символы первого периода будут находиться прямо перед позицией распаковки, то по ним мы можем воссоздать всю цепочку целиком, просто копируя символы предыдущего периода в следующий.
С этим разобрались. Теперь заменим найденные повторы на ссылки в словарь. Будем записывать ссылку в формате , где P - позиция первого вхождения цепочки в строке, L - её длина.
«The compression and t de leave i . Hah !»
Но не стоит забывать, что мы имеем дело со скользящим окном. Для большего понимания, чтобы ссылки не зависели от размера окна, заменим абсолютные позиции на разницу между ними и текущей позицией кодирования.
«The compression and t de leave i . Hah !»
Теперь нам достаточно отнять P от текущей позиции кодирования, чтобы получить абсолютную позицию в строке.
Пришло время определиться с размером окна и максимальной длиной кодируемой фразы. Поскольку мы имеем дело с текстом, редко когда в нём будут встречаться особо длинные повторяющиеся последовательности. Так что выделим под их длину, скажем, 4 бита - лимита на 15 символов за раз нам вполне хватит.
А вот от размера окна уже зависит, насколько глубоко мы будем искать одинаковые цепочки. Поскольку мы имеем дело с небольшими текстами, то в самый раз будет дополнить используемое нами количество бит до двух байт: будем адресовать ссылки в диапазоне из 4096 байт, используя для этого 12 бит.
По опыту с RLE мы знаем, что не всякие значения могут быть использованы. Очевидно, что ссылка может иметь минимальное значение 1, поэтому, чтобы адресовать назад в диапазоне 1..4096, мы должны при кодировании отнимать от ссылки единицу, а при декодировании прибавлять обратно. То же самое с длинами последовательностей: вместо 0..15 будем использовать диапазон 2..17, поскольку с нулевыми длинами мы не работаем, а отдельные символы последовательностями не являются.
Итак, представим наш закодированный текст с учётом этих поправок:
«The compression and t de leave i . Hah !»
Теперь, опять же, нам надо как-то отделить сжатые цепочки от остальных данных. Самый распространённый способ - снова использовать структуру и прямо указывать, где сжатые данные, а где нет. Для этого мы разделим закодированные данные на группы по восемь элементов (символов или ссылок), а перед каждой из таких групп будем вставлять байт, где каждый бит соответствует типу элемента: 0 для символа и 1 для ссылки.
Разделяем на группы:
«{0,0,0,0,0,0,0,0} The comp{0,0,0,0,0,0,0,0} ression {0,0,0,0,0,1,0,0} and t de{1,0,0,0,0,0,1,0} leave {0,1,0,0,0,0,0,1} i . Hah {0} !»
Таким образом, если при распаковке мы встречаем бит 0, то мы просто читаем символ в выходной поток, если же бит 1, мы читаем ссылку, а по ссылке читаем последовательность из словаря.
Теперь нам остаётся только сгруппировать результат в массив байтов. Условимся, что мы используем биты и байты в порядке от старшего к младшему. Посмотрим, как пакуются в байты ссылки на примере :
В итоге наш сжатый поток будет выглядеть так:
0000: 00
54 68 65 20 63 6f 6d 70 00
72 65 73 73 69 6f #The comp#ressio
0010: 6e 20 04
61 6e 64 20 74 01 31
64 65 82
01 5a
6c n #and t##de###l
0020: 65 61 76 65 01 b1
20 41
69 02 97
2e 20 48 61 68 eave## #i##. Hah
0030: 00 15
00
21 00 00 00 00 00 00 00 00 00 00 00 00
###!
«The long goooooong. The loooooower bound.»
Найдём последовательности только для слова «loooooower»:
«The long goooooong. The wer bound.»
Для кодирования такого результата нам понадобится четыре байта на ссылки. Однако, более экономично было бы сделать так:
«The long goooooong. The l wer bound.»
Тогда мы потратили бы на один байт меньше.
Их плюс - простота и быстродействие, а на их принципах и их комбинациях могут быть основаны более сложные и эффективные алгоритмы.
Надеюсь, изложенная таким образом суть этих алгоритмов поможет кому-нибудь разобраться в основах и начать смотреть в сторону более серьёзных вещей.
Данных, который поддерживается большинством форматов файлов растровых изображений: TIFF, BMP и PCX. RLE подходит для сжатия любого типа данных независимо от его информационного содержимого, но содержание данных влияет на коэффициент сжатия. Несмотря на то что большинство алгоритмов RLE не могут обеспечить высокие коэффициенты сжатия более сложных методов, данный инструмент легко реализовать и быстро выполнить, что делает его хорошей альтернативой.
RLE работает, уменьшая физический размер повторяющейся строки символов. Эта строка, называемая run, обычно кодируется в два байта. Первый байт представляет количество символов в пробеге и называется счетчиком прогона. На практике кодированный прогон может включать от 1 до 128 и 256 символов. Счетчик обычно содержит число символов минус один (значение в диапазоне значений от 0 до 127 и 255). Второй байт — это значение символа в прогоне, которое содержится в диапазоне значений от 0 до 255 и именуется значением запуска.
Без сжатия символьный пробег в 15 символов обычно требует 15 байтов для хранения:
AAAAAAAAAAAAAAA.
В той же строке после RLE-кодирования потребуется только два байта: 15А.
Кодировка 15A, сгенерированная для обозначения символьной строки, называется RLE-пакетом. В данном коде первый байт, 15, является счетчиком прогона и содержит необходимое количество повторений. Второй байт, A, является значением run и содержит фактическое повторяющееся значение в пробеге.
Новый пакет генерируется каждый раз, когда символ запуска изменяется, или каждый раз, когда количество символов в пробеге превышает максимальное количество. Предположим, что 15-символьная строка согласно условиям содержит 4 разных символа:
Используя кодировку с длиной строки, она может быть сжата в четыре двухбайтовых пакета:
После кодирования по длине строки для 15-байтовой строки потребуется всего восемь байтов данных для представления строки, в отличие от исходных 15 байтов. В этом случае кодирование во время выполнения давало коэффициент сжатия почти 2 к 1.
Длинные прогоны редки в некоторых типах данных. Например, открытый текст ASCII редко содержит длинные прогоны. В предыдущем примере последний пробег (содержащий символ t) был только одним символом в длину. 1-символьный прогон все еще работает. И счет запуска, и значение запуска должны быть записаны для каждого пробега в 2 символа. Для кодирования пробега с помощью алгоритма RLE требуется информация, состоящая не менее чем из двух символов. В связи с чем запуск одиночных символов на самом деле занимает больше места. По тем же причинам данные, состоящие полностью из 2-символьных прогонов, остаются неизменными после кодирования RLE.
Схемы алгоритма сжатия RLE отличаются простотой и высокой скоростью выполнения, но их эффективность зависит от типа кодируемых данных изображения. Черно-белое изображение, которое в основном белого цвета, например страницы книги, будет очень хорошо кодироваться из-за большого количества смежных данных, имеющих одинаковый цвет. Однако изображение со многими цветами, например, фотография, не будет кодироваться так же хорошо. Это связано с тем, что сложность изображения выражается в виде большого количества разных цветов. И из-за этой сложности будет относительно мало пробегов одного цвета.
Существует несколько вариантов кодировки во время выполнения. Данные изображения, как правило, закодированы в последовательном процессе, который обрабатывает визуальный контент как 1D-поток, а не как 2D-карту данных. При последовательной обработке растровое изображение кодируется, стартуя с верхнего левого угла, и направляется слева направо по каждой строке сканирования в нижний правый угол растрового изображения. Но альтернативные схемы RLE также могут быть записаны для кодирования данных по длине растрового изображения вдоль столбцов для сжатия в 2D-плитки или даже для кодирования пикселей по диагонали зигзагообразным способом. Нечетные варианты RLE могут использоваться в узкоспециализированных приложениях, но обычно встречаются довольно редко.
Другим редко встречающимся вариантом является алгоритм кодирования RLE с ошибкой длины пробега. Данные инструменты обычно выполняют сжатие без потерь, но отбрасывание данных во время процесса кодирования, как правило, путем обнуления одного или двух младших значащих битов в каждом пикселе, может увеличить коэффициенты сжатия, не влияя отрицательно на качество сложных изображений. Эта программа алгоритма RLE хорошо работает только с изображениями реального мира, которые содержат много тонких вариаций значений пикселей.
Кросс-кодирование — это объединение строк сканирования, которое происходит, когда процесс сжатия теряет различие между исходными линиями. Если данные отдельных линий объединены алгоритмом кодирования повторов RLE, точка, где одна линия сканирования остановлена, а другая - потеряна, является уязвимой и сложной для обнаружения.
Иногда происходит перекрестное кодирование, которое усложняет процесс декодирования, добавляя стоимость времени. Для форматов файлов растровых изображений этот метод ставит целью организовать растровое изображение по линиям сканирования. Хотя многие спецификации формата файлов явно указывают, что данные строки должны быть индивидуально кодированы, многие приложения кодируют эти изображения как непрерывный поток, игнорируя границы строк.
Индивидуальное кодирование строк сканирования имеет преимущества в тех случаях, когда приложение должно использовать только некоторую часть изображения. Предположим, что фото содержит 512 строк развертки, и необходимо отображать только строки от 100 до 110. Если мы не знали, где строки сканирования начинались и заканчивались данными кодированного изображения, нашему приложению пришлось бы декодировать строки с 1 по 100, прежде чем найти десять строк, которые требуются. Если переходы между линиями сканирования были отмечены каким-то легко узнаваемым маркером разграничения, приложение могло бы просто считывать закодированные данные, подсчитывая маркеры, пока не дойдет до нужных ему строк. Но этот подход был бы довольно неэффективным.
Другим вариантом для определения начальной точки любой конкретной строки сканирования в блоке кодированных данных является построение таблицы строк развертки. Данная табличная структура обычно содержит один элемент для каждой строки сканирования на изображении, и каждый элемент содержит значение смещения соответствующей строки сканирования. Чтобы найти первый RLE-пакет строки 10 сканирования, все, что нужно сделать декодеру, — это найти значения позиции смещения, хранящегося в десятом элементе таблицы поиска строки сканирования. Таблица строк развертки также может содержать количество байтов, используемых для кодирования каждой строки. Используя этот метод с целью найти первый RLE-пакет строки сканирования 10, ваш декодер будет объединять значения первых 9-ти элементов таблицы строк развертки. Первый пакет для строки 10 сканирования будет начинаться с этого смещения байта от начала данных изображения с кодированием RLE.
Части алгоритмов кодирования по длине, которые различаются, — это решения, которые принимаются на основе типа данных, которые декодируются (например, длина прогона данных). Схемы RLE, используемые для сжатия растровой графики, обычно подразделяются на классы по типу атомных (то есть наиболее фундаментальных) элементов, которые они кодируют. Три класса, используемые большинством графических форматов файлов, — это бит, байты и пиксельные RLE.
Битовые уровни RLE-схем кодируют прогоны нескольких бит в строке сканирования и игнорируют границы байтов и слов. Только монохромные (черно-белые), 1-битные изображения содержат достаточное количество бит, чтобы сделать этот класс RLE-кодирования эффективным. Типичная схема RLE на уровне бит кодирует от одного до 128 бит в однобайтовом пакете. Семь младших значащих бит содержат счетчик запуска минус один, а старший бит содержит значение битового прогона, равное 0 или 1. Прогон длиной более 128 пикселей разбит на несколько RLE-кодированных пакетов.
Схемы RLE на уровне байта кодируют прогоны одинаковых байтовых значений, игнорируя некоторые биты и границы слов в строке сканирования. Наиболее распространенная схема RLE на байтовом уровне кодирует прогоны байтов в 2-байтовые пакеты. Первый байт содержит счетчик от 0 до 255, а второй — содержит значение байтового запуска. Также распространено дополнение двухбайтовой схемы кодирования с возможностью хранения литеральных, незаписанных прогонов байтов в потоке кодированных данных.
В такой схеме семь младших значащих бит первого байта содержат счетчик прогона минус один, а самый старший бит первого байта является индикатором типа запуска, который следует за байтом подсчета прогона. Если старший бит установлен в 1, он обозначает кодированный прогон. Закодированные прогоны декодируются путем считывания значения пробега и повторения его количества раз, указанного числом циклов. Если самый старший бит установлен в 0, отображается литеральный прогон, а это означает, что байты подсчета следующего прогона считываются буквально из данных кодированного изображения. Затем байт счетчика выполнения содержит значение в диапазоне от 0 до 127 (счетчик запуска минус один). Схемы RLE на уровне байта хороши для данных изображения, которые сохраняются как один байт на пиксель.
Схемы RLE на уровне пикселей используются, когда два или более последовательных байта данных изображения используются для хранения значений одного пикселя. На уровне пикселей биты игнорируются, а байты подсчитываются только для идентификации каждого значения пикселя. Размер кодированных пакетов зависит от размера кодируемых значений пикселей. Количество бит или байтов на пиксель сохраняется в заголовке файла изображения. Запуск данных изображения, сохраненных в виде 3-байтовых значений пикселей, кодируется в 4-байтовый пакет, с одним байтом подсчета количества операций, за которым следуют три байта с байтами. Метод кодирования остается таким же, как и с байтовым RLE.
