Интернет магазин китайских планшетных компьютеров

Компьютеры - Move-To-Front

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

Алгоритм

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

Алгоритм впервые описан в работе. Изначально алгоритм назывался «стопка книг». История разработки алгоритма рассказана в.

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