Оглавление [Скрыть]
Преобразование с перемещением вперед
-
Основы MTF-преобразования
- MTF-преобразование повышает производительность энтропийного сжатия.
- Алгоритм был опубликован Борисом Рябко в 1980 году и заново открыт Дж. Бентли в 1986 году.
-
Принцип работы MTF
- Каждый символ в данных заменяется индексом в стеке “недавно использованных символов”.
- Длинные последовательности одинаковых символов заменяются нулями, а редко используемые символы – большими числами.
- В конце данные преобразуются в последовательность целых чисел, что обычно приводит к маленьким числам при наличии локальных корреляций.
-
Реализация MTF
- Для кодирования используется связанный список, а для декодирования – специализированные структуры данных.
- Для декодирования можно использовать самоорганизующийся список “Вперед”.
-
Пример реализации на Python
- В Python представлена возможная реализация MTF-преобразования.
- Обратный процесс восстанавливает исходный текст.
-
Применение MTF в алгоритмах сжатия
- MTF используется для уменьшения энтропии сообщений с локальными частотными корреляциями.
- В сочетании с преобразованием Берроуза-Уилера MTF значительно повышает эффективность сжатия.
-
Проблемы и улучшения MTF
- Базовый MTF вносит одинаковые изменения для всех символов, что может снизить степень сжатия.
- Были разработаны различные модификации MTF для улучшения эффективности и предотвращения снижения степени сжатия.
-
Перемещение связанного списка на передний план
- “Переместить на передний план” – это тип динамического связанного списка, где элементы перемещаются на передний план при обращении к ним.
Полный текст статьи: