4 ms·
Are there any good writeups on how to implement the trigram index side of this? For instance, the code alludes to the idea that you could store each trigram as
by btown 8y ago
Are there any good writeups on how to implement the trigram index side of this? For instance, the code alludes to the idea that you could store each trigram as a bitmap over documents, then the Boolean combinations become bitwise operations. I suppose you could keep the bitmaps in compressed (or even probabilistic sketch) form, then decompress only those required for a query, but is this the right intuition? Are there lower-level libraries or databases that do this kind of thing well, rather than rolling your own on a KV store or using something monstrous like ElasticSearch?
- shabble 8y agohttps://wiki.postgresql.org/images/6/6c/Index_support_for_regular_expression_search.pdf https://wiki.postgresql.org/images/6/6c/Index_support_for_re... is I think the slides for a conference talk on implementing within Postgres
- JaggedNZ 8y agoPostgres FTS with trigrams (pg_trigram extension) works really well for many search applications. Most of the effort would be tuning the FTS dictionary.
- dreamer_soul 8y agoMy issue with it is that a small term such as one word doesn't event match to a record which is weird, I'm using it with rails. Thinking of using elastic search to help with that
- deleted 8y ago[deleted]
- user5994461 8y agoThe project was released by the original author here. https://github.com/google/codesearch https://github.com/google/codesearch There is no information on the subject besides the 3 blog posts and the proof of concept.
- hn_throwaway_99 8y agoNote that Elasticsearch is built on top of Lucene (lucene.apache.org), which is a straight forward search indexer that creates a reverse index and document store, and gives pluggable low-level access to parts of the indexer path. Would be very easy to create a custom analyzer to create a trigram-based index (my guess is one already exists).
- straws 8y agoThere's https://github.com/google/zoekt https://github.com/google/zoekt which provides a pretty straight-forward and memory-efficient implementation. Their design document goes a bit into what makes it fast: https://github.com/google/zoekt/blob/master/doc/design.md https://github.com/google/zoekt/blob/master/doc/design.md