I just peeked at the gzip source (actually, the algorithm.doc file in the root of the source). It looks like they limit back-pointers to point to the previous 3

I just peeked at the gzip source (actually, the algorithm.doc file in the root of the source). It looks like they limit back-pointers to point to the previous 32k bytes, immidietly reducing this to a naive O(n). From my brief reading, it looks like they use a hash table to speed up lookups. Each 3 byte string is entered into the hashtable, with a pointer to the relevent location in the original text. Each has index has a linked list of entries. To find what backpointer to use for a given string, gzip finds the relevent linked list from the hash table, and scans it looking for the longest match. More recent entries in the list are preferred (as smaller distances make the pointers smaller because of the encoding). Additionally, the linked lists are arbitrarily truncated to a certain length (determined by the '-1' through '-9' run-time argument). gzip also has a 'lazy evaluation mecanism'. This is where, after it matches a string, it checks the next byte anyway (even if this byte is contained in the previous match). If a longer match is found, gzip discards the previous pointer and uses the new match. This is disabled in the fast speed modes. If they are doing anything particularly clever, it is in the implementation details. The algorithm itself seems relatively straightforward.