This is not finished page
Let’s call subsequence of length N and distance betwen items K -
skip-gram(N, K). Example for string
skip-gram(0, 0): empty
skip-gram(2, 5): empty
skip-gram(7, 0): empty
skip-gram(2, <=1) = skip-gram(2, 0)$\cup$
Skip-gram with distance zero is a q-gram:
q-gram(Q) = skip-gram(Q, 0).
Note: In some literatue set of equal length subsequences called q-grams and set of varied langth called n-grams. For example n-grams anchored to the start fo string is all prefixes of the string.
Delete-grams are subsequences of string generated by allowing up to M deletiotions:
delete-gram(M) = skip-gram(>=L - M, <=M) (
L is a length of string). Example for string
Longest equal delete-grams of two strings are Longest Common Subsequences (LCS).
- blocks - non-overlapping substrings. To be fair no sure what is the point, I met it only in papper mentioning it.
Subsequences are important for offline algorithms: