1. Rle, Run Length Encoding, Кодирование Длин Повторов.

Самый тривиальный способ сжатия. Использующий меньше всего памяти и времени. Компрессор находит повторы одинаковых элементов Z и замещает их набором {элемент Z, флаг повтора, число элементов в повторе N}. Остальные же элементы попросту копируются из входного потока в выходной. Если памяти доступно больше, чем несколько байт, вместо флага повтора можно записывать расстояние до следующего повтора.

Как и всякий поточный метод, RLE применим и к блокам данных. Вообще блочные методы отличаются лишь тем, что не могут работать, пока не задана длина буфера с данными. Остальное же - их свойства, а не признаки:

- чем меньше размер блока, тем менее эффективен блочный метод (поточным методам это свойство присуще в меньшей степени);

- всякий элемент блока преобразуется одинаковым образом, независимо от его расстояния до начала и конца блока (это свойственно и многим поточным методам, например SEM и Delta Coding);

- почти все блочные методы являются двухпроходными (LZ77 и т.п. намного эффективнее с двумя проходами «поиск слов» и «анализ и преобразование»).

Если предполагается дальнейшее сжатие выхода RLE, то можно создавать четыре выходных потока/блока: длины повторов N[i]; элементы повторов Z[i]; длины остальных фрагментов, в которых повторов не найдено, R[i]; остальные фрагменты OF[i]. Может оказаться, что сжатие улучшится, если первые элементы остальных фрагментов (элементы, «обрывающие» повторы) записывать в отдельный пятый поток/блок, а последние элементы OF - в шестой.

Основные принципы сжатия информации видны уже на этом самом тривиальном примере. Остается упомянуть, что RLE - частный случай «скользящего окна», словарных методов типа LZ*, когда размер этого окна-словаря равен единице, то есть ссылка-смещение может быть только на один элемент назад, а длина - любой.

RLE эффективнее на ММД с маленькой размерностью R, от 1 до 8 битов. Чем больше размерность R байтов ММД, тем менее вероятно, что применение RLE к этим ММД улучшит сжатие.

2. Sem (Separate Exponents and Mantissas). Отделение мантиссы числа от экспоненты.

Большое семейство методов, называемое обычно Integer Coding, включающее структурную модель Фенвика, Rice codes, Fibonacci codes, Golomb codes, Elias Gamma и Delta codes и много других, более сложных вариантов, например DAKX.

А в простейшем случае создается два потока: старшие N битов, младшие (R-N) битов. Очевидно, что первый поток - старшие биты (Most Significant Bits) при правильном выборе N сжимается, как правило, лучше, особенно в случае ММД. Но еще эффективнее разделение числа на экспоненту (номер старшего ненулевого бита B) и мантиссу (остальные биты, младше B). Первый поток получается байтовым, второй - битовым. Можно и дальше разделять получающиеся потоки, особенно первый.

SEM часто применяется при сжатии ММД, в сочетании с другими методами, а в алгоритмах сжатия с потерями SEM присутствует обязательно.