Предсказание по частичному совпадению

Предсказание по частичному совпадению (англ. Prediction by Partial Matching, PPM) — это адаптивный статистический метод сжатия данных без потерь, основанный на контекстном моделировании и арифметическом кодировании. Алгоритм предсказывает следующий символ последовательности, анализируя конечное число предыдущих символов (контекст) и используя для оценки вероятности модель, построенную на основе уже обработанных данных. PPM относится к классу методов, обеспечивающих высокую степень сжатия, особенно на текстовых данных, и является одним из наиболее эффективных универсальных алгоритмов, предшествовавших современным нейросетевым подходам.

История

Метод PPM был впервые предложен Джоном Клири и Йеном Уиттеном в 1984 году в статье «Сжатие данных с использованием адаптивного кодирования по частичному совпадению» (англ. Data Compression Using Adaptive Coding of Partial String Matching). Разработка велась в Университете Калгари (Канада) и была направлена на улучшение эффективности сжатия текстовой информации по сравнению с алгоритмами LZ77 и LZ78, которые на тот момент доминировали в области архивации.

В 1987 году Алок Мишра и Йен Уиттен представили улучшенную версию — PPMC (PPM с методом исключения), которая позволила повысить точность предсказаний за счёт исключения уже использованных символов из контекста. В 1990-х годах алгоритм был доработан в рамках конкурса по сжатию текстов (Calgary Corpus, Canterbury Corpus), где PPM демонстрировал одни из лучших результатов, уступая лишь специализированным методам, таким как PAQ.

В 2000-х годах PPM послужил основой для ряда коммерческих и открытых архиваторов, включая RAR (в режиме сжатия текста), 7z (с фильтром PPMd) и PAQ. Впоследствии, с развитием нейронных сетей и методов глубокого обучения, PPM утратил лидерство в области сжатия, но остаётся важным эталонным алгоритмом для задач моделирования последовательностей.

Принцип работы

Контекстное моделирование

Основная идея PPM заключается в том, что вероятность появления следующего символа в последовательности зависит от ограниченного числа предыдущих символов — контекста. Длина контекста (порядок модели) обозначается как \( k \). Например, для \( k = 2 \) предсказание символа \( c \) после последовательности «ab» будет основано на статистике, собранной для контекста «ab» из уже обработанного потока данных.

Модель порядка \( k \)

Алгоритм хранит таблицу частот всех возможных контекстов длины \( k \) и символов, которые встречались после них. Для каждого контекста вычисляется вероятность появления каждого символа как отношение числа его появлений к общему числу появлений контекста. Если контекст длины \( k \) не встречался в обработанных данных (или встречался, но символ \( c \) в нём не наблюдался), алгоритм переходит к контексту длины \( k-1 \), и так далее, вплоть до контекста длины 0 (модель нулевого порядка, где вероятность символа равна его частоте во всём потоке).

Метод исключения

Для повышения точности предсказаний используется метод исключения (англ. exclusion). Если символ не был найден в контексте порядка \( k \), то при переходе к контексту порядка \( k-1 \) из рассмотрения исключаются символы, которые уже были учтены в более высоких порядках. Это предотвращает двойной учёт вероятностей и улучшает сжатие.

Арифметическое кодирование

Полученные вероятности передаются в арифметический кодер, который преобразует последовательность символов в битовый поток. Арифметическое кодирование позволяет закодировать символ с дробным числом бит, что особенно важно для редких символов.

Варианты алгоритма

PPM-A, PPM-B, PPMC

Изначально были предложены три варианта: PPM-A (простая модель), PPM-B (с учётом порядка) и PPMC (с методом исключения). PPMC стал наиболее распространённым благодаря лучшему сжатию.

PPMd

PPMd (PPM with Dictionary) — модификация, разработанная Дмитрием Шкариным в 1990-х годах. В PPMd используется динамическое построение модели с ограничением памяти, а также специальные методы для обработки длинных контекстов. PPMd реализован в архиваторах 7-Zip и WinRAR.

PPMZ

PPMZ — улучшенная версия, созданная Чарльзом Блумом в 1998 году. Она добавляет механизмы для обработки контекстов переменной длины и адаптивного выбора порядка модели, что позволяет достичь сжатия, близкого к теоретическому пределу для текстовых данных.

PPMonstr

PPMonstr — вариант, разработанный для сжатия бинарных данных и изображений. Он использует контексты, основанные не только на предыдущих символах, но и на их битовом представлении.

Применение

Сжатие текстов

PPM традиционно демонстрирует высокую степень сжатия на текстовых данных, особенно на естественных языках с повторяющимися структурами (например, английский, русский). В тестах на корпусе Calgary Corpus (набор текстовых файлов) PPMd сжимает тексты в среднем на 10–15 % лучше, чем LZMA.

Архивация

Алгоритм PPM реализован в ряде архиваторов:

• 7-Zip (фильтр PPMd для сжатия текстовых файлов)
• WinRAR (режим сжатия текста с использованием PPM)
• PAQ (гибридный алгоритм, включающий PPM-подобные модели)
• bzip2 (использует преобразование Барроуза-Уиллера, но в некоторых версиях — PPM)

Моделирование последовательностей

PPM применяется в задачах, где требуется предсказание следующего элемента последовательности:

• Коррекция опечаток (предсказание следующего слова в тексте)
• Генерация текста (простые модели, предшествовавшие нейросетевым)
• Анализ ДНК (предсказание нуклеотидных последовательностей)
• Сжатие изображений (в комбинации с вейвлет-преобразованием)

Критика и ограничения

Вычислительная сложность

PPM требует значительных вычислительных ресурсов, особенно при больших порядках контекста (\( k > 5 \)). Для каждого символа необходимо обновлять таблицу частот, что замедляет работу на больших объёмах данных. В отличие от алгоритмов LZ, PPM не может быть эффективно реализован на аппаратном уровне.

Память

Модель PPM хранит все встреченные контексты, что при обработке больших файлов (сотни мегабайт) может приводить к переполнению памяти. Для ограничения используются методы сброса модели (например, после каждого 10 МБ данных) или усечения контекстов.

Чувствительность к типу данных

PPM плохо сжимает бинарные данные (исполняемые файлы, изображения, видео), где структура не является последовательной и предсказуемой. Для таких данных более эффективны алгоритмы LZMA или BWT.

Сравнение с нейросетевыми методами

Современные нейросетевые модели (например, LSTM, Transformer) превосходят PPM по степени сжатия на текстовых данных, но требуют на порядки больше вычислительных ресурсов и памяти. PPM остаётся актуальным для задач, где важна скорость и низкое потребление памяти.

Интересные факты

• Алгоритм PPM лёг в основу стандарта сжатия текстов в формате PDF (версия 1.5 и выше).
• В 2000 году PPMd был включён в состав ядра Linux для сжатия файлов подкачки.
• PPM является одним из немногих алгоритмов, для которых доказана асимптотическая оптимальность (при бесконечной длине контекста и бесконечном объёме данных).

Источники

• Cleary, J. G., & Witten, I. H. (1984). Data Compression Using Adaptive Coding of Partial String Matching. IEEE Transactions on Communications, 32(4), 396–402.
• Moffat, A. (1990). Implementing the PPM Data Compression Scheme. IEEE Transactions on Communications, 38(11), 1917–1921.
• Bloom, C. (1998). PPMZ: High-Compression Text Compression. Dr. Dobb's Journal.
• Salomon, D. (2007). Data Compression: The Complete Reference (4th ed.). Springer.
• Корпус Calgary Corpus — набор тестовых файлов для оценки алгоритмов сжатия.