Прогноз по частичному совпадению - Википедия - Prediction by partial matching

Прогноз по частичному совпадению (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.

Смотрите также

Источники

  • Cleary, J .; Виттен, И. (апрель 1984 г.). «Сжатие данных с использованием адаптивного кодирования и частичного сопоставления строк». IEEE Trans. Commun. 32 (4): 396–402. CiteSeerX  10.1.1.14.4305. Дои:10.1109 / TCOM.1984.1096090.
  • Моффат, А. (ноябрь 1990 г.). «Реализация схемы сжатия данных PPM». IEEE Trans. Commun. 38 (11): 1917–1921. CiteSeerX  10.1.1.120.8728. Дои:10.1109/26.61469.
  • Cleary, J. G .; Teahan, W. J .; Виттен, И. Х. «Контексты неограниченной длины для PPM». Компьютерный журнал. Оксфорд, Англия: Издательство Оксфордского университета. 40 (2_and_3): Страницы 67–75. Дои:10.1093 / comjnl / 40.2_and_3.67. ISSN  0010-4620.
  • К. Блум, Решение задач контекстного моделирования.
  • W.J. Teahan, Оценка вероятности PPM.
  • SchüRmann, T .; Грассбергер, П. (сентябрь 1996 г.). «Энтропийная оценка символьных последовательностей». Хаос. 6 (3): 414–427. arXiv:cond-mat / 0203436. Bibcode:1996 Хаос ... 6..414S. Дои:10.1063/1.166191. PMID  12780271.

Рекомендации

внешняя ссылка