> 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 в форму, хорошо подходящую для сжатия. Он проще арифметического кодирования, но немного менее оптимален.
// Разобранный пример
| # | Symbol | Index | List |
|---|---|---|---|
| 1 | b | 1 | abcdefg… |
| 2 | a | 1 | bacdefg… |
| 3 | n | 13 | abcdefg… |
| 4 | a | 1 | nabcdef… |
| 5 | n | 1 | anbcdef… |
| 6 | a | 1 | nabcdef… |
// Примеры кода
Input banana initial list: a b c d ... z (index from 0)
Output 1 1 13 1 1 1
Encode output the index of the symbol, then move it to the front
Decode read index, output list[index], move it to the front
Use after BWT: runs of equal symbols become runs of 0s,
which RLE and Huffman/arithmetic coding then compress well (bzip2)
>> Другие вопросы
В: Для чего нужен Move-to-Front?
О: MTF — не сжатие, а преобразование: недавно использованные символы получают малые индексы. Получается много нулей и единиц, которые хорошо сжимает энтропийный кодер (Хаффман, арифметический).
В: Как MTF связан с преобразованием Барроуза — Уилера?
О: BWT группирует одинаковые символы в серии. MTF превращает их в серии малых чисел, прежде всего 0. Цепочка BWT → MTF → RLE → Хаффман используется в bzip2.
В: MTF без потерь и обратим?
О: Да. Декодер начинает с того же исходного списка и повторяет те же перемещения. Исходный список (алфавит и порядок) должен совпадать на обеих сторонах.