String matching algorithm
Trigram search is a method of searching for text when the exact syntax or spelling of the target object is not precisely known or when queries may be regular expressions. It finds objects which match the maximum number of three consecutive character strings (i.e. trigrams) in the entered search terms, which are generally near matches. Two strings with many shared trigrams can be expected to be very similar. Trigrams also allow for efficiently creating search engine indexes for searches that are regular expressions or match the text inexactly. Indexes can significantly accelerate searches. A threshold for number of trigram matches can be specified as a cutoff point, after a result is unmatched.
Using trigrams for accelerating searches is a technique used in some systems for code searching, in situations in which queries that are regular expressions may be useful, in search engines such as Elasticsearch, as well as in databases such as PostgreSQL.
Examples.
Consider the string "alice". The trigrams of the string would be "ali", "lic", and "ice", not including spaces. Searching for this string in a database with a trigram-based index would involve finding which objects contain as many of the three trigrams as possible.
As a concrete example of using trigram search to search for a regular expression query, consider searching for the string codice_1, where the brackets denote that the third character in the string being searched for could be codice_2 or codice_3. In this situation, one could query the index for objects that have the two trigrams codice_4 and codice_5 or the two trigrams codice_6 and codice_7. Thus, finding this query would involve no string matching, and could just query the index directly, which can be faster in practice.