Subsequences

Last updated Aug 6, 2023

Warning

This is not finished page

Let’s call subsequence of length N and distance betwen items K - skip-gram(N, K). Example for string abcdef:

• skip-gram(1, 0): a, b, c, d, e, f
• skip-gram(2, 0): ab, bc, cd, de, ef
• skip-gram(3, 0): abc, bcd, cde, def
• skip-gram(2, 1): ac, bd, ce, df
• skip-gram(2, 2): ad, be, cf
• skip-gram(2, 3): ae, bf
• skip-gram(2, 4): af ???:
• skip-gram(0, 0): empty
• skip-gram(2, 5): empty
• skip-gram(7, 0): empty
• skip-gram(1, 5): a, f
• skip-gram(2, <=1) = skip-gram(2, 0) $\cup$ skip-gram(2, 1)

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 abcdef:

• delete-gram(1): bcdef, acdef, abdef, abcef, abcdf, abcde

Longest equal delete-grams of two strings are Longest Common Subsequences (LCS).

• prefixes: abcdef, abcde, abcd, abc, ab, a
• suffixes: abcdef, bcdef, cdef, def, ef, f
• 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:

• Delete-grams
  • FastSS (Fast Similarity Search)
  • SymSpell
• q-grams
  • pattern matching and substring lookup
• Suffixes
  • suffix trie
  • suffix array