4 ms·
I’m a bit confused as to how https://swtch.com/~rsc/regexp/regexp4.html https://swtch.com/~rsc/regexp/regexp4.html isn’t mentioned at all.
by frutiger 3y ago
I’m a bit confused as to how https://swtch.com/~rsc/regexp/regexp4.html https://swtch.com/~rsc/regexp/regexp4.html isn’t mentioned at all.
- beyang 3y agoZoekt was heavily inspired by Google's internal code search, as mentioned in the blog post. The original version of the internal code search is described in the rsc post. Zoekt keeps some of the foundational ideas (e.g., trigram index), but was a from-scratch implementation. We probably should link to the rsc post for completeness, will update.
- hanwenn 3y agoAt the time that I started Zoekt (2016), Google's internal codesearch used suffix arrays for the string matching, which the team wasn't happy with, presumably because of the algorithmic complexity and indexing slowness. The Codesearch team was exploring alternatives, one of them the technique described in https://link.springer.com/article/10.1007/s11390-016-1618-6 https://link.springer.com/article/10.1007/s11390-016-1618-6. The positional trigrams were a simplification of this, that they didn't mind me open sourcing. so, in terms of algorithms, Zoekt wasn't actually inspired by Google's internal code search. The precise query syntax of zoekt is mostly copied from google's internal syntax, though.
- IshKebab 3y agoIt is mentioned.
- frutiger 3y agoIt is now, but wasn’t earlier.
- hanwenn 3y agoRuss Cox' trigram approach uses document IDs for the posting list, which makes the index much smaller, but gives less precise (ie. slower) matching. This is mentioned in the design doc at https://github.com/sourcegraph/zoekt/blob/main/doc/design.md#positional-trigrams https://github.com/sourcegraph/zoekt/blob/main/doc/design.md....