{"thread":{"id":"5282","subject":"Re: Compression and dictionaries","startedAt":"2006-08-15T08:33:03Z","lastAt":"2006-08-17T22:33:03Z","messageCount":10,"participants":["linux@horizon.com","Jon Smirl","Johannes Schindelin","Shawn Pearce"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"25344","messageId":"20060815083303.13253.qmail@science.horizon.com","threadId":"5282","inReplyTo":null,"subject":"Re: Compression and dictionaries","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-08-15T08:33:03Z","receivedAt":"2006-08-15T08:33:03Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"Just to inform this discussion, a brief description of the zlib\n\"deflate\" algorithm. A full description is in RFC1951.\n\nThis is LZ77 compression, meaning that what is actually encoded is\na series of instruction to either\n- Insert a specified byte, or\n- Copy a run of n bytes, starting m bytes ago.\n\nI.e. roughly\n\nunion {\n\tstruct { bool is_literal, char literal};\n\tstruct { bool is_literal; uint8_t length; uint16_t distance; } copy;\n};\n\nNote that 100 repetitions of a character can be unambiguously encoded\nas the character, followed by \"copy 99 chars starting at offset -1\".\n\nThere are also 257 possible literals, the 256 bytes plus a special EOF token.\n\nThe valid copy lengths are 3..258, and the valid distances are 1..32768.\n\nAnyway, the deflate algorithm operates in a couple of steps:\n\n- Translate the input into an (uncompressed) series of literals and\n copies.\n- Take the literals and the lengths and put them into one big Huffman tree.\n- Take the distances (actually, the simplified distances; large\n distances are grouped into ranges, which are followed by a binary suffix)\n and put them in a separate Huffman tree.\n- A Huffman tree can be transmitted by encoding the number of bits assigned\n to each symbol, with a apecial value (infinity is mathematically\n the most logical but deflate calls it zero) for a symbol that does\n not appear in the tree at all.\n- The way that deflate sends the lengths involves run-length encoding\n and a third Huffman tree, but I won't go into it now.\n\nThe finding of the copies is the most expensive part. The minimum\ncopy length is 3 bytes, so the 3 bytes starting at each position are\nhashed and the result put in a hash table, then you search the hash\nchain looking for the longest match. There are various heuristics\nfor aborting the search early, which the compression level adjusts.\n-1 doesn't look very hard at all, while -9 always does exhaustive search.\n\n(For example, when searching at all aggressively, when you've found a\nmatch, you search starting at the next byte position in the input as well.\nIf that produces a longer match, you emit the skipped byte as a literal\nand take the longer match and start looking for an improvement on it.)\n\n\nAnyway, input is divided into blocks. Each block is has a 2-bit\nprefix that encodes one of three possibilities:\n- Send uncompressed\n- Send compressed, with fixed (specified in the standard) literal/length &\n distance Huffman code. This \"static Huffman tree\" case is useful for\n short blocks where the overhead of encoding the Huffman tree is\n significant.\n- Send compressed, using dynamic (encoded in the file) Huffman codes.\n This is the most commonly used case for large, compressible files.\n\nNote that \"copy\" intructions can span blocks; the block boundaries are\nonly opportunities to change the way that the copy instructions are\ncoded if the file changes character (like text vs. data parts of an\nexecutable). Deciding when to end one block and start a new one is\nanother set of heuristics.\n\n\nOnly thing like a \"dictionary\" is the codes used for Huffman\ncompression.\n\nNow, what you *could* do is pre-load the \"copy from this text\" buffer\n(hash table) with up to 32K of example data, before you start encoding\ndata for real. Basically, run some example text through the compresser\nto warm it up, but throw away the compressed form.\n\nThis isn't a \"dictionary\" in the LZ78 sense (to start with, there are\nno boundaries between entries), but serves the same purpose. Note that\nsince the distance to copy from is limited to 32768, there's no point\nto having more warm-up text than that.\n"},{"id":"25356","messageId":"9e4733910608150629t1826717cqc4bde9f1ab5cc725@mail.gmail.com","threadId":"5282","inReplyTo":"20060815083303.13253.qmail@science.horizon.com","subject":"Re: Compression and dictionaries","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-15T13:29:28Z","receivedAt":"2006-08-15T13:29:28Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 15 Aug 2006 04:33:03 -0400, linux@horizon.com wrote:\n> Just to inform this discussion, a brief description of the zlib\n> \"deflate\" algorithm. A full description is in RFC1951.\n>\n> This is LZ77 compression, meaning that what is actually encoded is\n> a series of instruction to either\n> - Insert a specified byte, or\n> - Copy a run of n bytes, starting m bytes ago.\n\nShawn and I did some testing overnight. A simple 4KB preload table\nyielded a 4% size reduction in my 850MB pack. I'm still hoping for 10%\nusing an optimal 32K table.\n\nPaper on computing the optimal preload table:\nhttp://www.eecs.harvard.edu/~michaelm/postscripts/dcc2001a.pdf\n\nIf anyone is interested in doing some research, it would be\ninteresting to build a pack engine based on full-text search\ntechnology. For example cLucene,\nhttp://clucene.sourceforge.net/index.php/Main_Page The full-text\nsearch app contains the code for extracting the dictionary and then\nencoding all of the blobs using it.\n\nMy prediction is that a large global dictionary based scheme will\ncompress significantly better than zlib is capable of.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25358","messageId":"9e4733910608150755q54757386n13c705b0043e8308@mail.gmail.com","threadId":"5282","inReplyTo":"20060815083303.13253.qmail@science.horizon.com","subject":"Re: Compression and dictionaries","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-15T14:55:02Z","receivedAt":"2006-08-15T14:55:02Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"I explained our situation to Mark Adler, zlib author, and he recommend\nchecking out this book for techniques that can be used.\n\nhttp://www.cs.mu.oz.au/mg/\n\n-----\nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25396","messageId":"20060816003712.32000.qmail@science.horizon.com","threadId":"5282","inReplyTo":"9e4733910608150755q54757386n13c705b0043e8308@mail.gmail.com","subject":"Re: Compression and dictionaries","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-08-16T00:37:12Z","receivedAt":"2006-08-16T00:37:12Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"> I explained our situation to Mark Adler, zlib author, and he recommend\n> checking out this book for techniques that can be used.\n> \n> http://www.cs.mu.oz.au/mg/\n\nI was about to suggest the same thing! It's an excellent book.\n\nIt's about a piece of software and the choices made there, but it\nexplains in detail many alternatives and why they weren't chosen for\nthe mg software, but what they might be useful for.\n\nThe mg software itself is designed for human-language text, and does\nindexing as well. So it does a fixed breakdown into alternate word and\nnon-word tokens, builds a lexicon with frequency tables, then uses the\nfrequencies to build Huffman trees, and Huffman-compresses each token.\nThe \"word\" dictionary is also used as part of the search index, as each\nword has a (very cleverly compressed to less than one byte on average)\npointer to each document it appears in with a count of the number of\nappearances.\n\nThe word encoding is straight zero-order Huffman, so inter-word\ncorrelations are not used.\n\nFor software, with lots of punctuation and multi-word idioms\n(\"for (i = 0; i < n; i++) {\"), the basic design is not very well suited.\n(To say nothing of binary data, like some people who want to\ncheck images or multi-megabyte video files into git.)\n\nBut there is a good description of many possible algorithms, with\nlots of emphasis on practicalities.\n\nAnd the software *does* support dynamic collections, via auxiliary indexes\nand escape codes for any new words not found in the main dictionary.\nIn fact, generating the Huffman tree from as little as 1/8 of the material\nto be compressed only loses you 5.7% of the compression. (Table 9011,\np. 360.)\n\nHowever, that is for English text, with a pretty Zipf-like distribution.\nIn code, we generate new words (new function names) frequently, and\nproceed to use them heavily.\n\nIt's worth noting the similarity between generating a good base dictionary\nwith finding a good base version of a file for delta-encoding.\nYou may end up having to divide the documents into classes (different\nsource languages for example - C vs. asm vs. perl vs. python vs.\ndocs vs. GIFs), and use a different dictionary per class. But that\ndrives up the cost of compression (you have to see which class the\nfile to be compressed falls into).\n\nAnyway, highly recommended.\n"},{"id":"25398","messageId":"9e4733910608152250h1bcb8bf5qebb29ef84b971abd@mail.gmail.com","threadId":"5282","inReplyTo":"4b73d43f0608152243i15b37036x7aa50aa3afc2b02f@mail.gmail.com","subject":"Re: Compression and dictionaries","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-16T05:50:24Z","receivedAt":"2006-08-16T05:50:24Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/16/06, John Rigby wrote:\n> Sorry if this is off topic, but could the dictionary be used to make\n> git-grep alot faster?\n\nIt would be almost instant.\n\nInverted full-text indices are what Google uses to grep 20B web pages in 1 sec.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25399","messageId":"Pine.LNX.4.63.0608160832320.28360@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5282","inReplyTo":"9e4733910608152250h1bcb8bf5qebb29ef84b971abd@mail.gmail.com","subject":"Re: Compression and dictionaries","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-16T06:33:02Z","receivedAt":"2006-08-16T06:33:02Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 16 Aug 2006, Jon Smirl wrote:\n\n> On 8/16/06, John Rigby wrote:\n> > Sorry if this is off topic, but could the dictionary be used to make\n> > git-grep alot faster?\n> \n> It would be almost instant.\n\nBut only if you are not using a regular expression, but a single word.\n\nCiao,\nDscho\n"},{"id":"25404","messageId":"20060816065515.GB18778@spearce.org","threadId":"5282","inReplyTo":"Pine.LNX.4.63.0608160832320.28360@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: Compression and dictionaries","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-16T06:55:15Z","receivedAt":"2006-08-16T06:55:15Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Johannes Schindelin wrote:\n> Hi,\n> \n> On Wed, 16 Aug 2006, Jon Smirl wrote:\n> \n> > On 8/16/06, John Rigby wrote:\n> > > Sorry if this is off topic, but could the dictionary be used to make\n> > > git-grep alot faster?\n> > \n> > It would be almost instant.\n> \n> But only if you are not using a regular expression, but a single word.\n\nYes and no. If the inverted index contains terms broken by some\nknown pattern (e.g. break on word-type boundaries) and the regex\nin question has constant sections (it should, otherwise it might\nas well just be '.') then you can reduce your search space to a\nfraction of the overall data by looking at the inverted index to\nselect likely terms, select the related revisions containing those\npossible terms, then run the regex only on those revisions.\n\nSure you would be possibly pulling out a number of false positives\nbut if the constant sequence(s) in the regex reduce your search\nspace to below 1/2 of the overall data that's probably a lot less\nI/O and CPU required to complete the query, even if you have to\nread the entire dictionary and apply each term in the dictionary\nto the regex to look for those possible matches.\n\n-- \nShawn.\n"},{"id":"25405","messageId":"Pine.LNX.4.63.0608160908070.28360@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5282","inReplyTo":"20060816065515.GB18778@spearce.org","subject":"Re: Compression and dictionaries","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-16T07:09:00Z","receivedAt":"2006-08-16T07:09:00Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 16 Aug 2006, Shawn Pearce wrote:\n\n> Johannes Schindelin wrote:\n> > Hi,\n> > \n> > On Wed, 16 Aug 2006, Jon Smirl wrote:\n> > \n> > > On 8/16/06, John Rigby wrote:\n> > > > Sorry if this is off topic, but could the dictionary be used to make\n> > > > git-grep alot faster?\n> > > \n> > > It would be almost instant.\n> > \n> > But only if you are not using a regular expression, but a single word.\n> \n> Yes and no. If the inverted index contains terms broken by some\n> known pattern (e.g. break on word-type boundaries) and the regex\n> in question has constant sections (it should, otherwise it might\n> as well just be '.') then you can reduce your search space to a\n> fraction of the overall data by looking at the inverted index to\n> select likely terms, select the related revisions containing those\n> possible terms, then run the regex only on those revisions.\n> \n> Sure you would be possibly pulling out a number of false positives\n> but if the constant sequence(s) in the regex reduce your search\n> space to below 1/2 of the overall data that's probably a lot less\n> I/O and CPU required to complete the query, even if you have to\n> read the entire dictionary and apply each term in the dictionary\n> to the regex to look for those possible matches.\n\nSo it would speed up the search, but no, in case of regular expressions, \nparticularly any interesting one, the result would not be instantaneous.\n\nCiao,\nDscho\n"},{"id":"25416","messageId":"9e4733910608160743k22362dc4r4fa22c791707c73c@mail.gmail.com","threadId":"5282","inReplyTo":"Pine.LNX.4.63.0608160908070.28360@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: Compression and dictionaries","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-16T14:43:30Z","receivedAt":"2006-08-16T14:43:30Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/16/06, Johannes Schindelin wrote:\n> Hi,\n>\n> On Wed, 16 Aug 2006, Shawn Pearce wrote:\n>\n> > Johannes Schindelin wrote:\n> > > Hi,\n> > >\n> > > On Wed, 16 Aug 2006, Jon Smirl wrote:\n> > >\n> > > > On 8/16/06, John Rigby wrote:\n> > > > > Sorry if this is off topic, but could the dictionary be used to make\n> > > > > git-grep alot faster?\n> > > >\n> > > > It would be almost instant.\n> > >\n> > > But only if you are not using a regular expression, but a single word.\n> >\n> > Yes and no. If the inverted index contains terms broken by some\n> > known pattern (e.g. break on word-type boundaries) and the regex\n> > in question has constant sections (it should, otherwise it might\n> > as well just be '.') then you can reduce your search space to a\n> > fraction of the overall data by looking at the inverted index to\n> > select likely terms, select the related revisions containing those\n> > possible terms, then run the regex only on those revisions.\n> >\n> > Sure you would be possibly pulling out a number of false positives\n> > but if the constant sequence(s) in the regex reduce your search\n> > space to below 1/2 of the overall data that's probably a lot less\n> > I/O and CPU required to complete the query, even if you have to\n> > read the entire dictionary and apply each term in the dictionary\n> > to the regex to look for those possible matches.\n>\n> So it would speed up the search, but no, in case of regular expressions,\n> particularly any interesting one, the result would not be instantaneous.\n\nInstant is a relative term. Google is instant compared to running grep\nover 10TB of data. How long would that take, a month?\n\nShawn is correct, the inverted indexes are used to eliminate as many\nfiles as possible. So the response time is a more of a function of how\nmany hits you have instead of how big the data set is. Of course if\nyou give it a pattern that matches everything it will just as slow as\ngrep. Give it a pattern that is only in one file and detectable by the\nindex and it will be very fast. If you are going to give it a bunch of\npatterns that aren't in the index, then we need to adjust how the\nindex is built.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"25511","messageId":"20060817223303.1712.qmail@science.horizon.com","threadId":"5282","inReplyTo":"Pine.LNX.4.63.0608160832320.28360@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: Compression and dictionaries","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-08-17T22:33:03Z","receivedAt":"2006-08-17T22:33:03Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"Just a note: there are index structures that support regular expression\nsearching. In particular, a PAT tree, usually represented implicitly as\na PAT array, can be walked by a finite automaton to find all the places\nit matches.\n\nHowever, there's a lot of code complexity associated with that. And a\nPAT array assumes efficient random access to the text being indexed,\nas it does not keep a copy of the text.\n\n\nPerhaps most importantly, this would be a big change to \"git grep\", as\nit would search every object in the database, not a particular commit.\nAnd mapping objects back to filenames in trees and commits requires\nanother index.\n\n\nCompression dictionaries and indexes have some opposing points. In a\ncompression dictionary, you prefer common words that appear in many places.\nFor an index, you prefer rare words that identify a small set of files.\n"}]}