Хорошо, я замечаю, что вы вдаваетесь в некоторые подробности о проблеме, но не упоминаете информацию, представленную в разделе 4 RFC 1951 (спецификация для формата сжатых данных DEFLATE, т.е. используемый формат в ZIP), что наводит меня на мысль, что вы, возможно, пропустили этот ресурс.
Их основной подход - это хеш-таблица, использующая трехбайтовые последовательности в качестве ключей. Пока цепочка не пуста, все записи вдоль нее сканируются, чтобы а) устранить ложные столкновения, б) устранить слишком старые совпадения и в) выбрать самое длинное совпадение из оставшихся.
(Обратите внимание, что их рекомендация определяется фактором патентов; возможно, они знали о более эффективном методе, но не могли быть уверены, что на него не распространяется чей-то патент. Лично я всегда удивлялся, почему не удалось найти самые длинные совпадения, изучив совпадения для трехбайтовых последовательностей, которые начинаются со второго байта входящих данных, третьего байта и т. д., и отсеивания совпадений, которые не совпадают, т. е. если ваш входящий data - "ABCDEFG ...", и у вас есть совпадения хеш-значений для "ABC" со смещениями 100, 302 и 416, но ваше единственное совпадение хеш-значений для "BCD" - со смещением 301, вы знаете, что, если у вас нет двух полностью совпадающих совпадений совпадения хэшей - маловероятно - тогда 302 - ваш самый длинный матч.)
Также обратите внимание на их рекомендацию о необязательном «ленивом сопоставлении» (что по иронии судьбы делает больше работы): вместо того, чтобы автоматически брать самое длинное совпадение, которое начинается с первого байта входящих данных, компрессор проверяет еще более длинное совпадение, начиная с следующий байт. Если ваши входящие данные имеют значение «ABCDE ...» и ваши единственные совпадения в скользящем окне соответствуют «ABC» и «BCDE», лучше кодировать «A» в виде буквенного байта, а «BCDE» - в виде матч.