Prediction by partial matching
패턴 일치 예측 또는 PPM은 통계학적 자료 압축 기법 중 하나로, 맥락 모델링과 예측을 기반으로 한 적응형 기법이다. PPM 모델은 압축되지 않은 심벌 스트림에서 이전의 심벌 집합을 사용하여 다음 심벌을 예측한다. PPM 알고리즘은 또한 클러스터 분석에서 데이터를 예측된 그룹으로 클러스터링하는 데에도 사용될 수 있다.
이론[편집]
예측은 보통 심벌 순위로 축소된다. 각 심벌(문자, 비트 또는 다른 양의 데이터)은 압축되기 전에 순위가 매겨지며, 순위 시스템은 해당 코드워드(압축률)를 결정한다. 많은 압축 알고리즘에서 순위는 확률 질량 함수 추정과 동등하다. 주어진 이전 문자(또는 맥락)에 따라 각 심벌에는 확률이 할당된다. 예를 들어, 산술 부호화에서 심벌은 이전 심벌 이후에 나타날 확률에 따라 순위가 매겨지며, 전체 시퀀스는 이러한 확률에 따라 계산된 단일 분수로 압축된다.
이전 심벌의 수, n은 PPM 모델의 순서를 결정하며, PPM(n)로 표시된다. 길이 제한이 없는 맥락을 가진 변형도 존재하며, 이는 PPM*로 표시된다. 모든 n 맥락 심벌을 기반으로 예측이 불가능한 경우, n − 1 심벌로 예측이 시도된다. 이 과정은 일치가 발견될 때까지 또는 맥락에 더 이상 심벌이 남아 있지 않을 때까지 반복된다. 그 시점에 고정된 예측이 이루어진다.
PPM 모델을 최적화하는 대부분의 작업은 입력 스트림에서 이미 발생하지 않은 입력을 처리하는 것이다. 명백한 방법은 "never-seen" 심벌을 생성하여 이스케이프 시퀀스를 트리거하는 것이다. 그런데 한 번도 본 적이 없는 심벌에 어떤 확률을 할당해야 할까? 이를 영 빈도 문제라고 한다. 하나의 변형은 라플라스 추정기를 사용하여 "never-seen" 심벌에 고정된 의사 카운트 1을 할당한다. PPMd라는 변형은 "never-seen" 심벌이 사용될 때마다 의사 카운트를 증가시킨다. (다른 말로, PPMd는 새로운 심벌의 확률을 고유 심벌 수와 관찰된 총 심벌 수의 비율로 추정한다).
구현[편집]
PPM 압축 구현은 다른 세부 사항에서 크게 다르다. 실제 심벌 선택은 보통 산술 부호화을 사용하여 기록되지만, 허프만 부호화 또는 어떤 종류의 사전 부호화 기법을 사용하는 것도 가능하다. 대부분의 PPM 알고리즘에서 사용되는 기본 모델은 여러 심벌을 예측하도록 확장할 수도 있다. 마르코프 모델링을 대체하거나 보완하기 위해 비 마르코프 모델링을 사용하는 것도 가능하다. 심벌 크기는 보통 고정되어 있으며, 일반적으로 단일 바이트이므로 어떤 파일 형식이든 쉽게 처리할 수 있다.
연구 논문은 1980년대 중반까지 거슬러 올라간다. 소프트웨어 구현은 1990년대 초까지 인기가 없었는데, 이는 PPM 알고리즘이 상당한 양의 RAM을 필요로 하기 때문이다. 최근의 PPM 구현은 자연어 텍스트에 대한 무손실 압축 프로그램 중 가장 성능이 좋다.
PPMd는 디미트리 쉬카린이 작성한 PPMII(정보 상속을 가진 PPM)의 공개 도메인 구현으로, 여러 차례 호환되지 않는 수정을 거쳤다. 기본적으로 RAR 파일 형식에 사용된다.7z와 zip 파일 형식에서도 사용할 수 있다.
PPM 알고리즘을 개선하려는 시도는 PAQ 데이터 압축 알고리즘 시리즈로 이어졌다.
PPM 알고리즘은 압축을 위해 사용되는 것이 아니라, 사용자 입력의 효율성을 높이기 위해 대체 입력 방법 프로그램인 Dasher에서 사용된다.
참고 문헌[편집]
- 스크립트 오류: "Citation/CS1" 모듈이 없습니다.
- 스크립트 오류: "Citation/CS1" 모듈이 없습니다.
- 스크립트 오류: "Citation/CS1" 모듈이 없습니다.
- C. Bloom, Solving the problems of context modeling
- W.J. Teahan, Probability estimation for PPM, Original Source from archive.org
- 스크립트 오류: "Citation/CS1" 모듈이 없습니다.
