From: linux@horizon.com Date: Thu, 17 Aug 2006 22:33:03 GMT Subject: Re: Compression and dictionaries Message-ID: <20060817223303.1712.qmail@science.horizon.com> In-Reply-To: Just a note: there are index structures that support regular expression searching. In particular, a PAT tree, usually represented implicitly as a PAT array, can be walked by a finite automaton to find all the places it matches. However, there's a lot of code complexity associated with that. And a PAT array assumes efficient random access to the text being indexed, as it does not keep a copy of the text. Perhaps most importantly, this would be a big change to "git grep", as it would search every object in the database, not a particular commit. And mapping objects back to filenames in trees and commits requires another index. Compression dictionaries and indexes have some opposing points. In a compression dictionary, you prefer common words that appear in many places. For an index, you prefer rare words that identify a small set of files.