Ppm prediction by partial matching предсказание по частичному совпадению это

Методы контекстного моделирования

Алгоритмы PPM

Техника контекстного моделирования Prediction by Partial Matching (предсказание по частичному совпадению), предложенная в 1984 году Клири (Cleary) и Уиттеном (Witten) [3.5], является одним из самых известных подходов к сжатию качественных данных и уж точно самым популярным среди контекстных методов. Значимость подхода обусловлена и тем фактом, что алгоритмы, причисляемые к PPM , неизменно обеспечивают в среднем наилучшее сжатие при кодировании данных различных типов и служат стандартом, «точкой отсчета» при сравнении универсальных алгоритмов сжатия.

Перед собственно рассмотрением алгоритмов PPM необходимо сделать замечание о корректности используемой терминологии. На протяжении примерно 10 лет — с середины 1980-х годов до середины 1990-х — под PPM понималась группа методов с вполне определенными характеристиками. В последние годы, вероятно из-за резкого увеличения числа всевозможных гибридных схем и активного практического использования статистических моделей для сжатия, произошло смешение понятий, и термин » PPM » часто используется для обозначения контекстных методов вообще.

Ниже будет описан некий обобщенный алгоритм PPM , а затем особенности конкретных распространенных схем.

Как и в случае многих других контекстных методов, для каждого контекста, встречаемого в обрабатываемой последовательности, создается своя контекстная модель КМ. При этом под контекстом понимается последовательность элементов одного типа — символов, пикселов, чисел, но не набор разнородных объектов. Далее вместо слова «элемент» мы будем использовать «символ». Каждая КМ включает в себя счетчики всех символов, встреченных в соответствующем контексте.

PPM относится к адаптивным методам моделирования. Исходно кодеру и декодеру поставлена в соответствие начальная модель источника данных . Будем считать, что она состоит из КМ(-1), присваивающей одинаковую вероятность всем символам алфавита входной последовательности. После обработки текущего символа кодер и декодер изменяют свои модели одинаковым образом, в частности, наращивая величину оценки вероятности рассматриваемого символа. Следующий символ кодируется (декодируется) на основании новой, измененной модели, после чего модель снова модифицируется и т.д. На каждом шаге обеспечивается идентичность модели кодера и декодера за счет применения одинакового механизма ее обновления.

В PPM используется неявное взвешивание оценок. Попытка оценки символа начинается с КМ(N) , где N является параметром алгоритма и называется порядком PPM -модели. В случае нулевой частоты символа в КМ текущего порядка осуществляется переход к КМ меньшего порядка за счет использования механизма уходов ( escape strategy ), рассмотренного в предыдущем пункте.

Фактически, вероятность ухода — это суммарная вероятность всех символов алфавита входного потока, еще ни разу не появлявшихся в контексте. Любая КМ должна давать отличную от нуля оценку вероятности ухода. Исключения из этого правила возможны только в тех случаях, когда значения всех счетчиков КМ для всех символов алфавита отличны от нуля, то есть любой символ может быть оценен в рассматриваемом контексте. Оценка вероятности ухода традиционно является одной из основных проблем алгоритмов с неявным взвешиванием, и она будет специально рассмотрена ниже в пункте «Оценка вероятности ухода».

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

1. источник является марковским с порядком N , т.е. вероятность генерации символа зависит от N предыдущих символов и только от них;
2. источник имеет такую дополнительную особенность, что чем ближе располагается один из символов контекста к текущему символу, тем больше корреляция между ними.

Таким образом, механизм уходов первоначально рассматривался лишь как вспомогательный прием, позволяющий решить проблему кодирования символов, ни разу не встречавшихся в контексте порядка N . В идеале, достигаемом после обработки достаточно длинного блока , никакого обращения к КМ порядка меньше N происходить не должно. Иначе говоря, причисление классических алгоритмов PPM к методам, производящим взвешивание, пусть и неявным образом, является не вполне корректным.

При сжатии очередного символа выполняются следующие действия.

Если символ s обрабатывается с использованием PPM -модели порядка N , то, как мы уже отмечали, в первую очередь рассматривается KM(N) . Если она оценивает вероятность s числом, не равным нулю, то сама и используется для кодирования s. Иначе выдается сигнал в виде символа ухода, и на основе меньшей по порядку КМ(N-1) производится очередная попытка оценить вероятность s. Кодирование происходит через уход к КМ меньших порядков до тех пор, пока s не будет оценен. КМ(-1) гарантирует, что это в конце концов произойдет. Таким образом, каждый символ кодируется серией кодов символа ухода, за которой следует код самого символа. Из этого следует, что вероятность ухода также можно рассматривать как вероятность перехода к контекстной модели меньшего порядка.

Если в процессе оценки обнаруживается, что текущий рассматриваемый контекст встречается в первый раз, то для него создается KM(N) .

При оценке вероятности символа в КМ порядка o можно исключить из рассмотрения все символы, которые содержатся в KM(0+1) , поскольку ни один из них точно не является символом s . Для этого в текущей KM(o) нужно замаскировать, т.е. временно установить в ноль, значения счетчиков всех символов, имеющихся в КМ(o+1). Такая техника называется методом исключения (exclusion).

После собственно кодирования символа обычно осуществляется обновление статистики всех КМ, использованных при оценке его вероятности, за исключением статической КМ(-1). Такой подход называется методом исключения при обновлении. Простейшим способом модификации является инкремент счетчиков символа в этих КМ. Подробнее о стратегиях обновления будет сказано в пункте «Обновление счетчиков символов».

Источник

Прогноз по частичному совпадению — Prediction by partial matching — Wikipedia

Прогноз по частичному совпадению (PPM) является адаптивным статистический Сжатие данных техника, основанная на контекстное моделирование и прогноз. Модели PPM используют набор предыдущих символов в несжатом потоке символов для предсказания следующего символа в потоке. Алгоритмы PPM также можно использовать для кластеризации данных в прогнозируемые группы в кластерный анализ.

Содержание

Теория

Прогнозы обычно сводятся к символ рейтинги [ требуется разъяснение ] . Каждый символ (буква, бит или любой другой объем данных) ранжируется перед сжатием, и система ранжирования определяет соответствующее кодовое слово (и, следовательно, степень сжатия). Во многих алгоритмах сжатия ранжирование эквивалентно функции массы вероятности оценка. Учитывая предыдущие буквы (или учитывая контекст), каждому символу присваивается вероятность. Например, в арифметическое кодирование символы ранжируются по их вероятностям появления после предыдущих символов, и вся последовательность сжимается до единственной дроби, которая вычисляется в соответствии с этими вероятностями.

Количество предыдущих символов, п, определяет порядок модели PPM, которая обозначается как PPM (п). Неограниченные варианты, в которых контекст не имеет ограничений по длине, также существуют и обозначаются как PPM *. Если невозможно сделать прогноз на основе всех п символы контекста, с которыми делается попытка предсказания п — 1 символ. Этот процесс повторяется до тех пор, пока не будет найдено совпадение или пока в контексте не останется символов. В этот момент делается фиксированный прогноз.

Большая часть работы по оптимизации модели PPM заключается в обработке входных данных, которые еще не вошли во входной поток. Очевидный способ справиться с ними — создать «невидимый» символ, который запускает escape-последовательность [ требуется разъяснение ] . Но какова вероятность того, что символ никогда не видел? Это называется проблема нулевой частоты. В одном варианте используется оценка Лапласа, которая присваивает «невидимому» символу фиксированный псевдосчет одного. Вариант, называемый PPMd, увеличивает псевдосчет «никогда не виденного» символа каждый раз, когда используется «никогда не виданный» символ. (Другими словами, PPMd оценивает вероятность появления нового символа как отношение количества уникальных символов к общему количеству наблюдаемых символов).

Выполнение

Реализации сжатия PPM сильно различаются по другим деталям. Фактический выбор символа обычно записывается с использованием арифметическое кодирование, хотя также можно использовать Кодирование Хаффмана или даже какой-то кодирование словаря техника. Базовая модель, используемая в большинстве алгоритмов PPM, также может быть расширена для прогнозирования нескольких символов. Также возможно использовать немарковское моделирование, чтобы заменить или дополнить марковское моделирование. Размер символа обычно статический, обычно один байт, что упрощает обычную обработку файлов любого формата.

Опубликованные исследования этого семейства алгоритмов можно найти еще в середине 1980-х годов. Программные реализации не были популярны до начала 1990-х годов, потому что алгоритмы PPM требовали значительного количества баран. Недавние реализации PPM являются одними из самых эффективных сжатие без потерь программы для естественный язык текст.

PPMd — это реализация PPMII Дмитрия Шкарина. Он используется в RAR по умолчанию. Он также используется 7-молния как один из нескольких возможных методов сжатия в 7z формат файла.

Попытки улучшить алгоритмы PPM привели к PAQ серия алгоритмов сжатия данных.

Алгоритм PPM вместо сжатия используется для повышения эффективности пользовательского ввода в программе с альтернативным методом ввода. Dasher.

Источник

Алгоритм сжатия PPM

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

Длина контекста, который используется при предсказании обычно сильно ограничена. Эта длина обозначается n и определяет порядок модели PPM, что обозначается как PPM(n). Неограниченные модели так же существуют и обозначаются просто PPM*. Если предсказание символа по контексту из n символов не может быть произведено, то происходит попытка предсказать его с помощью n-1 символов. Рекурсивный переход к моделям с меньшим порядком происходит пока предсказание не произойдёт в одной из моделей, либо когда контекст станет нулевой длины (n=0). Модели степени 0 и −1 следует описать особо. Модель нулевого поpядка эквивалента случаю контекстно-свободного моделиpования, когда веpоятность символа опpеделяется исключительно из частоты его появления в сжимаемом потоке данных. Подобная модель обычно пpименяется вместе с кодиpованием по Хаффману. Модель поpядка −1 пpедставляют собой статическую модель, пpисваивающую веpоятности символа опpеделенное фиксиpованное значение; обычно все символы, котоpые могут встpетиться в сжимаемом потоке данных, пpи этом считаются pавновеpоятными. Для получения хоpошей оценки веpоятности символа необходимо учитывать контексты pазных длин. PPM пpедставляет собой ваpиант стpатегии пеpемешивания, когда оценки веpоятностей, сделанные на основании контекстов pазных длин, объединяются в одну общую веpоятность. Полученная оценка кодиpуется любым энтpопийным кодеpом (ЭК), обычно это некая pазновидность аpифметического кодеpа. На этапе энтpопийного кодиpования и пpоисходит собственно сжатие.

Большое значение для алгоритма PPM имеет проблема обработки новых символов, ещё не встречавшихся во входном потоке. Это проблема носит название проблема нулевой частоты. Некоторые варианты реализаций PPM полагают счётчик нового символа равным фиксированной величине, например, единице. Другие реализации, как например, PPM-D, увеличивают псевдосчётчик нового символа каждый раз, когда, действительно, в потоке появляется новый символ. (Другими словами, PPM-D оценивает вероятность появления нового символа как отношение числа уникальных символов к общему числу используемых символов).

Опубликованные исследование алгоритмов семейства PPM появились в середине 1980-х годов. Программные реализации не были популярны до 1990-х годов, потому как модели PPM требуют значительное количество оперативной памяти. Современные реализации PPM являются одними из лучших среди алгоритмов сжатия без потерь для текстов на естественном языке. [1] [2]

Практическое использование

Варианты алгоритма PPM на данный момент широко используются, главным образом для компрессии избыточной информации и текстовых данных. Следующие архиваторы используют PPM [3] :

• boa, основан на PPMz (Ian Sutton)
• HA, PPM order 4, оригинальный метод оценки вероятности ухода (Harry Hirvola)
• lgha, основан на коде архиватора ha (Юрий Ляпко)
• ppmpacktc, основан на коде PPMd, PPMz, PPMVC и коде HA с реализацией hsc (Александр Мясников)
• arhangel, основан на алгоритмах ha с добавлением набора фильтров для различных данных (Юрий Ляпко)
• PPMd — реализация PPM order-2..16, применяется наследование информации («дурилка» Дмитрия Шкарина)
• ppmz — реализован метод Z (Charles Bloom)
• rk — реализация PPMz с набором фильтров (Malcolm Taylor)
• rkuc — PPM с порядками 16-12-8-5-3-2-1-0 (Malcolm Taylor)
• rkive (Malcolm Taylor)
• x1 — реализация LZP и PPM (Stig Valentini)
• RAR (версии 3 и выше) — реализация варианта PPMd, PPMII
• 7-Zip — реализация варианта PPMd
• WinZip (версии 10 и выше) — реализация варианта PPMd

Источник

Ppm prediction by partial matching предсказание по частичному совпадению это

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

Длина контекста, который используется при предсказании обычно сильно ограничена. Эта длина обозначается n и определяет порядок модели PPM, что обозначается как PPM(n). Неограниченные модели так же существуют и обозначаются просто PPM*. Если предсказание символа по контексту из n символов не может быть произведено, то происходит попытка предсказать его с помощью n-1 символов. Рекурсивный переход к моделям с меньшим порядком происходит пока предсказание не произойдёт в одной из моделей, либо когда контекст станет нулевой длины (n=0). Модели степени 0 и −1 следует описать особо. Модель нулевого поpядка эквивалента случаю контекстно-свободного моделиpования, когда веpоятность символа опpеделяется исключительно из частоты его появления в сжимаемом потоке данных. Подобная модель обычно пpименяется вместе с кодиpованием по Хаффману. Модель поpядка −1 пpедставляют собой статическую модель, пpисваивающую веpоятности символа опpеделенное фиксиpованное значение; обычно все символы, котоpые могут встpетиться в сжимаемом потоке данных, пpи этом считаются pавновеpоятными. Для получения хоpошей оценки веpоятности символа необходимо учитывать контексты pазных длин. PPM пpедставляет собой ваpиант стpатегии пеpемешивания, когда оценки веpоятностей, сделанные на основании контекстов pазных длин, объединяются в одну общую веpоятность. Полученная оценка кодиpуется любым энтpопийным кодеpом (ЭК), обычно это некая pазновидность аpифметического кодеpа. На этапе энтpопийного кодиpования и пpоисходит собственно сжатие.

Большое значение для алгоритма PPM имеет проблема обработки новых символов, ещё не встречавшихся во входном потоке. Это проблема носит название проблема нулевой частоты. Некоторые варианты реализаций PPM полагают счётчик нового символа равным фиксированной величине, например, единице. Другие реализации, как например, PPM-D, увеличивают псевдосчётчик нового символа каждый раз, когда, действительно, в потоке появляется новый символ. (Другими словами, PPM-D оценивает вероятность появления нового символа как отношение числа уникальных символов к общему числу используемых символов).

Опубликованные исследование алгоритмов семейства PPM появились в середине 1980-х годов. Программные реализации не были популярны до 1990-х годов, потому как модели PPM требуют значительное количество оперативной памяти. Современные реализации PPM являются лучшими среди алгоритмов сжатия без потерь для текстов на естественном языке.

Практическое использование

Варианты алгоритма PPM на данный момент широко используются, главным образом для компрессии избыточной информации и текстовых данных. Следующие архиваторы используют PPM [1] :

• boa, основан на PPMz (Ian Sutton)
• HA, PPM order 4, оригинальный метод оценки вероятности ухода (Harry Hirvola)
• lgha, основан на коде архиватора ha (Юрий Ляпко)
• ppmpacktc, основан на коде PPMd, PPMz, PPMVC и коде HA с реализацией hsc (Александр Мясников)
• arhangel, основан на алгоритмах ha с добавлением набора фильтров для различных данных (Юрий Ляпко)
• PPMd — реализация PPM order-2..16, применяется наследование информации (Дмитрий Шкарин)
• ppmz — реализован метод Z (Charles Bloom)
• rk — реализация PPMz с набором фильтров (Malcolm Taylor)
• rkuc — PPM с порядками 16-12-8-5-3-2-1-0 (Malcolm Taylor)
• rkive (Malcolm Taylor)
• x1 — реализация LZP и PPM (Stig Valentini)
• RAR — реализация варианта PPMd
• 7-Zip — реализация варианта PPMd
• WinZip (версии 10 и выше) — реализация варианта PPMd

Примечания

Методы сжатия
Теория	Информация Собственная · Взаимная · Энтропия · Условная энтропия · Сложность · Избыточность Единицы измерения Бит · Нат · Ниббл · Хартли · Формула Хартли
Без потерь	Энтропийное сжатие Алгоритм Хаффмана · Адаптивный алгоритм Хаффмана · Арифметическое кодирование (Алгоритм Шеннона — Фано · Интервальное) · Коды Голомба · Дельта · Универсальный код (Элиаса · Фибоначчи) Словарные методы RLE · DEFLATE · LZ (LZ77/LZ78 · LZSS · LZW · LZWL · LZO · LZMA · LZX · LZRW · LZJB · LZT) Прочее RLE · CTW · BWT · PPM · DMC
Аудио	Теория Свёртка · PCM · Алиасинг · Дискретизация · Теорема Котельникова Методы LPC (LAR · LSP) · WLPC · CELP · ACELP · A-закон · μ-закон · MDCT · Преобразование Фурье · Психоакустическая модель Прочее Dynamic range compression · Сжатие речи · Полосное кодирование
Изображения	Термины Цветовое пространство · Пиксел · Chroma subsampling · Артефакты сжатия Методы RLE · DPCM · Фрактальный · Wavelet · EZW · SPIHT · LP · ДКП · ПКЛ Прочее Битрейт · Test images · PSNR · Квантование
Видео	Термины Характеристики видео · Кадр · Типы кадров · Качество видео Методы Компенсация движения · ДКП · Квантование Прочее Видеокодек · Rate distortion theory (CBR · ABR · VBR)
См. также: Программы для сжатия данных • Стандарты и форматы сжатия

Wikimedia Foundation . 2010 .

Смотреть что такое «PPM» в других словарях:

ppm — 〈Abk. für engl.〉 part per million, gibt an, dass auf eine Million Teilchen einer Sorte ein Teilchen einer anderen Sorte kommt * * * ppm ↑ pp Einheiten. * * * I ppm [Abk. für Parts per Million, dt. »Teile pro Million«], Mengenangaben … Universal-Lexikon

Ppm — ppm, PPM: Миллионная доля (ppm, от англ. parts per million частей на миллион) единица измерения концентрации. ppm (англ. pages per minute) единица измерения скорости работы принтеров и сканеров. PPM формат… … Википедия

ppm — parts per million; a measurement showing how much of a particular substance something contains: • employees exposed to formaldehyde concentrations of 1 ppm or more * * * ppm UK US noun [plural] MEASURES ► ABBREVIATION FOR parts per million: the… … Financial and business terms

PPM — (PPM, ppm) Proporción de la concentración de una sustancia con respecto a la concentración de otra, como una unidad de soluto disuelta en un millón de unidades de disolvente. Se puede expresar también en términos de peso peso, volumen volumen o… … Diccionario médico

PPM — may refer to:* In music: ** Please Please Me , the first album by The Beatles. * In computing: **Perl package manager, a packaging system for distributing precompiled modules for use with the Activestate binary distribution of the Perl… … Wikipedia

PPM — puede referir a: Partes por millón, unidad de medida. Páginas por minuto, referido a la velocidad de impresión Pulsaciones por minuto, unidad utilizada para expresar la velocidad de una pieza en música Partido Popular Monárquico, Portugal… … Wikipedia Español

ppm — Abreviatura de partes por millón. Diccionario Mosby Medicina, Enfermería y Ciencias de la Salud, Ediciones Hancourt, S.A. 1999 … Diccionario médico

PPM — ● PPM Abréviation de l anglais part per million (partie par million), désignant une concentration d une substance égale à 10−6, soit un millionième … Encyclopédie Universelle

ppm — simb. TS chim. parts per million, parti per milione … Dizionario italiano

ppm — 〈Physik; Abk. für engl.〉 part per million, gibt an, dass auf eine Million Teilchen einer Sorte ein Teilchen einer anderen Sorte kommt … Lexikalische Deutsches Wörterbuch

Источник