Войти
Прогноз по частичному совпадению ( PPM ) - это адаптивный статистический метод сжатия данных, основанный на контекстном моделировании и прогнозировании. Модели PPM используют набор предыдущих символов в несжатом потоке символов для предсказания следующего символа в потоке. Алгоритмы PPM также могут использоваться для кластеризации данных в прогнозируемые группы в кластерном анализе.
Прогнозы обычно сводятся к символу рейтингу. Каждый символ (буква, бит или любой другой объем данных) ранжируется перед его сжатием, и система ранжирования определяет соответствующее кодовое слово (и, следовательно, степень сжатия). Во многих алгоритмах сжатия ранжирование эквивалентно оценке функции массы вероятности. Учитывая предыдущие буквы (или учитывая контекст), каждому символу присваивается вероятность. Например, в арифметическом кодировании символы ранжируются по их вероятностям появления после предыдущих символов, и вся последовательность сжимается до единственной дроби, которая вычисляется в соответствии с этими вероятностями.
Число предыдущих символов n определяет порядок модели PPM, которая обозначается как PPM (n). Неограниченные варианты, в которых контекст не имеет ограничений по длине, также существуют и обозначаются как PPM *. Если невозможно сделать прогноз на основе всех n символов контекста, выполняется попытка прогнозирования с помощью n - 1 символа. Этот процесс повторяется до тех пор, пока не будет найдено совпадение или пока в контексте не останутся символы. В этот момент делается фиксированный прогноз.
Большая часть работы по оптимизации модели PPM связана с обработкой входных данных, которые еще не присутствовали во входном потоке. Очевидный способ справиться с ними - создать «невидимый» символ, который запускает escape-последовательность . Но какова вероятность того, что символ никогда не видел? Это называется проблемой нулевой частоты. В одном варианте используется оценка Лапласа, которая присваивает «невидимому» символу фиксированное псевдосчет, равное единице. Вариант, называемый PPMd, увеличивает псевдосчет «никогда не виденного» символа каждый раз, когда используется «никогда не виданный» символ. (Другими словами, PPMd оценивает вероятность появления нового символа как отношение количества уникальных символов к общему количеству наблюдаемых символов).
Реализации сжатия PPM сильно различаются по другим деталям. Фактический выбор символа обычно записывается с использованием арифметического кодирования, хотя также возможно использование кодирования Хаффмана или даже некоторого типа методики кодирования словаря. Базовая модель, используемая в большинстве алгоритмов PPM, также может быть расширена для прогнозирования нескольких символов. Также возможно использовать немарковское моделирование для замены или дополнения марковского моделирования. Размер символа обычно статический, обычно один байт, что упрощает обычную обработку файлов любого формата.
Опубликованные исследования этого семейства алгоритмов можно найти еще в середине 1980-х годов. Программные реализации не были популярны до начала 1990-х годов, потому что алгоритмы PPM требовали значительного объема RAM. Последние реализации PPM относятся к числу наиболее эффективных программ сжатия без потерь для текста на естественном языке.
PPMd - это реализация PPMII Дмитрия Шкарина. По умолчанию он используется в RAR. Он также используется 7-Zip как один из нескольких возможных методов сжатия в формате файла 7z.
Попытки улучшить алгоритмы PPM привели к серии алгоритмов сжатия данных PAQ.
Алгоритм PPM вместо сжатия используется для повышения эффективности пользовательского ввода в программе альтернативного метода ввода Dasher.
