🏷️ fuzzy text search


Search IconIcon to open search


Last updated Aug 6, 2023


This is not finished page

# Types

# Skip-grams

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

# Q-grams

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

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:

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

# Other

# Motivation

Subsequences are important for offline algorithms: