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

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

Теория

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

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

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

Выполнение

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

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

PPMd — это общедоступная реализация PPMII (PPM с наследованием информации) Дмитрия Шкарина, которая претерпела несколько несовместимых изменений. ^[1] он используется в формате файла RAR По умолчанию . Он также доступен в форматах файлов 7z и zip .

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

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

См. также

Источники

Клири, Дж.; Виттен, И. (апрель 1984 г.). «Сжатие данных с использованием адаптивного кодирования и частичного сопоставления строк». IEEE Транс. Коммун. 32 (4): 396–402. CiteSeerX 10.1.1.14.4305 . дои : 10.1109/TCOM.1984.1096090 .
Моффат, А. (ноябрь 1990 г.). «Реализация схемы сжатия данных PPM». IEEE Транс. Коммун. 38 (11): 1917–1921. CiteSeerX 10.1.1.120.8728 . дои : 10.1109/26.61469 .
Клири, Дж. Г.; Тихан, штат Вашингтон; Виттен, Айленд (1997). «Контексты неограниченной длины для PPM» . Компьютерный журнал . 40 (2_и_3). Оксфорд, Англия: Издательство Оксфордского университета: 67–75. дои : 10.1093/comjnl/40.2_and_3.67 . ISSN 0010-4620 .
К. Блум, Решение задач контекстного моделирования .
У. Дж. Тихан, Оценка вероятности для PPM , исходный источник с сайта archive.org .
Шюрманн, Т.; Грассбергер, П. (сентябрь 1996 г.). «Оценка энтропии последовательностей символов». Хаос . 6 (3): 414–427. arXiv : cond-mat/0203436 . Бибкод : 1996Хаос...6..414S . дои : 10.1063/1.166191 . ПМИД 12780271 . S2CID 10090433 .

Ссылки

^ "BMF, PPMd Всё о сжатии данных, изображений и видео" . compression.ru (in Russian). NOTE: requires manually setting the "Cyrillic (Windows)" encoding in browser.

Внешние ссылки

Набор компрессоров PPM с тестами
BICOM, биективный компрессор PPM. Архивировано 15 апреля 2004 г. в Wayback Machine.
«Арифметическое кодирование + Статистическое моделирование = Сжатие данных», Часть 2
(на русском языке) Компрессор PPMd Дмитрия Шкарина
Сжатие PPM в C++, Рене Пушингер

[1] "BMF, PPMd Всё о сжатии данных, изображений и видео" . compression.ru (in Russian). NOTE: requires manually setting the "Cyrillic (Windows)" encoding in browser.

[1]