Алгоритм Running. Один из самых простых алгоритмов сжатия без потерь – так называемый алгоритм Running

Один из самых простых алгоритмов сжатия без потерь – так называемый алгоритм Running. Допустим, мы имеем цепочку одинаковых символов. Налицо явная избыточность информации. Сжатие осуществляется следующим образом:

1) подсчитывается количество одинаковых символов в цепочке;

2) вместо цепочки записывается символ и сколько раз повторяется этот символ.

Например, для строки из 40 пробелов записывается байт-код, показывающий, что идет повторяющийся символ, затем число 40 (сколько раз повторяется), и, наконец, пробел (повторяющийся символ). Строка длиной 40 байт сжимается до 3 байт.

Данный алгоритм прост и в понимании, и в реализации, но он малоэффективен, если используется в одиночку. Существуют файлы, которые содержат повторяющиеся символы, но не могут быть сжаты описанным выше алгоритмом. Это происходит, когда повторяются не символы, а последовательность символов. Например: «абабабабабаб». Повторяющихся друг за другом символов нет, и сжать предыдущим алгоритмом нельзя. В этом случае используется расширенный алгоритм. Он заключается в следующем:

1) Ищутся не повторяющиеся символы, а повторяющиеся последовательности символов (в данном случае это «аб»).

2) Затем подсчитывается, сколько раз повторяется эта последовательность.

3) Производится запись по следующему правилу: байт-код сигнала начала последовательности, количество повторяющихся последовательностей (в нашем случае 6), и сама последовательность (в нашем случае «аб»).

Но и это не конец. Дело в том, что могут существовать одинаковые фрагменты текста, располагающиеся в разных местах файла. Основная проблема состоит в том, чтобы найти эти фрагменты. Далее, фрагмент необходимо записать в определенную кодовую таблицу и приписать ему определенное значение. После этого можно заменять все фрагменты этим кодом-ссылкой. Реализация такого поиска – весьма сложная и трудоемкая задача. Хотя существуют особые ситуации, когда подобный поиск повторяющихся фрагментов может быть ускорен. Например, при передаче видеоизображения данные представляют собой последовательность кадров — картинок, состоящих из массива точек. Эти картинки имеют одинаковый размер и, что гораздо более важно, часто предыдущая картинка слабо отличаются от последующей (простейший пример – снимается неподвижный объект). В этом случае реализация Running -подобного алгоритма достаточно проста. Достаточно записывать для каждого следующего кадра только его отличия от предыдущего и можно добиться существенного сжатия данных для медленно меняющихся изображений.