Move-To-Front

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

Алгоритм

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

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

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

Пример

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

bananaaa

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

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

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

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

bzip2

Литература

↑ Рябко, Борис Яковлевич (1980). "Сжатие данных с помощью стопки книг" (PDF). Проблемы передачи информации. 16 (4): 265–269. Zbl 0447.94009.
↑ Ryabko, Boris Yakovlevich; Horspool, R. Nigel [in английский]; Cormack, Gordon Villy [in английский] (1987). "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 (9): 792—794. doi:10.1145/30401.315747. S2CID 16138142.
↑ Bentley, Jon Louis [in английский]; Sleator, Daniel Dominic Kaplan [in английский]; Tarjan, Robert Endre; Wei, V. K. (1986). "A Locally Adaptive Data Compression Scheme". Communications of the ACM. 29 (4): 320—330. CiteSeerX 10.1.1.69.807. doi:10.1145/5684.5688. S2CID 5854590.

[1] Рябко, Борис Яковлевич (1980). "Сжатие данных с помощью стопки книг" (PDF). Проблемы передачи информации. 16 (4): 265–269. Zbl 0447.94009.

[2] Ryabko, Boris Yakovlevich; Horspool, R. Nigel [in английский]; Cormack, Gordon Villy [in английский] (1987). "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 (9): 792—794. doi:10.1145/30401.315747. S2CID 16138142.

[3] Bentley, Jon Louis [in английский]; Sleator, Daniel Dominic Kaplan [in английский]; Tarjan, Robert Endre; Wei, V. K. (1986). "A Locally Adaptive Data Compression Scheme". Communications of the ACM. 29 (4): 320—330. CiteSeerX 10.1.1.69.807. doi:10.1145/5684.5688. S2CID 5854590.

[1]

[2]

[3]