Move-to-front transform¶
Move-to-front transform (MTF, преобразование перемещением в начало) — это алгоритм обратимого преобразования данных, используемый в сжатии информации. Он преобразует последовательность символов (или других элементов) в последовательность чисел, представляющих собой позиции этих символов в динамически обновляемом списке. Основная идея заключается в том, что часто встречающиеся символы кодируются малыми числами, что повышает эффективность последующего сжатия статистическими методами, такими как кодирование Хаффмана или арифметическое кодирование.
¶История
Move-to-front transform был впервые описан в 1987 году Бентоном Лейтоном и Джеймсом Сторером в контексте сжатия изображений. Однако широкое распространение алгоритм получил после его включения в состав блочного алгоритма сжатия Барроуза — Уилера (BWT), представленного в 1994 году. В этом контексте MTF применяется как второй этап после BWT, значительно улучшая сжатие текстовых данных. Впоследствии MTF нашёл применение в различных архиваторах, таких как bzip2, и в алгоритмах сжатия изображений (например, в формате JPEG 2000 в некоторых реализациях).
¶Принцип работы
¶Алгоритм кодирования
- Инициализация: создаётся упорядоченный список всех возможных символов алфавита. Например, для алфавита ASCII из 256 символов список содержит все коды от 0 до 255.
- Обработка символов: для каждого символа входной последовательности:
- Находится его текущая позиция в списке (индекс, начиная с 0).
- В выходной поток записывается этот индекс.
- Символ перемещается в начало списка (на позицию 0).
- Повторение: шаг 2 выполняется для всех символов входной последовательности.
¶Алгоритм декодирования
Процесс декодирования является обратным и использует тот же динамический список:
- Инициализация: создаётся тот же упорядоченный список алфавита.
- Обработка чисел: для каждого числа из входной последовательности:
- Из списка извлекается символ, находящийся на позиции, равной этому числу.
- Этот символ записывается в выходной поток.
- Символ перемещается в начало списка.
¶Пример
Рассмотрим алфавит из трёх символов: a, b, c. Исходная последовательность: a b c a b a.
| Шаг | Символ | Список до | Позиция | Список после | Выход |
|---|---|---|---|---|---|
| 1 | a | a b c | 0 | a b c | 0 |
| 2 | b | a b c | 1 | b a c | 1 |
| 3 | c | b a c | 2 | c b a | 2 |
| 4 | a | c b a | 2 | a c b | 2 |
| 5 | b | a c b | 2 | b a c | 2 |
| 6 | a | b a c | 1 | a b c | 1 |
Выходная последовательность: 0 1 2 2 2 1.
Декодирование:
| Шаг | Число | Список до | Символ | Список после | Выход |
|---|---|---|---|---|---|
| 1 | 0 | a b c | a | a b c | a |
| 2 | 1 | a b c | b | b a c | b |
| 3 | 2 | b a c | c | c b a | c |
| 4 | 2 | c b a | a | a c b | a |
| 5 | 2 | a c b | b | b a c | b |
| 6 | 1 | b a c | a | a b c | a |
Восстановленная последовательность: a b c a b a.
¶Свойства и характеристики
¶Обратимость
Преобразование является полностью обратимым. Декодирование восстанавливает исходную последовательность без потерь при условии, что известен исходный алфавит.
¶Эффективность
Основное преимущество MTF — преобразование локальных повторений в малые числа. Если в последовательности встречаются повторяющиеся символы, после первого появления они будут кодироваться числом 0, так как сразу перемещаются в начало списка. Это делает MTF особенно эффективным после BWT, который группирует одинаковые символы вместе.
¶Адаптивность
Список динамически изменяется в зависимости от входных данных, что позволяет алгоритму адаптироваться к локальным закономерностям. Символы, которые часто встречаются в последнее время, кодируются малыми числами.
¶Ограничения
- Зависимость от алфавита: размер алфавита должен быть известен заранее и фиксирован для всего процесса.
- Начальные затраты: первые появления редких символов кодируются большими числами, что может снижать эффективность на коротких последовательностях.
- Не является сжатием: MTF сам по себе не сжимает данные, а лишь подготавливает их для более эффективного сжатия другими алгоритмами.
¶Применение
¶Сжатие данных
Основное применение MTF — в составе алгоритмов сжатия, особенно текстовых данных. Наиболее известный пример — архиватор bzip2, который использует следующую цепочку преобразований:
- BWT (Burrows-Wheeler transform) — группировка одинаковых символов.
- MTF — преобразование позиций в малые числа.
- RLE (run-length encoding) — кодирование повторяющихся чисел.
- Статистическое кодирование (обычно кодирование Хаффмана).
¶Сжатие изображений
В некоторых реализациях формата JPEG 2000 и в алгоритмах сжатия изображений на основе вейвлет-преобразований MTF может использоваться для улучшения сжатия коэффициентов.
¶Обработка данных
MTF применяется в задачах, где требуется уменьшить энтропию данных перед статистическим кодированием, например, в системах хранения и передачи данных.
¶Варианты и модификации
¶Move-to-front с весами
В некоторых модификациях вместо полного перемещения символа в начало используется частичное перемещение, основанное на весах или частоте. Это может улучшить адаптацию к данным с неравномерным распределением.
¶MTF с ограниченной памятью
Для снижения вычислительных затрат и уменьшения влияния редких символов используются варианты с ограниченным размером списка или с забыванием старых символов.
¶MTF в комбинации с другими преобразованиями
MTF часто комбинируется с BWT, RLE, LZ-алгоритмами (LZ77, LZ78) для достижения более высоких степеней сжатия.
¶Интересные факты
- Алгоритм MTF интуитивно понятен и может быть реализован с использованием простых структур данных, таких как связанный список или массив с операцией сдвига.
- В контексте сжатия текстов на естественных языках MTF после BWT позволяет кодировать большинство символов числами 0, 1 и 2, что значительно снижает энтропию.
- MTF является примером адаптивного кодирования, где модель данных обновляется в процессе обработки.
¶Источники
- Leighton, B., & Storer, J. (1987). Data Compression Algorithms. Springer.
- Burrows, M., & Wheeler, D. J. (1994). A Block-sorting Lossless Data Compression Algorithm. Digital Equipment Corporation.
- Nelson, M., & Gailly, J.-L. (1996). The Data Compression Book. M&T Books.
- Salomon, D. (2007). Data Compression: The Complete Reference. Springer.