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

Литература

1. Ryabko, B. Ya. Data compression by means of a «book stack», Problems of Information Transmission, 1980, v. 16: (4), pp. 265–269.
2. 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.

Отрывок, характеризующий Move-To-Front

– Имею удовольствие говорить с графом Безухим, ежели я не ошибаюсь, – сказал проезжающий неторопливо и громко. Пьер молча, вопросительно смотрел через очки на своего собеседника.
– Я слышал про вас, – продолжал проезжающий, – и про постигшее вас, государь мой, несчастье. – Он как бы подчеркнул последнее слово, как будто он сказал: «да, несчастье, как вы ни называйте, я знаю, что то, что случилось с вами в Москве, было несчастье». – Весьма сожалею о том, государь мой.
Пьер покраснел и, поспешно спустив ноги с постели, нагнулся к старику, неестественно и робко улыбаясь.
– Я не из любопытства упомянул вам об этом, государь мой, но по более важным причинам. – Он помолчал, не выпуская Пьера из своего взгляда, и подвинулся на диване, приглашая этим жестом Пьера сесть подле себя. Пьеру неприятно было вступать в разговор с этим стариком, но он, невольно покоряясь ему, подошел и сел подле него.
– Вы несчастливы, государь мой, – продолжал он. – Вы молоды, я стар. Я бы желал по мере моих сил помочь вам.
– Ах, да, – с неестественной улыбкой сказал Пьер. – Очень вам благодарен… Вы откуда изволите проезжать? – Лицо проезжающего было не ласково, даже холодно и строго, но несмотря на то, и речь и лицо нового знакомца неотразимо привлекательно действовали на Пьера.
– Но если по каким либо причинам вам неприятен разговор со мною, – сказал старик, – то вы так и скажите, государь мой. – И он вдруг улыбнулся неожиданно, отечески нежной улыбкой.
– Ах нет, совсем нет, напротив, я очень рад познакомиться с вами, – сказал Пьер, и, взглянув еще раз на руки нового знакомца, ближе рассмотрел перстень. Он увидал на нем Адамову голову, знак масонства.
– Позвольте мне спросить, – сказал он. – Вы масон?
– Да, я принадлежу к братству свободных каменьщиков, сказал проезжий, все глубже и глубже вглядываясь в глаза Пьеру. – И от себя и от их имени протягиваю вам братскую руку.
– Я боюсь, – сказал Пьер, улыбаясь и колеблясь между доверием, внушаемым ему личностью масона, и привычкой насмешки над верованиями масонов, – я боюсь, что я очень далек от пониманья, как это сказать, я боюсь, что мой образ мыслей насчет всего мироздания так противоположен вашему, что мы не поймем друг друга.