Преобразование MTF

Преобразование MTF

Движение к началу (англ. move-to-front, MTF) — преобразование для кодирования данных (обычно потока байтов) разработанное для улучшения производительности энтропийного кодирования. При хорошей реализации, оно достаточно быстро для включения как дополнительный шаг в алгоритмах сжатия данных.

Алгоритм

Основной идеей преобразования является замена каждого входного символа его номером в специальном стэке недавно использованных символов. Последовательности идентичных символов, к примеру, будут заменены оригинальным алгоритмом (начиная со второго символа) на последовательность нулей. Если же символ долго не появлялся во входной последовательности, он будет заменен большим числом. Преобразование заменяет последовательность входных символов на последовательность целых чисел, если во входных данных было много локальных корреляций, то среди этих чисел будут преобладать небольшие, лучше сжимаемые энтропийным кодированием, чем исходные данные. Алгоритм впервые описан в работе. Изначально алгоритм назывался «стопка книг» («book stack»). Часто используется при преобразовании байтов. Изначально каждое возможное значение байта записывается в список, в ячейку с номером равным значению байта, т.е (0, 1, 2, 3, …, 255). В процессе обработки данных этот список изменяется. Первый обработанный символ заменяется самим собой, после чего элемент, соответствующий этому символу перемещается в голову списка (сдвигая элементы с 0 по свое положение на 1 вправо). Последующие символы кодируются номером элемента, содержащего их значение. После кодирования каждого символа эти элементы также продвигаются к голове списка.

Coder

Code Symbol List 0 a a b c d 1 b b a c d 1 a a b c d 0 a a b c d 2 c c a b d 1 a a c b d 2 b b a c d 1 a a b c d 3 d d a b c Decoder Symbol Code List a 0 a b c d b 1 b a c d a 1 a b c d a 0 a b c d c 2 c a b d a 1 a c b d b 2 b a c d a 1 a b c d d 3 d a b c Литература "Move to front" by Arturo San Emeterio Campos http://ru.wikipedia.org/wiki/Move-To-Front