[HN Gopher] Regular Expression Matching with a Trigram Index (2012)
       ___________________________________________________________________
        
       Regular Expression Matching with a Trigram Index (2012)
        
       Author : colinprince
       Score  : 102 points
       Date   : 2023-02-07 13:23 UTC (9 hours ago)
        
 (HTM) web link (swtch.com)
 (TXT) w3m dump (swtch.com)
        
       | talolard wrote:
       | Postgres implements this[0] as well, and it's really wonderful.
       | It doesn't give a human the search experience they are used to,
       | but for the superhuman who can write regex , this becomes a very
       | cheap way to search data at scale.
       | 
       | [0]https://www.postgresql.org/docs/current/pgtrgm.html
        
         | jkingsman wrote:
         | I use trigram indices on a project I run[0] where I want to do
         | cheap filtering of DB results and the performance is just
         | outstanding; I didn't think free text search could be so fast!
         | 
         | CREATE EXTENSION IF NOT EXISTS pg_trgm;
         | 
         | CREATE INDEX IF NOT EXISTS lowercase_title ON streams
         | (lower(title));
         | 
         | CREATE INDEX IF NOT EXISTS title_trgm ON streams USING gin
         | (lower(title) gin_trgm_ops);
         | 
         | And boom, super performant search via `LIKE %{}%`.
         | 
         | I also love taking advantage of `TABLESAMPLE system_rows()`
         | which lets me do hyperfast random selection without needing to
         | randomly sort the entire table. PG has so many hidden gems.
         | 
         | [0] https://nobody.live
        
         | eyelidlessness wrote:
         | > but for the superhuman who can write regex
         | 
         | Usually when I write regex someone describes me as a monster. I
         | guess both could be accurate!
        
       | cjbprime wrote:
       | Hound is an excellent implementation of this for code search:
       | 
       | https://github.com/hound-search/hound
        
       | secure wrote:
       | Debian Code Search is based on this work! :)
       | 
       | https://codesearch.debian.net/
       | 
       | (If you want a lot more details, check out my thesis on it:
       | https://codesearch.debian.net/research/bsc-thesis.pdf)
        
         | donio wrote:
         | plocate is another nice simple use case of a trigram index.
         | It's a faster version of the classic locate/slocate/mlocate
         | tools.
         | 
         | https://plocate.sesse.net/
        
       | [deleted]
        
         | [deleted]
        
       | heipei wrote:
       | Trigram indexing is also used by the Elasticsearch "wildcard"
       | field type for fast arbitrary regex/infix matching:
       | https://www.elastic.co/blog/find-strings-within-strings-fast...
        
       | zelphirkalt wrote:
       | I have seen the term "trigram" twice today on HN. I am familiar
       | with the term only for something like on the South Korean flag
       | [1]. Interesting to see this being used for a special case of
       | n-grams in language processing.
       | 
       | [1]: https://en.wikipedia.org/wiki/Bagua
        
         | tgv wrote:
         | It's not really special. It used to be quite common, as well as
         | bigrams (n=2). In the Roman alphabet, 3 characters give a fair
         | trade-off between precision and recall, making them suitable to
         | things like spelling error correction.
         | 
         | Everything old will be new again.
        
         | Rimintil wrote:
         | If you want a challenge, try solving the Eye Messages puzzle
         | from Noita, which is a bunch of trigrams!
         | 
         | https://noita.wiki.gg/wiki/Eye_Messages
        
         | dekhn wrote:
         | Much of google search ranking is based on (well, was ten years
         | ago) on bigram and trigram statistics. Short of a real n-gram
         | model this is remarkably effective but has some obvious failure
         | modes.
        
       | abdullah2993 wrote:
       | Github code search blog probably resurfaced this one.
        
       | asicsp wrote:
       | (2012)
       | 
       | Past discussions: https://hn.algolia.com/?q=regexp4.html
        
       ___________________________________________________________________
       (page generated 2023-02-07 23:01 UTC)