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

Материал из Викиконспекты
Перейти к: навигация, поиск

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

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



Алгоритм


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



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

Coder и Decoder


Coder
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
Decoder
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

Ссылки


"Move to front" by Arturo San Emeterio Campos
Преобразование Барроуза-Вилера
http://ru.wikipedia.org/wiki/Move-To-Front