Если кому интересно, (типа похвалюсь!) почему сжатие было быстрым, и почему на некоторых файлах в режиме best тормозилось. Без заумных слов, одни схемы:

Код:
Файл:      |   Таблица зацикленная,
           |   Указывает на предыдущее
           |   вхождение символа:

#8000   A<----+   #0000
#8001   B     |   #0000
#8002   C     |   #0000
#8003   D     |   #0000
...           |
              |
#8010   A<--+ +-- #8000
#8011   E   | 
#8012   C   | 
...         |
            |
#8030   A   +---- #8010
#8031   F
#8032   D
... 

#8070   A   <--- Мы тут.
#8071   B
#8072   C


Таблица последних вхождений символов:

A	#8030
B       #8001
...
--------------------------

Всё ОК, но есть фейл на таких вот данных:

#8000   A<------+ #0000
#8001   A<----+ +-#8000
#8002   A<--+ +---#8001
#8003   A<+ +-----#8002
....      +---+
              |
#8010   A<-   +---#8003
#8011   A<-     <-#8010
#8012   A<--+   <-#8011
....        |
            |
#8030   A   +---- #8012
#8031   A         #8030
#8032   A         #8031
....

#8070   A   <--- Мы тут. Впереди печаль.
#8071   A
#8072   A
В пакере в режимах fast и good эти таблицы заполнялись частично, чтобы скорость не падала. В 95 году это типа было крута. Сейчас все проще - в свободном доступе много инфы, в т.ч. на русском. Например, кандидатская Кадача. Там много всего написано, читать в общем, интересно.

В хрусте2 поиск идет не по одному символу, а по символу и нескольким битам следующего символа.

Позже выложу схему, алгоритм, который без потери коэффициента сжатия решает вопрос по скорости с такими "рыхлыми" файлами.