부분 일치를 통한 예측

Prediction by partial matching

부분 매칭에 의한 예측(PPM)은 컨텍스트 모델링 및 예측에 기초한 적응형 통계 데이터 압축 기술입니다.PPM 모델은 압축되지 않은 기호 스트림의 이전 기호 집합을 사용하여 스트림의 다음 기호를 예측합니다.PPM 알고리즘을 사용하여 군집 분석에서 데이터를 예측된 그룹으로 군집화할 수도 있습니다.

이론.

예측은 보통 기호[clarification needed] 순위로 축소됩니다.각 기호(문자, 비트 또는 기타 데이터량)는 압축되기 전에 순위가 매겨지며 순위 시스템은 대응하는 코드워드(및 압축률)를 결정한다.많은 압축 알고리즘에서 순위는 확률 질량 함수 추정과 동일합니다.이전 문자(또는 컨텍스트가 지정됨)를 지정하면 각 기호에는 확률이 할당됩니다.예를 들어 산술 부호화에서는 기호가 이전의 기호 뒤에 나타나도록 확률에 따라 순위가 매겨지고 전체 시퀀스가 이러한 확률에 따라 계산되는 단일 분수로 압축된다.

이전 기호 수 n은 PPM(n)으로 표시되는 PPM 모형의 순서를 결정합니다.콘텍스트에 길이 제한이 없는 무한 변형도 존재하며 PPM*으로 표시됩니다.모든 n개의 콘텍스트 기호를 기반으로 예측을 할 수 없는 경우 n - 1개의 기호를 사용하여 예측을 시도합니다.이 프로세스는 일치하는 기호가 발견되거나 더 이상 컨텍스트에 남아 있지 않을 때까지 반복됩니다.그 시점에서 고정 예측이 이루어집니다.

PPM 모델을 최적화하는 작업의 대부분은 입력 스트림에서 아직 발생하지 않은 입력을 처리하는 것입니다.이러한 문제를 해결하는 확실한 방법은 탈출[clarification needed] 시퀀스를 트리거하는 "보이지 않는" 기호를 만드는 것입니다.하지만 한 번도 본 적이 없는 기호에는 어떤 확률을 부여해야 할까요?이것은 제로 주파수 문제라고 불립니다.한 변종에서는 "never see" 기호를 1의 고정 의사 카운트를 할당하는 Laplace 추정기를 사용합니다.PPMd라고 하는 변형은 "보이지 않는" 기호를 사용할 때마다 "보이지 않는" 기호의 의사 카운트를 증가시킵니다.즉, PPMd는 관측된 총 기호 수에 대한 고유 기호 수의 비율로 새 기호의 확률을 추정합니다.

실행

PPM 압축의 실장은, 그 외의 세부 사항에서도 큰 차이가 있습니다.실제 기호 선택은 보통 산술 부호화를 사용하여 기록되지만, 허프만 부호화 또는 사전 부호화 기법도 사용할 수 있습니다.대부분의 PPM 알고리즘에 사용되는 기본 모델을 확장하여 여러 기호를 예측할 수도 있습니다.마르코프 모델링을 대체하거나 보완하기 위해 비 마르코프 모델링을 사용할 수도 있습니다.기호 크기는 일반적으로 정적이며 일반적으로 단일 바이트이므로 파일 형식을 쉽게 처리할 수 있습니다.

이 알고리즘군에 대한 발표된 연구는 1980년대 중반까지 거슬러 올라갈 수 있습니다.PPM 알고리즘에는 대량의 RAM이 필요하기 때문에 소프트웨어 실장은 1990년대 초반까지 인기가 없었습니다.최근 PPM 구현은 자연어 텍스트에 대한 최고의 성능의 무손실 압축 프로그램 중 하나입니다.

PPMd는 Dmitry Shkarin에 의한 PPMII의 구현이다.디폴트로는 RAR에서 사용됩니다.또한 7z 파일 형식의 몇 가지 가능한 압축 방법 중 하나로 7-Zip에서 사용됩니다.

PPM 알고리즘을 개선하려는 시도가 PAQ 일련의 데이터 압축 알고리즘으로 이어졌습니다.

PPM 알고리즘은 압축에 사용되는 것이 아니라 대체 입력 방법 프로그램 대셔에서 사용자 입력의 효율을 높이기 위해 사용된다.

「 」를 참조해 주세요.

원천

  • Cleary, J.; Witten, I. (April 1984). "Data Compression Using Adaptive Coding and Partial String Matching". IEEE Trans. Commun. 32 (4): 396–402. CiteSeerX 10.1.1.14.4305. doi:10.1109/TCOM.1984.1096090.
  • Moffat, A. (November 1990). "Implementing the PPM data compression scheme". IEEE Trans. Commun. 38 (11): 1917–1921. CiteSeerX 10.1.1.120.8728. doi:10.1109/26.61469.
  • Cleary, J. G.; Teahan, W. J.; Witten, I. H. "Unbounded length contexts for PPM". The Computer Journal. Oxford, England: Oxford University Press. 40 (2_and_3): Pages 67–75. doi:10.1093/comjnl/40.2_and_3.67. ISSN 0010-4620.
  • C. Bloom, 컨텍스트 모델링의 문제를 해결합니다.
  • W.J. 티한, PPM에 대한 확률 추정.
  • SchüRmann, T.; Grassberger, P. (September 1996). "Entropy estimation of symbol sequences". Chaos. 6 (3): 414–427. arXiv:cond-mat/0203436. Bibcode:1996Chaos...6..414S. doi:10.1063/1.166191. PMID 12780271.

레퍼런스

외부 링크