<story><title>Fast Search Using PostgreSQL Trigram Indexes</title><url>https://about.gitlab.com/2016/03/18/fast-search-using-postgresql-trigram-indexes/?</url></story><parent_chain><item><author>mbenjaminsmith</author><text>Trigrams are a very straightforward solution to this but they have one major limitation: They break with misspellings &amp;#x2F; alternative spellings. For example the words &amp;quot;vodka&amp;quot; and &amp;quot;votka&amp;quot; share no trigrams yet are obviously very similar.&lt;p&gt;I recently worked on this problem for a project and came up with a more robust solution using pre-computed Levenshtein indexes. You&amp;#x27;ve probably heard of Levenshtein distance as a measure of word similarity. It counts the number of single-character edits that are required to transform one string into another. For example &amp;quot;vodka&amp;quot; and &amp;quot;votka&amp;quot; have a Levenshtein distance of 1.&lt;p&gt;Using a related approach (single character edits) it&amp;#x27;s possible to build a so-called Levenshtein index.&lt;p&gt;The major issue with a vanilla Levenshtein index is that it&amp;#x27;s impractically large. There is a way to make a space &amp;#x2F; time trade-off however that makes it much smaller. The basic idea is that instead of generating all Levenshtein variations for a word you only use the set of variations created by deleting single characters for a word.&lt;p&gt;Since that doesn&amp;#x27;t match all possible variations we have to compensate somehow. For example with a full index &amp;quot;votka&amp;quot; would be in the set of variations for &amp;quot;vodka&amp;quot; which means if we had misspelled vodka when searching for it we&amp;#x27;d still get a match. With our deletions-only index, however, we&amp;#x27;d get &amp;quot;voka&amp;quot; as our closest match. To work around this, we generate the deletion-only variations of our search term as well. In this case our search term &amp;quot;vodka&amp;quot; would become &amp;quot;odka&amp;quot;, &amp;quot;vdka&amp;quot;, &amp;quot;voka&amp;quot;, etc. and each of those terms would be matched against the index. That means our query is slower overall as it contains a number of sub-queries but in practice it&amp;#x27;s more than fast enough.&lt;p&gt;I wrote a meandering blog post about it here: &lt;a href=&quot;http:&amp;#x2F;&amp;#x2F;lattejed.com&amp;#x2F;writing-an-embedded-full-text-search-engine&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;lattejed.com&amp;#x2F;writing-an-embedded-full-text-search-eng...&lt;/a&gt;&lt;p&gt;There are some additional ideas in there such as how to make a Levenshtein index handle prefix matches better (for e.g., incremental search) that may be helpful if you need to implement something like this.&lt;p&gt;If you do read that I&amp;#x27;d like to point out that I no longer recommend LevelDB. That doesn&amp;#x27;t change anything of importance in the post though.</text></item></parent_chain><comment><author>jmilum</author><text>vodka and votka do share trigrams: __v, _vo, and ka_, as the PG rules for generating them add two spaces at the beginning and one at the end.</text></comment>
<story><title>Fast Search Using PostgreSQL Trigram Indexes</title><url>https://about.gitlab.com/2016/03/18/fast-search-using-postgresql-trigram-indexes/?</url></story><parent_chain><item><author>mbenjaminsmith</author><text>Trigrams are a very straightforward solution to this but they have one major limitation: They break with misspellings &amp;#x2F; alternative spellings. For example the words &amp;quot;vodka&amp;quot; and &amp;quot;votka&amp;quot; share no trigrams yet are obviously very similar.&lt;p&gt;I recently worked on this problem for a project and came up with a more robust solution using pre-computed Levenshtein indexes. You&amp;#x27;ve probably heard of Levenshtein distance as a measure of word similarity. It counts the number of single-character edits that are required to transform one string into another. For example &amp;quot;vodka&amp;quot; and &amp;quot;votka&amp;quot; have a Levenshtein distance of 1.&lt;p&gt;Using a related approach (single character edits) it&amp;#x27;s possible to build a so-called Levenshtein index.&lt;p&gt;The major issue with a vanilla Levenshtein index is that it&amp;#x27;s impractically large. There is a way to make a space &amp;#x2F; time trade-off however that makes it much smaller. The basic idea is that instead of generating all Levenshtein variations for a word you only use the set of variations created by deleting single characters for a word.&lt;p&gt;Since that doesn&amp;#x27;t match all possible variations we have to compensate somehow. For example with a full index &amp;quot;votka&amp;quot; would be in the set of variations for &amp;quot;vodka&amp;quot; which means if we had misspelled vodka when searching for it we&amp;#x27;d still get a match. With our deletions-only index, however, we&amp;#x27;d get &amp;quot;voka&amp;quot; as our closest match. To work around this, we generate the deletion-only variations of our search term as well. In this case our search term &amp;quot;vodka&amp;quot; would become &amp;quot;odka&amp;quot;, &amp;quot;vdka&amp;quot;, &amp;quot;voka&amp;quot;, etc. and each of those terms would be matched against the index. That means our query is slower overall as it contains a number of sub-queries but in practice it&amp;#x27;s more than fast enough.&lt;p&gt;I wrote a meandering blog post about it here: &lt;a href=&quot;http:&amp;#x2F;&amp;#x2F;lattejed.com&amp;#x2F;writing-an-embedded-full-text-search-engine&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;lattejed.com&amp;#x2F;writing-an-embedded-full-text-search-eng...&lt;/a&gt;&lt;p&gt;There are some additional ideas in there such as how to make a Levenshtein index handle prefix matches better (for e.g., incremental search) that may be helpful if you need to implement something like this.&lt;p&gt;If you do read that I&amp;#x27;d like to point out that I no longer recommend LevelDB. That doesn&amp;#x27;t change anything of importance in the post though.</text></item></parent_chain><comment><author>oelmekki</author><text>Super interesting approach, thanks for contributing it.&lt;p&gt;From what I see in your article, you used this for searching through mails, so I guess it works on a pretty decent volume of data, but just to confirm it: do you think it&amp;#x27;s viable on something like gitlab&amp;#x27;s multi-resources full text search? For reference, what is the size of this index for your mailbox? (assuming it&amp;#x27;s an usual contractor dev mailbox, with mainly lots of notification mails and discussions with daily customers)&lt;p&gt;PS: don&amp;#x27;t worry about other reactions, users have invaded our dev world, nowadays, the sad thing with having attractive salaries</text></comment>