 |
|
From: "Vadim Yoockin" <vy@thermosyn.com>
Date: 3 Aug 2000 10:19:59 +0400
Subj: BWT-FAQ
Burrows Wheeler Transform
AKA Block-Sorting Lossless Data Compression Algorithm.
Frequently Asked Questions.
Vadim Yoockin (yoockinv@mtu-net.ru, vy@thermosyn.com, 2:5020/1042.50).
Редакция от 2.08.2000
Добавлено/изменено:
- более подробное сравнение BWT и PPM методов
- описание существующих BWT-компрессоров
- анонс моего вечно недоделанного ybs :)
- очень краткий обзор методов сортировки и сжатия
- 1-2 coding
В перспективе:
- расширенный список литературы для самого искушенного читателя
- <здесь могло бы быть ваше предложение :)>
Содержание.
1. BWT - что, собственно, это такое?
2. За счет мы можем добиться хорошего сжатия?
3. Возможно ли обратное преобразование?
4. Schindler Transform.
5. Чем компрессоры, использующие этот метод, лучше/хуже остальных?
6. Методы сортировки, используемые в BWT-компрессорах.
7. Методы сжатия, используемые в BWT и ST-компрессорах.
8. Какие существуют компрессоры/архиваторы на основе BWT и ST?
9. Какое отношение имеет к BWT автор данного FAQ'a?
10. Что такое 1-2 coding?
11. Литература.
12. Приложение. Статья Леонида Брухиса 1994 года.
1. BWT - что, собственно, это такое?
Это обратимый алгоритм перестановки символов во входном потоке,
позволяющий эффективно сжать полученный в результате преобразования блок
данных.
Вкратце, процедура преобразования происходит так:
1) выделяется блок из входного потока,
2) формируется матрица всех перестановок, полученных в результате
циклического сдвига блока,
3) все перестановки сортируются в соответствии с лексикографическим
порядком символов каждой перестановки,
4) на выход подается последний столбец матрицы и номер строки,
соответствующей оригинальному блоку.
2. За счет мы можем добиться хорошего сжатия?
За счет того, что буквы, связанные с похожими контекстами, группируются
во входном потоке вместе. Например, в английском языке часто встречается
последовательность 'the'. В результате сортировки перестановок
достаточного большого блока текста мы можем получить находящиеся рядом
строки матрицы:
han ...t
he ....t
he ....t
hen ...t
hen ...w
here...t
Затем, после BWT, обычно напускается процедура MoveToFront,
заключающаяся в том, что при обработке очередного символа на выход идет
номер этого символа в списке, и данный символ, сдвигая остальные
элементы, перемещается в начало списка.
Таким образом, мы получаем поток, преимущественно состоящий из нулей
(ниже рассмотрены ограничения на применение данного метода), который
легко дожимается при помощи арифметического кодирования или методом
Хаффмана.
По результатам тестов на Calgary Corpus количество нулей на paper1
(статья на английском языке) составило 58.4%, на progp (программа) -
74%, geo (двоичный файл) - 35.8%.
Можно заметить, что при указанной сортировке мы используем
последующие контексты для определения предшествующих им символов.
Если сортировать в другом, более привычном для сжатия порядке - не
слева направо, а справа налево, ухудшается сжатие текстовых файлов,
но улучшается сжатие бинарников и слегка возрастает скорость
расжатия в силу более удобного обратного преобразования.
3. Возможно ли обратное преобразование?
Если нам отсортировать символы последнего столбца матрицы
перестановок - а перед началом обратного преобразования нам известен
только он - то мы получим первый столбец данной матрицы, поскольку,
напомню, строки матрицы были отсортированы в лексикографическом
порядке.
Таким образом, мы имеем уже список пар, состоящих из символа
последнего столбца и следующего за ним символа первого столбца.
После сортировки этих пар мы обретаем знание о двух первых столбцах
матрицы. И т.д., пока мы не получим всю матрицу перестановок.
Зная номер исходной строки, мы воспроизводим входные данные.
Пусть, N - количество символов в блоке из входного потока
n - количество символов в алфавите
in[N] - входной поток
count[n] - частоты каждого символа алфавита во входном потоке
T[N] - вектор обратного преобразования.
На первом шаге считаем частоты символов.
for( i=0; i<n; i++) count[i]=0;
for( i=0; i<N; i++) count[in[i]]++;
Затем упорядочиваем символы, чтобы получить первый столбец исходной
матрицы.
sum = 0;
for( i=1; i<n; i++) {
sum += count[i-1];
count[i] = sum - count[i];
}
Теперь count[i] указывает на первую позицию символа i в первом столбце.
Следующий шаг - создание вектора обратного преобразования.
for( i=0; i<N; i++) T[count[in[i]]++]]=i;
И, наконец, восстановим исходный текст.
for( i=0; i<N; i++) {
putc( in[i], output );
i = T[i];
}
4. Schindler Transform.
Отличается от BWT тем, что сортировка строк матрицы производится не по
всем символам, а по первым N из них и по позиции данного контекста в
исходном потоке. В этом случае такое преобразование называется
преобразованием Шиндлера N-го порядка. Можно сказать, что BWT - это ST
порядка, равного величине блока.
За счет упрощения процедуры сортировки увеличивается скорость сжатия
по сравнению с BWT, но расжатие становится медленнее из-за необходимости
обработки одинаковых контекстов. Об этом будет написано подробнее в
одной из частей BWT FAQ.
5. Чем компрессоры, использующие этот метод, лучше/хуже остальных?
Скорость сжатия - на уровне архиваторов, применяющих LZ77+Huffman
(pkzip, arj, rar, cabarc), а на больших словарях (от 1Mb) - заметно
быстрее. У сжимателя на ST, szip, скорость сжатия для малых порядков
еще выше.
Скорость расжатия у сжимателей на BWT в 3-4 раза быстрее сжатия. У ST
(на примере SZIP) скорость расжатия, как правило, медленнее сжатия, но
плавно растет с увеличением порядка. В целом, классические
LZ77+Huffman расжимают, конечно, быстрее.
Степень сжатия сильно зависит от типа сжимаемых данных. Наиболее
эффективно использование BWT для текстов и любых потоков со
стабильнами контекстами. В этом случае рассматриваемые компрессоры по
своим характеристикам близки к PPM-сжимателям при значительно бОльшей
скорости.
На неоднородных данных известные BWT-сжиматели заметно уступают по
сжатию лучшим современным сжимателям на LZhuf и чуть не дотягивают до
результатов, показываемых PPM'ми. Впрочем, есть способы сильно
увеличить сжатие неоднородных файлов. Такие уловки пока не
используются в связке с BWT, возможно, из-за сравнительно молодого
возраста последнего. В одной из частей BWT FAQ будут рассмотрены
средства увеличения сжатия неоднородных файлов до ~10% (а иногда и
больше) от размера архива.
В силу участившихся дискуссий по сравнению конкурирующих методов
BWT и PPM в свете появления крайне быстрого на текстах PPMD
Дмитрия Шкарина, считаю необходимым рассмотреть противостояние
лучших представителей упомянутых методов отдельно. Замечу, что
нижеизложенное является моим мнением, хотя и претендует на
некоторую объективность :) Оговорюсь также, что рассматриваю
только те компрессоры, которые заявлены и как сильные, и как
быстрые. И, соответственно, выпускаю из рассмотрения
задумчивые PPM-компрессоры, могущие себе позволить тратить
большое время на выжимание из данных последних крох избыточности.
Итак,
1) PPM в лице PPMD достигает лучших силы и скорости сжатия текстов,
но медленнее при расжатии.
2) BWT лучше сжимает файлы, состоящие из длинных и стабильных
контекстов. Например, исходники. PPM'у, чтобы достичь таких
результатов, необходимо увеличить глубину контекстов, что
сказывается на скорости.
3) Данные методы по-разному реагируют на файлы с большим
количеством коротких контекстов. PPM заметно замедляется,
а BWT ухудшает свое сжатие.
4) PPM лучше сжимает неоднородные файлы благодаря своей
лучшей адаптивности. Но, справедливости ради замечу,
BWT еще не исследованы в этой области.
6. Методы сортировки, используемые в BWT-компрессорах.
Начиная с bzip2, а точнее, с какого-то из Уилеровских bred'ов, идет
линейка компрессоров, использующих предварительную
radix-сортировку по паре байт. Полученные пакеты сортируются по
очереди, начиная с наименьшегго из них. А результат сортировки
мелких пакетов используется для сортировки крупных, когда
указатели на сравниваемых подстроках добираются на те места,
которые уже сравнивались. Компрессоры, _грамотно_ реализующие
такой подзод очень устойчивы в вырожденным данным. К примеру, для
Ybs в худшем случае все равно должно бы получаться n*logn, но мне
такие случаи не попадались. Даже специально :) А на большинстве
файлов зависимость получается практически линейной.
Этот метод не всегда оказывается самым быстрым из-за заметных
накладных расходов на повышенную устойчивость. К примеру, на
большинстве текстов более быстры Imp и, особенно, DC. Но последние
хорошо задумываются на длинных контекстах.
В научных кругах сейчас идет борьба за достижение линейного роста
времени сжатия от размера блока и уже существует ряд публикаций по
этому поводу авторства Садакане, Куртца, Балкенхола, и Ларссона.
Но лично я скептически отношусь к таким ухищрениям из-за слишком
больших расходов на построения деревьев или сложных ковыряний с
суффиксами, поскольку на большинстве файлов эти методы проигрывают
в скорости.
7. Методы сжатия, используемые в BWT и ST-компрессорах.
Исторически сложилось так, что для этого на протяжение долгого
времени использовался джентельменский набор в виде MTF +
арифметический кодер (или Хаффман, или rangecoder). Время от
времени многие пытались сделать шаг в сторону для того, чтобы
избежать MTF, эмпирически правого только на данных после
BW-преобразования :)
Первая удачная попытка была сделана Шиндлером (не считая самого
ST-преобразования, конечно). В Szip'e используется 3 модели.
Первая, быстрая адаптивная модель обрабатывает наиболее часто
используемые символы с соответствующими вероятностями, вторая -
MTF-модель для менее частых, но все же актуальных символов, и
третья модель подбирает оставшиеся символы. Для кодирования
длинных последовательностей BWT-выхода используется RLE.
Но MTF используется по-прежнему и с неменьшим усердием. И последние
компрессоры, использующие его, достигают сжатия, не уступающего
Szip'у на большинстве файлов кроме, разве что, неоднородных. Но,
конечно, это не такой уж простой MTF.
Среди используемых хитростей упомяну к примеру замедленное
прохождение в MTF0. Поскольку мы можем предположить, что среди
последовательности одинаковых символов может запросто попасться
случайный (хотя бы из-за орфографической ошибки в тексте), было бы
логично установить своеобразный фильтр, чтобы не сломать эту
последовательность и не пытаться кодировать через RLE этот
случайный символ. Например, можем пропускать символ в MTF0 только
если он уже находится в MTF1.
Такое ухищрение позволяет достичь наибольшего эффекта по сравнению с
остальными трюками. Правда, на некоторых файлах он ухудшает
сжатие. Например, на тех, в которых есть два почти равноправных и
частых символа, привязанных к одинаковым контекстам. Вроде пробела
и табуляции в исходниках.
Со временем, ежели оно у меня появится, я постараюсь описать еще многие
друие MTF-трюки, благо что почти с десяток, пожалуй насчитать
можно. А пока - вот, наиболее значимый, для дальнейших раздумий
читателю ;)
Что касается модели MTF для сжатия, почти все, достигающие
более-менее приличных результатов, используют структурную модель
Фенвика с, возможно, небольшими модификациями. В авторском
описании предполагалось поделить все MTF-коды на 7 групп: 1, 2-3,
4-7, 8-15, 16-31, 32-63, 64-127, 128-255 с EOB. При кодировании
MTF-кода полагается сначала кодировать номер группы, а затем номер
символа в этой группе.
Такое деление позволяет довольно быстро адаптироваться к изменению
данных. Ведь выход BWT состоит из фрагментов, в которых
присутствует небольшое количество символов с постоянной
вероятностью (эти фрагменты соответствуют стабильным контекстам),
перемежающхся с кусками, в которых символы попадаются как Бог на
душу положит. Поэтому нам надо вовремя определить, находимся ли мы
в хорошим фрагменте или попали на межфрагментное бездорожье.
Сравнительно небольшое количество групп позволяет это сделать с
вполне приемлимой скоростью.
Надавно появился сравнительно новый метод трактовки данных после
преобразования Бэрроуза-Уилера. Мне он впервые повстречался
в одной из статей Азнавута и Магливераса под названием
IF (inversed frequencies). Независимо от них этот метод
реализовал в своем архиваторе Эдгар Биндер, назвав его
DC (distance coder). И это название мне представляется более
логичным, поскольку предполагает кодировать расстояния
между одинаковыми символами. Данный метод пока реализван,
если не считать Ybs, только в DC.
8. Какие существуют компрессоры/архиваторы на основе BWT и ST?
Компрессор и вресия Автор Адрес
imp 1.10 (метод 2) Conor McCarthy <imp@technelysium.com.au>
x1 0.95 (метод 7) Stig Valentini <x1develop@dk-online.dk>
szip 1.11 Michael Schindler <michael@compressconsult.com>
bwc 0.99 Willem Monsuwe <willem@stack.nl>
bzip 0.21 Julian Seward <jseward@acm.org>
bzip2 1.00 Julian Seward <jseward@acm.org>
bred, bred2, bred3 D.J.Wheeler
ba 1.00 Mikael Lundqvist <mikael@2.sbbs.se>
zzip 0.35b Damien Debin <damien.debin@via.ecp.fr>
dc 0.99.015b Edgar Binder <EdgarBinder@t-online.de>
eri 4.6fre Alexander Ratushnyak <ratush@srsc-gw.sscc.ru>
Причем количество таких программ непрерывно растет, видимо,
вскоре придется оставлять упоминание только про самые интересные :)
Ниже приведены краткие особенности некоторых этих и других программ:
Семейство bred'ов написаны одним из родоначальником BWT, когда узок
был круг людей, занимающихся этим методом. Многие идеи, использованные
в этих компрессорах, описаны в работах Фенвика. В x1 включена
реализация BWT, основанная на этих компрессорах.
Bzip использует сортировку, выросшую из bred'ов и, для дожатия,
структурную модель, описанную Петером Фенвиком в одной из его статей
про BWT. Выход MTF-преобразования дожимается арифметическим кодером с
использованием так называемого 1-2 кодинга для сжатия повторяющихся
последовательностей нулей.
Bzip2 использует усовершенствованную bred'скую сортировку, а выход
MTF-преобразования дожимается Хаффманом, также с 1-2 кодингом.
Bwc использует сортировку, похожую на ту, что применяется
в bzip2. Для дожатия использует структурную модель, 1-2 coding,
rangecoder (т.е. все то, что используется в bzip).
Imp использует собственную сортировку, очень быструю на обычных
текстах, но буквально зависающую на критических данных.
Дожиматель полностью позаимствован из bzip2.
Интересная реализация применена в DjVu library. Сортировку
там не смотрел (вроде не особо быстрая). Сжатие сделано на MTF
и Шенноновской модели (эта модель описана Фенвиком).
Жмет немного лучше bzip'a, но долго.
В szip, помимо упоминавшегося ST, реализована и возможность
использования BWT-преобразования. Реализована, прямо скажем,
только для примера, без затей. А вот дожиматель у szip'a
прекрасный. Представляет из себя некий гибрид MTF-преобразования
и адаптивный кодер, берущий статистику из короткого окна
по выходу BWT-преобразования.
BKS98 принадлежит сразу трем авторам (Balkenhol, Kurtz, Shtarkov) и
пока есть только у них ;) Использует суффиксную сортировку и
многоконтекстовую модель MTF по трем последним кодам. Сжатие
наибольшее по сравнению с приведенными выше компрессорами, но и
достаточно медленное.
Новые версии Zzip'a выпускаются очень часто и свойства
этого компрессора постепенно улучшаются. С ним я досконально
не разбирался, но, если я не ошибаюсь, он использует все ту же
структурную модель и суффиксную сортировку Садакане.
Ba использует сортировку из bzip2, соответственно с такими же
временными характеристиками. В качестве дожимателя используется MTF
с арифметическим кодером. Новшество, реализованное в ba - это выбор
структурной модели MTF в отдельном проходе. Заметно улучшено сжатие
неоднородных файлов. По сжатию ba опережает упомянутые выше
BWT-компрессоры,
DC - достаточно новый компрессор, в котором реализован целый ряд
новаторских идей. Во-первых, конечно, это модель сжатия, отличная
от MTF - distance coding. Во-вторых, новый метод сортировки
(информация о нем, может быть, будет опубликована позже), очень
быстрый на текстах, хотя и дающий слабину на сильно избыточных
данных. И, наконец, большой набор тектовых фильтров, позволяющий
добиться особенного успеха на английских текстах (описание этих
фильтров пока выходит за рамки этого документа). Хотя, замечу, и без
этого по сжатию DC опережает конкурентов. IMHO, сейчас лучший из
BWT-компрессоров.
БОльшую часть из них можно взять на
ftp://ftp.elf.stuba.sk/pub/pc/pack
ftp://ftp.cl.cam.ac.uk/users/djw3
http://www.compressconsult.com
http://www.technelysium.com.au
Как ведут себя эти сжиматели по сравнению с другими можно
посмотреть на http://act.by.net и на русскоязычном сайте
http://www.shomonopoly.com/arctest. Или найти периодически
помещаемый в RU.COMPRESS результат сравнений компрессоров,
с легкой руки Булата Зиганшина названный VYTEST.
9. Какое отношение имеет к BWT автор данного FAQ'a?
В редкие промежутки свободного времени я пытаюсь
делать свой компрессор, впитавший все вышеизложенное :)
К сожалению, идей больше, чем возможностей для их воплощения,
но компрессор есть и в промежутках между попытками
реализовать упомянутые идеи вполне рабоспособный :)
Отмечу его характеристики:
Основан на сортировке, аналогичной bzip2 (только раза в два быстрее
;)) В перспективе думаю сделать сортировку, дающую значительное
ускорение на коротких контекстах. Сейчас на текстах уступает
по скорости Imp'у и DC. На очень избыточных данных быстрее
всех известных мне BWT-реализаций. Скорость расжатия на данный
момент опять же самая быстрая.
Собственно жмущая часть сейчас в стадии переписывания.
В прошлом использовалась MTF со структурной моделью Фенвика
(именно эта версия фигурирует в CCT 5.6 августа 2000 года),
сейчас - distance coder. На текущий момент достигнута
степень сжатия мало отличающаяся от DC, за исключением того,
что Ybs пока не использует фильтры.
Прошу прощения, что описываю компрессор до его официального
выхода.
10. Что такое 1-2 coding?
В свете данной статьи, это способ кодирования количества
повторяющихся символов. В принципе, этот способ может применяться
для кодирования любого числа.
Как известно, после MTF-преобразования мы получаем
последовательность, в которой при удачном раскладе присутствует
большое количество нулей, соответствующих нулевому рангу MTF.
Ноль возникают тогда, когда после некоторого символа
идет такой же (см. п.1 данного FAQ).
Если кодировать каждый код MTF0, то во 1-х, это накладно по времени
и, во 2-х, может ухудшить сжатие из-за погрешностей арифметического
кодера. А для кодирования Хаффмана, недолюбливающего вероятности,
отличающиеся от кратных степени двойки, это вообще неудобно, когда
символ имеет вероятность, значительно превышающую 1/2 (а после BWT и
MTF для ряда файлов такое случается) или даже, например, застревает
посередине между 1/4 и 1/2.
Элегантный выход был найден в отведении под MTF0 не одного, а двух
символов (назовем их z1 и z2). Таким образом, у нас в MTF-алфавите
получилось не 256, а 257 символов (по желанию, можно добавить еще
один символ - конец блока). Эти z1 и z2 можно использовать
кодирования числа идущих подряд MTF0:
1 - z1 7 - z1z1z1
2 - z2 8 - z1z1z2
3 - z1z1 9 - z1z2z1
4 - z1z2 10 - z1z2z2
5 - z2z1 11 - z2z1z1
6 - z2z2 ...
11. Литература.
Для более подробного ознакомления рекомендуется статья Леонида Брухиса
от 96 года, регулярно публикуемая в RU.COMPRESS. Или обратиться к
первоисточнику.
Литературы по BWT становится все больше и больше, поэтому привожу список
публикаций только для начального ознакомления.
1. M. Burrows and D.J. Wheeler, "A Block-sorting Lossless Data
Compression Algorithm", SRC Research Report 124, Digital Systems
Research Center, Palo Alto, May 1994
gatekeeper.dec.com/pub/DEC/SRC/research-reports/SRC-124.ps.Z
2. P.M. Fenwick, "Block sorting text compression", Australasian
Computer Science Conference, ACSC'96, Melbourne, Australia, Feb
1996. ftp.cs.auckland.ac.nz/out/peter-f/ACSC96.ps
3. M.R. Nelson: Data Compression with the Burrows Wheeler Transform.
Dr. Dobbs Journal, Sept. 1996, pp 46-50.
http://web2.airmail.net/markn/articles/bwt/bwt.htm
12. Приложение. Статья Леонида Брухиса 1994(95?) года.
Данная статья была опубликована в коференции ru.compress.
--------------------------------------------------
Преобразование Бэрроуза-Уилера (Burrows-Wheeler Transform)
В этой статье вкратце описываются идеи, изложенные в
http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/src-rr-124.html
Для начала рассмотрим такое преобразование текста:
пусть у нас есть строка S длиной N. Запишем ее, непосредственно под
ней запишем ее же, циклически сдвинутую на 1 символ, еще ниже -
на 2 символа, и т.д. Всего N раз. Например, для S = карамба, N = 7.
КАРАМБА
АРАМБАК
РАМБАКА
X = АМБАКАР
МБАКАРА
БАКАРАМ
АКАРАМБ
Теперь отсортируем строчки:
АКАРАМБ
АМБАКАР
АРАМБАК
Y = БАКАРАМ
КАРАМБА
МБАКАРА
РАМБАКА
И запишем последнюю колонку букв L=БРКМААА и номер строки массива, в
которой оказалась оригинальная строка S - в данном случае это 5.
А теперь фокус! Этого достаточно, чтобы восстановить исходную строку!
Как это делается: запишем данную нам последовательность букв L
в колонку и припишем к ней ее же, но с отсортированными буквами
L F
1 Б А?
2 Р А?
3 К А?
4 М Б?
5 А К?
6 А М?
7 А Р?
Как нетрудно видеть, это в точности первая колонка матрицы Y. Но как
же продолжить заполнение - что делать с буквами Б, К, Р и М
очевидно, но какая из А какой соответствует? Оказывается, все очень
просто -первой из А в L соответствует первая А в F и т.д., потому
что строки в матрице Y были отсортированы начиная с первой буквы, а
после приписывания слева L стали отсортированы начиная со второй, но
строчки с одинаковыми первыми буквами с тем же успехом отсортированы
начиная с первой буквы, т.е. находятся в том же порядке, что и
строчки в матрице Y. Таким образом, получаем, что строка 1
получилась из 5, 2 - 6, 3 - 7, 4 - 1, 5 - 3, 6 - 4, 7 - 2. Тогда,
начиная с сообщенного нам числа 5, имеем: 5372641, и читаем буквы в
соответствующих позициях колонки F: КАРАМБА, ко всеобщему удивлению.
Но спрашивается, где тут компрессия? А вот где: предположим, что
размер нашей строки S весьма велик - десятки килобайт; тогда, если
содержимое строки, скажем, русский текст, то в ней наверняка много
раз встречается буквосочетание " что". Тогда в матрице Y будет много
строчек, начинающихся на "то" и кончающихся на "ч" подряд, например:
.....
то он говорил.... ....ч
то он сказал... ....ч
то он такой?.. ....К
то она увидела ....ч
то они приехали... ....ч
т.е. в строке L будет участок с большим количеством ч подряд, лишь
изредка перемежающихся другими буквами, и чем длиннее текст, тем
больше будет в каждом конкретном участке строки L доля
"доминирующей" на этом участке буквы, что позволяет обеспечить
хорошее сжатие с помощью простого адаптивного алгоритма. Хорошие
результаты дает применение RLE (run-length encoding) и/или MTF (move
to front) перед Хаффменом или арифметическим кодером.
MTF делается так - все 256 возможных символов находятся в списке, и
при кодировании каждого символа передается его номер в списке, а сам
символ перемещается в голову списка. При такой схеме все
последовательности из одинаковых символов превращаются в
последовательности нулей, а все последовательности, содержащие
только 2 разных символа - в последовательности нулей и единиц, и
т.п.
Leo
PS. Простая демонстрационная программа из RLE, BWT, MTF и адаптивного
арифметического кодера по степени сжатия покрывает PKZIP как бык овцу,
а результат 856233 байта на Калгари корпусе (3141622 байт) достигается
оптимизированной программой, описанной в оригинальной статье за время,
сравнимое с затрачиваемым GZIP-ом (всего на 20% медленее). Расход
памяти при этом, разумеется, побольше, чем у GZIP-а - мегабайта 4.
© faqs.org.ru