Предсказание путем частичного совпадения
-
Основы прогнозирования путем частичного сопоставления (PPM)
- PPM — адаптивный метод сжатия данных, основанный на контекстном моделировании и прогнозировании.
- Модели PPM используют предыдущие символы для предсказания следующего символа в потоке данных.
- Алгоритмы PPM могут объединять данные в прогнозируемые группы при кластерном анализе.
-
Теория и реализация
- Прогнозы ранжируют символы и определяют кодовое слово для сжатия.
- Ранжирование символов эквивалентно оценке функции массы вероятности.
- Количество предыдущих символов определяет порядок следования модели PPM.
- Существуют неограниченные варианты PPM, включая PPM* без ограничений по длине контекста.
- Если невозможно сделать прогноз на основе всех контекстных символов, используется прогнозирование с использованием меньшего количества символов.
- Обработка входных данных, которые еще не появились в потоке, включает создание «невидимых» символов.
- Проблема нулевой частоты решается с помощью оценки Лапласа или PPMd.
-
Реализации и эффективность
- Реализации PPM различаются и могут использовать арифметическое кодирование, кодирование Хаффмана или словарное кодирование.
- Базовая модель PPM может быть расширена для предсказания нескольких символов.
- Немарковское моделирование может быть использовано для замены или дополнения марковского моделирования.
- Размер символа обычно составляет один байт, что упрощает обработку файлов.
- PPMd — популярная реализация PPMII, доступная в форматах RAR, 7z и zip.
-
Развитие и применение
- Алгоритмы PPM привели к созданию семейства алгоритмов сжатия данных PAQ.
- PPM используется не только для сжатия, но и для повышения эффективности пользовательского ввода в программе Dasher.
-
Источники и рекомендации
- Ссылки на внешние источники и наборы компрессоров PPM с контрольными показателями доступны в статье.
Полный текст статьи: