Re: Compression and dictionaries

[Shawn Pearce <spearce@spearce.org>]

Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
> Hi,
> 
> On Wed, 16 Aug 2006, Jon Smirl wrote:
> 
> > On 8/16/06, John Rigby <jcrigby@gmail.com> wrote:
> > > Sorry if this is off topic, but could the dictionary be used to make
> > > git-grep alot faster?
> > 
> > It would be almost instant.
> 
> But only if you are not using a regular expression, but a single word.

Yes and no.  If the inverted index contains terms broken by some
known pattern (e.g. break on word-type boundaries) and the regex
in question has constant sections (it should, otherwise it might
as well just be '.') then you can reduce your search space to a
fraction of the overall data by looking at the inverted index to
select likely terms, select the related revisions containing those
possible terms, then run the regex only on those revisions.

Sure you would be possibly pulling out a number of false positives
but if the constant sequence(s) in the regex reduce your search
space to below 1/2 of the overall data that's probably a lot less
I/O and CPU required to complete the query, even if you have to
read the entire dictionary and apply each term in the dictionary
to the regex to look for those possible matches.

-- 
Shawn.