Move-To-Front

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

АлгоритмПравить

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

Алгоритм впервые описан в работе [1]. Изначально алгоритм назывался «стопка книг» («book stack»). История разработки алгоритма рассказана в [2].

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

ПримерПравить

Рассмотрим работу алгоритма на алфавите из английских букв (пронумеруем их с нуля). Возьмём слово

bananaaa

b - записан в элементе с номером 1. После передвигания b в голову списка b станет нулевым, а а — 1-м

Оно будет преобразовано в

1,1,13,1,1,1,0,0

Алгоритмы, использующие MTFПравить

bzip2

ЛитератураПравить

Ryabko, B. Ya. Data compression by means of a «book stack», Problems of Information Transmission, 1980, v. 16: (4), pp. 265–269.
Ryabko, B. Ya.; Horspool, R. Nigel; Cormack, Gordon V. Comments to: «A locally adaptive data compression scheme» by J. L. Bentley, D. D. Sleator, R. E. Tarjan and V. K. Wei. Comm. ACM 30 (1987), no. 9, 792—794.