6 ms·

Regular Expression Matching with a Trigram Index (2012)

122 points by colinprince 4y ago

abdullah2993 4y ago
Github code search blog probably resurfaced this one.
zelphirkalt 4y ago
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 https://en.wikipedia.org/wiki/Bagua
- tgv 4y ago
  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.
  - akomtu 4y ago
    Afaik, GPT works with trigrams, and calls them tokens.
  - msm_ 4y ago
    They also give you a good performance. I'm a maintainer of a specialised open-source 3gram database, and there's a lot of performance tricks you can do with 3grams. There are around 2*24 different 3grams (less if you only care about printable characters). This is small enough to pack into a single array on a modern computer. For example the file format I use has a header that reserves 8 bytes of data [1] for every possible 3gram - that's just 128MB of overhead per index, not a lot of disk storage. For 4grams, that's 32GB, much less acceptable even now. And 2grams are just not very useful for large datasets. [1] for the curious - the header is basically uint64_t file_offsets_to_3gram_data[2**24].
- dekhn 4y ago
  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.
- Rimintil 4y ago
  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 https://noita.wiki.gg/wiki/Eye_Messages
asicsp 4y ago
(2012) Past discussions: https://hn.algolia.com/?q=regexp4.html https://hn.algolia.com/?q=regexp4.html
secure 4y ago
Debian Code Search is based on this work! :) https://codesearch.debian.net/ 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 https://codesearch.debian.net/research/bsc-thesis.pdf)
- donio 4y ago
  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/ https://plocate.sesse.net/
- JoeyBananas 4y ago
  searching for dirty words is very fun
talolard 4y ago
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 https://www.postgresql.org/docs/current/pgtrgm.html
- eyelidlessness 4y ago
  > 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!
- jkingsman 4y ago
  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 https://nobody.live
cjbprime 4y ago
Hound is an excellent implementation of this for code search: https://github.com/hound-search/hound https://github.com/hound-search/hound
heipei 4y ago
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-faster-with-the-new-elasticsearch-wildcard-field https://www.elastic.co/blog/find-strings-within-strings-fast...
deleted 4y ago
[deleted]
- deleted 4y ago
  [deleted]

122 points by colinprince 4y ago

Github code search blog probably resurfaced this one.

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 https://en.wikipedia.org/wiki/Bagua

tgv 4y ago
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.
- akomtu 4y ago
  Afaik, GPT works with trigrams, and calls them tokens.
- msm_ 4y ago
  They also give you a good performance. I'm a maintainer of a specialised open-source 3gram database, and there's a lot of performance tricks you can do with 3grams. There are around 2*24 different 3grams (less if you only care about printable characters). This is small enough to pack into a single array on a modern computer. For example the file format I use has a header that reserves 8 bytes of data [1] for every possible 3gram - that's just 128MB of overhead per index, not a lot of disk storage. For 4grams, that's 32GB, much less acceptable even now. And 2grams are just not very useful for large datasets. [1] for the curious - the header is basically uint64_t file_offsets_to_3gram_data[2**24].
dekhn 4y ago
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.
Rimintil 4y ago
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 https://noita.wiki.gg/wiki/Eye_Messages

asicsp 4y ago

(2012) Past discussions: https://hn.algolia.com/?q=regexp4.html https://hn.algolia.com/?q=regexp4.html

secure 4y ago

Debian Code Search is based on this work! :) https://codesearch.debian.net/ 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 https://codesearch.debian.net/research/bsc-thesis.pdf)

donio 4y ago
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/ https://plocate.sesse.net/
JoeyBananas 4y ago
searching for dirty words is very fun

talolard 4y ago

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 https://www.postgresql.org/docs/current/pgtrgm.html

eyelidlessness 4y ago
> 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!
jkingsman 4y ago
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 https://nobody.live

cjbprime 4y ago

Hound is an excellent implementation of this for code search: https://github.com/hound-search/hound https://github.com/hound-search/hound

heipei 4y ago

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-faster-with-the-new-elasticsearch-wildcard-field https://www.elastic.co/blog/find-strings-within-strings-fast...

deleted 4y ago

[deleted]

deleted 4y ago
[deleted]