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

Литература

  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. Архивировано 4 марта 2024. Дата обращения: 4 марта 2024.
Иконка
Это заготовка статьи об информационных технологиях и вычислительной технике. Помогите Википедии, дополнив её.
Это примечание по возможности следует заменить более точным.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.