Move-To-Front

Move-To-Front (MTF, «перемещение в начало») — это адаптивный алгоритм преобразования данных, используемый в сжатии информации. Он относится к классу алгоритмов, изменяющих порядок элементов в списке (или словаре) на основе их частоты использования: каждый раз, когда к элементу обращаются, он перемещается в начало списка. Основное назначение MTF — преобразование входной последовательности символов (или других элементов) в последовательность индексов, которая часто содержит много повторяющихся малых значений, что повышает эффективность последующего статистического кодирования (например, кодирования Хаффмана или арифметического кодирования).

История

Алгоритм Move-To-Front был впервые описан в 1970-х годах в контексте организации списков и кэширования. Идея перемещения часто используемых элементов в начало списка для ускорения доступа известна как «эвристика MTF» (move-to-front heuristic). В области сжатия данных алгоритм получил широкое распространение в 1980-х годах, когда его стали применять в сочетании с преобразованием Барроуза — Уилера (BWT) и кодированием длин серий (RLE). Комбинация BWT → MTF → RLE → статистическое кодирование стала основой многих эффективных архиваторов, таких как bzip2.

Принцип работы

Алгоритм MTF оперирует с упорядоченным списком всех возможных символов (алфавитом). Изначально список строится в некотором фиксированном порядке (например, по возрастанию кодов символов). Для каждого символа входной последовательности выполняются два шага:

1. Поиск индекса: находится позиция (индекс) текущего символа в текущем списке. Этот индекс (начиная с 0) записывается в выходную последовательность.
2. Перемещение: найденный символ удаляется с его текущей позиции и вставляется в начало списка (на позицию 0).

Таким образом, часто встречающиеся символы быстро оказываются в начале списка и получают малые индексы (0, 1, 2...), а редкие — остаются в конце и получают большие индексы. Выходная последовательность индексов состоит преимущественно из малых чисел, что благоприятно для сжатия.

Пример работы

Пусть алфавит состоит из трёх символов: a, b, c. Изначальный список: [a, b, c]. Входная последовательность: a b a c a b a.

Выходная последовательность индексов: 0, 1, 1, 2, 1, 2, 1. Как видно, большинство значений — 0, 1 или 2, причём 0 встречается только один раз, а 1 — четыре раза. Такая последовательность хорошо сжимается.

Свойства и характеристики

Адаптивность

MTF автоматически адаптируется к локальным закономерностям данных: если в некотором участке текста часто встречается определённый символ, он быстро перемещается в начало списка, и его индекс становится малым. При смене контекста (например, появлении другого частого символа) список перестраивается.

Обратимость

Преобразование MTF является обратимым при условии, что известен начальный порядок списка. Для восстановления исходной последовательности по последовательности индексов необходимо выполнить обратную операцию: для каждого индекса взять символ из списка по этому индексу, записать его в выходной поток и переместить этот символ в начало списка.

Размер выходных данных

В худшем случае (например, при равномерном распределении символов или при подаче на вход последовательности, где каждый символ встречается один раз) выходные индексы могут быть большими, и сжатие может не улучшиться. Однако на практике, особенно после преобразования Барроуза — Уилера, MTF даёт значительный выигрыш.

Вычислительная сложность

Для каждого символа требуется найти его индекс в списке. При реализации с линейным поиском сложность составляет O(N * L), где N — длина входной последовательности, L — размер алфавита. Для типичных алфавитов (например, 256 байт) это приемлемо. Для ускорения можно использовать хеш-таблицы или деревья, но в классических реализациях (bzip2) используется простой линейный поиск.

Применение

Сжатие данных

MTF является ключевым компонентом в схеме сжатия, известной как BWT + MTF + RLE + энтропийное кодирование. Эта схема используется в архиваторе bzip2 (формат .bz2), а также в некоторых других алгоритмах и программах (например, в компрессоре текста szip). MTF также применяется в некоторых реализациях сжатия изображений и аудио.

Организация списков и кэшей

В информатике эвристика MTF используется для организации списков (например, в хеш-таблицах с открытой адресацией, в списках свободных блоков памяти) и кэшей, где часто используемые элементы должны быть доступны быстрее. Однако в современных процессорах и операционных системах чаще применяются более сложные алгоритмы (LRU, LFU), так как MTF может приводить к излишним перемещениям при циклическом доступе.

Критика и ограничения

• Неэффективность на равномерных данных: если все символы встречаются с одинаковой частотой, MTF не даёт выигрыша, а иногда даже ухудшает сжатие.
• Чувствительность к начальному порядку списка: если начальный порядок не соответствует статистике данных, первые символы могут получать большие индексы. На практике начальный порядок выбирается фиксированным (например, по возрастанию кодов ASCII).
• Проблема циклического доступа: при повторяющемся доступе к нескольким символам в цикле (например, a b a b a b...) MTF может постоянно перемещать их, не давая стабильно малых индексов. В таких случаях могут быть полезны модификации алгоритма (например, «move-to-front с порогом» или «transpose»).
• Отсутствие сжатия как такового: MTF сам по себе не сжимает данные, а лишь преобразует их в форму, более удобную для сжатия другими алгоритмами. Размер выходных данных после MTF может быть больше исходного.

Интересные факты

• Алгоритм MTF тесно связан с понятием «локальности ссылок» (locality of reference) в компьютерных системах: он предполагает, что недавно использованные данные будут использованы снова в ближайшем будущем.
• В архиваторе bzip2 после MTF применяется кодирование длин серий (RLE) для последовательностей нулей, которые часто возникают после MTF, а затем — кодирование Хаффмана.
• Существуют варианты MTF, в которых элемент перемещается не в начало, а на несколько позиций вперёд (например, «move-to-front с шагом»), что может улучшить поведение на некоторых типах данных.

Источники

• Bentley, J. L., Sleator, D. D., Tarjan, R. E., & Wei, V. K. (1986). A locally adaptive data compression scheme. Communications of the ACM, 29(4), 320-330.
• Burrows, M., & Wheeler, D. J. (1994). A block-sorting lossless data compression algorithm. Digital Equipment Corporation Technical Report, 124.
• Nelson, M., & Gailly, J.-L. (1996). The Data Compression Book (2nd ed.). M&T Books.
• Salomon, D. (2007). Data Compression: The Complete Reference (4th ed.). Springer.