Autarchy of the Private Cave

Tiny bits of bioinformatics, [web-]programming etc

    • Archives

    • Recent comments

    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.


    Leave a Reply

    XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>