is defined as follows: The are multiindices and is a string of length : subsequences can occur in a non-contiguous manner, but gaps are penalized. The multiindex gives the positions of the characters matching in . is the difference between the first and last entry in , that is: how far apart in the subsequence matching is. The parameter may be set to any value between (gaps are not allowed, as only is not but ) and (even widely-spread "occurrences" are weighted the same as appearances as a contiguous substring, as ). For several relevant algorithms, data enters into the algorithm only in expressions involving an inner product of feature vectors, hence the name kernel methods. A desirable consequence of this is that one does not need to explicitly calculate the transformation , only the inner product via the kernel, which may be a lot quicker, especially when approximated. References Algorithms on strings Kernel methods for machine learning Natural language processing String metrics