> mtf | move | front <
// Move-to-Front - Динамическая перестановка списка для улучшения сжатия
Самоадаптивный
Автоматически подстраивается под локальные шаблоны в данных.
Использует локальность
Недавно использованные символы получают меньшие индексы, что улучшает степень сжатия.
Часть цепочки bzip2
Используется после BWT в конвейере сжатия bzip2.
>> техническая информация
Как работает MTF:
MTF поддерживает список всех возможных символов. При кодировании символа выводится его текущая позиция в списке, после чего символ переносится в начало. Это даёт недавно использованным символам меньшие индексы, которые лучше сжимаются на последующих этапах энтропийного кодирования.
Пример кодирования:
Текст: "banana" Начальный список: [a,b,c,d,...] "b": индекс 1, переместить b→в начало [b,a,c,d,...] "a": индекс 1, переместить a→в начало [a,b,c,d,...] "n": индекс 13, переместить n→в начало [n,a,b,c,...] "a": индекс 1, переместить a→в начало [a,n,b,c,...] "n": индекс 1, переместить n→в начало [n,a,b,c,...] "a": индекс 1, переместить a→в начало [a,n,b,c,...] Выход: [1,1,13,1,1,1]
Зачем использовать MTF:
- >Улучшает локальную избыточность
- >Хорошо работает вместе с BWT
- >Простая реализация
- >Обратимое преобразование
- >Адаптируется к шаблонам
>> часто задаваемые вопросы
Что такое кодирование Move-to-Front?
MTF — это алгоритм преобразования данных, который кодирует каждый символ как его индекс в динамически обновляемом списке. После кодирования символ перемещается в начало списка, поэтому часто используемые символы получают маленькие индексы.
Почему MTF используют вместе с BWT?
BWT группирует похожие контексты и создаёт локальные повторы. MTF преобразует эти повторы в небольшие числа (много нулей и единиц), которые очень хорошо сжимаются с помощью кодирования длины серий или кодирования Хаффмана.
Как работает список в MTF?
Список начинается со всех 256 возможных значений байта в порядке возрастания. По мере кодирования символов используемые значения перемещаются в начало. Недавно использованные символы остаются ближе к началу со малыми индексами, а редко используемые постепенно смещаются к большим индексам.
MTF по сравнению с другими преобразованиями?
MTF специально разработан для использования после BWT. Сам по себе он не столь эффективен, но отлично подходит для преобразования вывода BWT в форму, хорошо подходящую для сжатия. Он проще арифметического кодирования, но немного менее оптимален.