Editing Trigram search (section)

{{Short description|String matching algorithm}}
'''Trigram search''' is a method of [[Search algorithm|searching]] for text when the exact [[syntax]] or spelling of the target object is not precisely known<ref>{{Cite journal |last=Hardarson |first=Omar |date=1997 |title=Interactive coding of economic activity using trigram search in BLAISE III |url=http://www.blaiseusers.org/1997/papers/hardar97.pdf |journal=International Blaise User Group}} Note: This article discusses trigram search as a way of efficiently encoding certain kinds of economic data, and finds that this technique is particularly useful when the users of the system have little context for the structure of the data.</ref> or when queries may be [[Regular expression|regular expressions]].<ref name=":2" /> It finds objects which match the maximum number of three consecutive character [[character string|string]]s (i.e. [[Trigram|trigrams]]) in the entered search terms, which are generally near matches.<ref>{{Cite book |last1=Adams |first1=Elizabeth |last2=Meltzer |first2=Arnold |title=Proceedings of the 1993 ACM conference on Computer science - CSC '93 |chapter=Trigrams as index element in full text retrieval: Observations and experimental results |date=1 March 1993 |pages=433–439 |chapter-url=https://dl.acm.org/doi/10.1145/170791.170891 |doi=10.1145/170791.170891 |isbn=0897915585 |s2cid=16701550 }}</ref> Two strings with many shared trigrams can be expected to be very similar.<ref name=":0" /> Trigrams also allow for efficiently creating [[search engine index]]es for searches that are regular expressions or match the text inexactly. Indexes can significantly accelerate searches.<ref name=":1" /><ref>{{Cite journal |last1=Zobel |first1=Justin |last2=Moffat |first2=Alistair |last3=Sacks-Davis |first3=Ron |date=1993 |title=Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files |url=http://www.vldb.org/conf/1993/P290.PDF |journal=Conference on Very Large Databases (VLDB)}} Note: This research paper does not use the term "trigram search" but does seem to be the first instance in the literature of using n-grams as indices, and is cited in the Russ Cox article as the first instance of the structure of a reverse index based on trigrams. The paper also cited successful performance results from using this style of search.</ref> A threshold for number of trigram matches can be specified as a cutoff point, after a result is unmatched.<ref name=":0" />

Using trigrams for accelerating searches is a technique used in some systems for [[computer program|code]] searching, in situations in which queries that are regular expressions may be useful,<ref name=":1">{{Cite web |date=2016-03-18 |title=Fast Search Using PostgreSQL Trigram Text Indexes |url=https://about.gitlab.com/blog/2016/03/18/fast-search-using-postgresql-trigram-indexes/ |access-date=2022-05-28 |website=GitLab |language=en}}</ref><ref name=":2">{{Cite web |last=Cox |first=Russ |date=January 2012 |title=Regular Expression Matching with a Trigram Index or How Google Code Search Worked |url=https://swtch.com/~rsc/regexp/regexp4.html}}</ref><ref>{{Cite web |title=Big Grep |url=https://resources.sei.cmu.edu/library/asset-view.cfm?assetid=507972 |access-date=2022-06-12 |website=resources.sei.cmu.edu | date=11 August 2017 |language=en}} Also called BigGrep. Uses n-grams (not always 3),</ref> in search engines such as [[Elasticsearch]],<ref>{{Cite web |title=N-gram tokenizer {{!}} Elasticsearch Guide [8.2] {{!}} Elastic |url=https://www.elastic.co/guide/en/elasticsearch/reference/current/analysis-ngram-tokenizer.html |access-date=2022-05-28 |website=www.elastic.co |language=en-us}}</ref> as well as in databases such as [[PostgreSQL]].<ref name=":0">{{Cite web |date=2022-05-12 |title=F.33. pg_trgm |url=https://www.postgresql.org/docs/14/pgtrgm.html |access-date=2022-05-28 |website=PostgreSQL Documentation |language=en}}</ref>