Ответ: К вопросу о сжатии черно-белого изображения
RLE работает так (на примере сжатия на уровне байтов):
- анализ данных и выявление самого редкого байта, этот байт будет признаком сжатой алгоритмом последовательности обозначим его буквой U, и сразу записываем его в выходной поток.
- сжатие работает так, читаем первый байт и запоминаем, читаем следующий, если байты неравны записываем первый байт в выходной поток (т.к. сжимать нечего.
Повторяем до тех пор пока вподряд небудет минимум 3х одинаковых байт (только для последовательностей от более 3х байт имеет RLE имеет смысл). Кодируем последовательность одинаковых байт в виде: U B C, где U - байт идентификатор сжатого блока, B - повторяемый байт, C - число повторений.
Если нам во входном потоке попадается байт U, мы его кодируем последовательностью UU.
Эта реализация обладает рядом свойств:
- сжатие не увеличивает размер файла если данные не сжимаемы. (возможно небольшое увеличение если байт U довольно популярен в данных, хотя алгоритмом оговорено четкое условие выбора байта на эту роль, как самого редкого)
- Максимальная длина сжимаемой последовательности 255 повторов. Последовательности длиной 3, сжимаются в эквивалентную последовательность.
Декомпрессия.
- читаем первый байт это наш U идентификатор.
- читаем байт если это U и следующий байт U то пишем в выходной поток U байт. Т.к. это экранирующая последовательность.
- читаем байт если это U, а следующий байт B не U, то читаем третий байт C и записываем B в выходной поток C раз.
- все остальные байты пишем без изменений.
__________________
|