Сжать с помощью способа кодирования серий rle сообщение и оценить степень сжатия

Обновлено: 05.07.2024

Наиболее известный простой подход и алгоритм сжатия информации обратимым путем - это кодирование серий последовательностей (Run Length Encoding - RLE). Это самый простой из методов упаковки информации.

Предположите, что вы имеете строку текста, и в конце строки стоит 40 пробелов. Налицо явная избыточность имеющейся информации. Проблема сжатия этой строки решается очень просто - эти 40 пробелов (40 байт) сжимаются в 3 байта с помощью упаковки их по методу повторяющихся символов (running). Первый байт, стоящий вместо 40 пробелов в сжатой строке, фактически будет являться пробелом, (последовательность была из пробелов). Второй байт - байт счета (в нашем случае это будет 40). Как вы сами можете видеть, достаточно, чтобы любой раз, когда мы имеем последовательность из более 3 одинаковых символов, заменять их вышеописанной последовательностью, чтобы на выходе получить блок информации, меньший по размеру, но допускающий восстановление информации в исходном виде.

Суть методов данного подхода состоит в замене цепочек или серий повторяющихся байтов или их последовательностей на один кодирующий байт и счетчик числа их повторений.

Например: 44 44 44 11 11 11 11 11 01 33 FF 22 22 - исходная последовательность 03 44 04 11 00 03 01 03 FF 02 22 - сжатая последовательность

Первый байт указывает сколько раз нужно повторить следующий байт.

Если первый байт равен 00, то затем идет счетчик, показывающий, сколько за ним следует неповторяющихся данных.

Данные методы, как правило, достаточно эффективны для сжатия растровых графических изображений (BMP, PCX, TIF, GIF), т.к. последние содержат достаточно много длинных серий повторяющихся последовательностей байтов.

Недостатком метода RLE является достаточно низкая степень сжатия.

9.9. Алгоритм Хаффмана

Сжимая файл по алгоритму Хаффмана, первое, что мы должны сделать, - это необходимо прочитать файл полностью и подсчитать, сколько раз встречается каждый символ из расширенного набора ASCII.

Если мы будем учитывать все 256 символов, то для нас не будет разницы в сжатии текстового и EXE файла.

После подсчета частоты вхождения каждого символа необходимо просмотреть таблицу кодов ASCII и сформировать бинарное дерево.

Мы имеем файл длиной в 100 байт и имеющий 6 различных символов в себе. Мы подсчитали вхождение каждого из символов в файл и получили следующее :

Теперь мы берем эти числа и будем называть их частотой вхождения для каждого символа.

Мы возьмем из последней таблицы 2 символа с наименьшей частотой. В нашем случае это D (5), и какой-либо символ из F или A (10), можно взять любой из них, например A.

Сформируем из "узлов" D и A новый "узел", частота вхождения для которого будет равна сумме частот D и A :

Номер в рамке - сумма частот символов D и A. Теперь мы снова ищем два символа с самыми низкими частотами вхождения. Исключаем из просмотра D и A и рассматриваем вместо них новый "узел" с суммарной частотой вхождения. Самая низкая частота теперь у F и нового "узла". Снова сделаем операцию слияния узлов :

Рассматриваем таблицу снова для следующих двух символов (B и E).

Мы продолжаем эту процедуру до тех пор, пока все "дерево" не сформировано, т.е. пока все не сведется к одному узлу.

Теперь, когда наше дерево создано, мы можем кодировать файл. Мы должны всегда начинать из корня (Root). Кодируя первый символ (лист дерева С), мы прослеживаем вверх по дереву все повороты ветвей, и, если мы делаем левый поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота. Так, для C мы будем идти влево к 55 (и запомним 0), затем снова влево (0) к самому символу. Код Хаффмана для нашего символа C - 00. Для следующего символа ( А ) у нас получается - влево, вправо, влево, влево, что выливается в последовательность 0100. Выполнив выше сказанное для всех символов, получим:

C = 00 (2 бита) A = 0100 (4 бита) D = 0101 (4 бита) F = 011 (3 бита) B = 10 (2 бита) E = 11 (2 бита)

При кодировании заменяем символы данными последовательностями. Достоинствами метода Хаффмана являются его достаточно высокая скорость и хорошее качество сжатия. Этот алгоритм сравнительно давно известен и широко применяется; примерами могут служить программа compress ОС UNIX (программная реализация) и стандарт кодирования для факсов [Hunter] (аппаратная реализация).

Кодирование Хаффмана имеет минимальную избыточность при условии, что каждый символ кодируется отдельной цепочкой в алфавите ).

Недостатком кодирования Хаффмана является зависимость степени сжатия от близости вероятностей символов к отрицательным степеням 2; это связано с тем, что каждый символ кодируется *целым* числом бит. Наиболее ярко это проявляется при кодировании двухсимвольного алфавита: в этом случае сжатие *всегда* отсутствует, несмотря на различие вероятностей символов; алгоритм фактически "округляет" их до 1/2!

Большую степень сжатия, не зависящую от близости значений вероятности символов к степеням 1/2, может дать так называемое арифметическое кодирование.

Собственно, метод сжатия RLE (Run Length Encoding), или, в русском переводе, кодирование длин серий или кодирование повторов - это наверное самые простейший алгоритм сжатия данных, в котором повторяющиеся символы (серии, т.е. последовательности, состоящая из нескольких одинаковых символов) заменяются на один символ и число его повторов.

начать с первого символа
добавить его в строку результата
посчитать число повторений символа и добавить это число в строку результата
взять следующий символ и повторять до конца исходной строки

Пример: строка “aaaabbbccd” после кодирования повторов превращается в строку “a4b3c2d1”, таким образом вместо 10 символов мы получаем 8. Сжатие налицо!

Калькулятор ниже сжимает введенную строку методом RLE, а также выводит длины исходной и получившейся строк и процент сжатия данных.

Алгоритм RLE — это алгоритм сжатия данных, который поддерживается большинством форматов файлов растровых изображений: TIFF, BMP и PCX. RLE подходит для сжатия любого типа данных независимо от его информационного содержимого, но содержание данных влияет на коэффициент сжатия. Несмотря на то что большинство алгоритмов RLE не могут обеспечить высокие коэффициенты сжатия более сложных методов, данный инструмент легко реализовать и быстро выполнить, что делает его хорошей альтернативой.

На чем основан алгоритм сжатия RLE?

RLE работает, уменьшая физический размер повторяющейся строки символов. Эта строка, называемая run, обычно кодируется в два байта. Первый байт представляет количество символов в пробеге и называется счетчиком прогона. На практике кодированный прогон может включать от 1 до 128 и 256 символов. Счетчик обычно содержит число символов минус один (значение в диапазоне значений от 0 до 127 и 255). Второй байт — это значение символа в прогоне, которое содержится в диапазоне значений от 0 до 255 и именуется значением запуска.

Без сжатия символьный пробег в 15 символов обычно требует 15 байтов для хранения:

В той же строке после 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, точка, где одна линия сканирования остановлена, а другая - потеряна, является уязвимой и сложной для обнаружения.

Иногда происходит перекрестное кодирование, которое усложняет процесс декодирования, добавляя стоимость времени. Для форматов файлов растровых изображений этот метод ставит целью организовать растровое изображение по линиям сканирования. Хотя многие спецификации формата файлов явно указывают, что данные строки должны быть индивидуально кодированы, многие приложения кодируют эти изображения как непрерывный поток, игнорируя границы строк.

Как с помощью алгоритма 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.

Алгоритм RLE (Run Length Encoding).
Учебная программа сжатия информации (данных) без потерь.

Очень простой и понятный алгоритм сжатия информации.

Суть его можно изложить так:
представлять все цепочки одинаковых символов всего одним из них, а в служебном байте, с которого начинается любая цепочка архива указывать их количество и тип цепочки.
Цепочки разных (не повторяющихся) символов исходного текста в архиве также будет иметь служебный байт (тип цепочки и длина), после которого следуют все символы исходной цепочки.

Задание:

Написать программу сжатия текста, состоящего из символов уникода.
Оценить степень (%) сжатия для каждого случая.

Решение:

служебный байт 10000000 (в дополнительном коде -128) говорит о том, что это серия с одинаковыми символами и таких символов в серии всего 2.
служебный байт 10000011 (в дополнительном коде -125) говорит о том, что это серия с одинаковыми символами и таких символов в серии всего 5.
служебный байт 00000011 (в дополнительном коде 3) говорит о том, что это серия с разными символами и символов в серии всего 4.
служебный байт 01111111 (в дополнительном коде 127) говорит о том, что это серия с разными символами и символов в серии всего 128.

Void Form1::button1_Click(System::Object^ sender, System::EventArgs^ e)

В файлах RLE.h и RLE.cpp кроме rleOperac (методы перечислены выше), описан класс RLE_Auto, предназначенный для работы с единственной серией (или цепочкой) символов. Среди его методов есть:
public: System::Void Step(wchar_t s) ; //очередной шаг для автомата Тьюринга
public: System::Void Check127(void) ; //проверка от переполнения служебного байта
public: System::Char GetServise(void) ; //получение служебного байта
public: System::Void ReadServise(System::Char serv) ; //чтение служебного байта
и другие…

Работать с классами намного проще, не говоря уже про повторное их использование…

Цепочки из разных символов в архиве будут повторять все символы исходной цепочки и дополняться служебным байтом, поэтому сжатием в этом случае и не пахнет. И лучше, чтобы эта цепочка была длинной, чтобы служебный байт дал меньший процент приращения размера архива по сравнению с исходным текстом…

Таким образом, понятно, что не всякий текст будет сжиматься. Если нет длинных цепочек с одинаковыми символами, то, скорее всего, длина архива даже увеличится, по сравнению с исходной строкой (за счет введения служебных байтов).

Читайте также: