2015-07-14
974
Наиболее известный простой подход и алгоритм сжатия информации обратимым путем - это кодирование серий последовательностей (Run Length Encoding - RLE). Суть методов данного подхода состоит в замене цепочек или серий повторяющихся байтов или их последовательностей на один кодирующий байт и счетчик числа их повторений. Проблема всех аналогичных методов заключается лишь в определении способа, при помощи которого распаковывающий алгоритм мог бы отличить в результирующем потоке байтов кодированную серию от других — некодированных последовательностей байтов. Решение проблемы достигается обычно простановкой меток в начале кодированных цепочек. Такими метками могут быть, например, характерные значения битов в первом байте кодированной серии, значения первого байта кодированной серии и т.п. Данные методы, как правило, достаточно эффективны для сжатия растровых графических изображений (BMP, PCX, TIF, GIF:), т.к. последние содержат достаточно много длинных серий повторяющихся последовательностей байтов. Недостатком метода RLE является достаточно низкая степень сжатия или стоимость кодирования файлов с малым числом серий и, что еще хуже - с малым числом повторяющихся байтов в сериях.
Алгоритм декомпрессии при этом выглядит так:
Initialization(...);
do {
byte = ImageFile.ReadNextByte();
if(является счетчиком(byte)) {
counter = Low6bits(byte)+1;
value = ImageFile.ReadNextByte();
for(i=1 to counter)
DecompressedFile.WriteByte(value)
}
else {
DecompressedFile.WriteByte(byte)
} while(ImageFile.EOF());
В данном алгоритме признаком счетчика (counter) служат единицы в двух верхних битах считанного файла:
Соответственно оставшиеся 6 бит расходуются на счетчик, который может принимать значения от 1 до 64. Строку из 64 повторяющихся байтов мы превращаем в два байта, т.е. сожмем в 32 раза.
Алгоритм рассчитан на деловую графику — изображения с большими областями повторяющегося цвета. Ситуация, когда файл увеличивается, для этого простого алгоритма не так уж редка. Ее можно легко получить, применяя групповое кодирование к обработанным цветным фотографиям. Для того, чтобы увеличить изображение в два раза, его надо применить к изображению, в котором значения всех пикселов больше двоичного 11000000 и подряд попарно не повторяются.
Данный алгоритм реализован в формате PCX.
Второй вариант алгоритма имеет больший максимальный коэффициент архивации и меньше увеличивает в размерах исходный файл.
Алгоритм декомпрессии для него выглядит так:
Initialization(...);
do {
byte = ImageFile.ReadNextByte();
counter = Low7bits(byte)+1;
if(если признак повтора(byte)) {
value = ImageFile.ReadNextByte();
for (i=1 to counter)
CompressedFile.WriteByte(value)
}
else {
for(i=1 to counter){
value = ImageFile.ReadNextByte();
CompressedFile.WriteByte(value)
}
CompressedFile.WriteByte(byte)
} while(ImageFile.EOF());
Признаком повтора в данном алгоритме является единица в старшем разряде соответствующего байта:
Как можно легко подсчитать, в лучшем случае этот алгоритм сжимает файл в 64 раза (а не в 32 раза, как в предыдущем варианте), в худшем увеличивает на 1/128. Средние показатели степени компрессии данного алгоритма находятся на уровне показателей первого варианта.
Похожие схемы компрессии использованы в качестве одного из алгоритмов, поддерживаемых форматом TIFF, а также в формате TGA.
