Sampled Pattern Matching (SPM) definition
5th May 2007
“… consider a universal predictor based on pattern matching: Given a sequence Xi,… ,Xn drawn from a stationary mixing source, it predicts the next symbol Xn+i based on selecting a context of Xn+i. The predictor, called the Sampled Pattern Matching (SPM), is a modification of the Ehrenfeucht-Mycielski pseudo random generator algorithm. It predicts the value of the most frequent symbol appearing at the so called sampled positions. These positions follow the occurrences of a fraction of the longest suffix of the original sequence that has another copy inside XiX2 … Xn. In other words, in SPM the context selection consists of taking certain fraction of the longest match. The study of the longest match for lossless data compression was initiated by [Aaron D.] Wyner and Ziv in their 1989 seminal paper.”
This was an excerpt from a paper titled “A Universal Predictor Based on Pattern Matching” by Philippe Jacquet, Wojciech Szpankowski and Izydor Apostol. This appears to be the best definition of SPM I found.
I found the text of this article available in PostScript format, and assume it’s OK to duplicate it here in PDF format: A Universal Predictor Based on Pattern Matching. Please contact me if there is a need to remove this link.