Definitions

Variable length Markov models (VLMM) were designed to learn text, that is sequence of letters. We will keep the original terminology and map it to our problem. In the next sections, we will use the following definitions.

An alphabet $\Sigma$ is a set of predefined distinct entities. In the case of a sequence of letters, the entities would be letters. In the case of a sequence of a face, the entities would be the pathlet models. We will refer to these entities as being letters to stick to the original definitions given by Ron et al. [81]. $\vert\Sigma\vert$ denotes the size of the alphabet.

A string is a sequence of letters and is denoted by $s=s_1s_2s_3\ldots s_n$ where $n$ is the length of the sequence. $\vert s\vert$ denotes the number of letters in the string $s$. We denote by $e$ the empty string ($\vert e\vert=0$). $\Sigma^*$ is the set of all strings over $\Sigma$, $\Sigma^L$ is the set of all strings of length $L$ over $\Sigma$, and $\Sigma^{\leq L}$ is the set of all strings of length at most $L$ over $\Sigma$.

A prefix of a string $s$ of length $n$ is denoted by $\mathit{prefix}(s)=s_1s_2s_3\ldots s_{n-1}$. In the same manner, a suffix of a string $s$ of length $n$ is denoted by $\mathit{suffix}(s)=s_2s_3\ldots s_n$. The set of all suffixes of a string $s$ of length $n$ is $\mathit{suffix}^*(s)=\{s_i\ldots s_n\vert 1\leq i\leq n\}\cup{e}$.

A string $p$ is a suffix extension of $s$ if and only if $s$ is a suffix of $p$, that is $s\in \mathit{suffix}^*(p)$.