чисто ради интереса сделал эксперимент: уменьшил словарь до 64 кб, но впилил энтропийный кодек и пол-дюжины битовых моделей 9+ порядка. тарбол пожало за три секунды, гзип обошло на 100 кб.

публиковать не буду, потому что грязный эксперимент, код больше, и лень под mainline адаптировать. кому интересно — в личке попросите, но адаптировать сами будете. ;-)

краткое описание: битовый range coder (для алфавита из одного бита, внутренней разрядностью 32), 17-битовый предиктор (там механика чуть сложнее, ну да неважно), модель 256*256 предикторов для байта. по две байтовых модели на счётчик литералов, смещения и длины. памяти жрёт дополнительно несколько мегов, но энтропийный кодек того стоит. плюс в такой конфигурации это буквально десять строк кода для предиктора, и по десятку для encode и decode. делений не использует, только одно умножение (правда, LONGINT'а), и сдвиги.

недостаток в том, что декомпрессор тоже жрёт эти мегабайты, потому что ему, натурально, те же самые модели нужны. и медленней, само собой.

глубокого смысла эксперимент не имеет, но удержаться было сложно.