Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Архиваторы, использующие BWT и ST

Довольно быстро после опубликования статьи Бао появляться первые компрессоры. Это объясняется, вопервых метод оказался хорошим компромиссом между быс использующими словарное сжатие, и медленными писсимистическими компрессорами. Во-вторых, авторы соглашаются на некоммерческое использование.

С тех пор количество программ, использующих уза - Уилера, непрерывно растет.

Компрессор и версия

Даты

Автор

BRed*

06.1997

D.J. Wheeler

ftp://ftp.cl.can.

XI -m7 0.95

05.1997

Stig Valentini

mailto :x 1 develop^ http://www.saunalaiu..

BWC 0.99

01.1999

Willem

Monsuwe

mailto:willem@stack .n

ftp://ftp.stack.nl/pub/us'

220


Раздел 1. Методы сжатия без потерь

Компрессор

и версия

Даты

Автор

Адреса

IMP-2 1.12 Winlmpl.21

01.2000 09.2000

Conor McCarthy

mailto:imp@technelysium.com.au http://www.technelysium.com.au/ http://www.winimp.com

szip 1.12

03.2000

Michael Schindler

mailto:michael@compressconsult.com http://www.compressconsult.com/

bzip2 1.01 (bzip0.21)

06.2000

Julian Seward

mailto :jseward@acm .org http://sourceware.cygnus.com/bzip2

DC 0.99.298b

08.2000

Edgar Binder

mailto:EdgarBinder@t-online.de ftp://ftp.elf.stuba.sk/pub/pc/pack

YBS О.ОЗе

09.2000

Vadim Yoockin

mailto:yoockinv@mtu-net.ru

mailto:vy@thermosyn.com

http:// compression.graphicon.~/ybs

В А 1.01Ы5

10.2000

Mikael Lundqvist

mailto:mikael@2.sbbs.se http://hem.spray.se/mikael.lundqvist

Zzip 0.36c

06.2001

Damien Debin

mailto:damien.debin@via.ecp.fr http://www.zzip.Cs.com/

SBC 0.910b

11.2001

Sami Makinen

mailto:sjm@pp.inet.fi

http ://www.geocities.com/sbcarchi ver

ERI 5.0re

12.2001

Alexander Ratushnyak

mailto:artest@inbox.ru http://geocities.com/eri32

GCA 0.9k

12.2001

Shin-ichi Tsuruta

mailto :synsyr@pop21 .odn.ne.jp http://www 1 .odn.ne.jp/~synsyr/

7-Zip2.30bl2

01.2002

Igor Pavlov

Mailto: support@7-zip.org Http://www.7-zip.org

Семейство программ BRed, BRed и BRed3 написано одним из родона­чальников BWT - Дэвидом Уилером. Многие идеи, использованные в этих компрессорах, описаны в работах Петера Фенвика [18] и нашли свое приме­нение в ряде других программ, например в XI.

Bzip использует адаптированную к BWT сортировку Бентли - Седжвика, во многом позаимствованную из вышеупомянутого семейства. После BWT выполняется преобразование методом стопки книг, выходные данные кото­рого сжимаются при помощи интервального кодирования (аналог арифме­тического сжатия) с использованием 1-2-кодирования и структурной моде­ли Петера Фенвика.

Для того чтобы создать программу, которую можно свободно использо­вать в некоммерческих целях, в bzip2 интервальное кодирование было за­менено на сжатие по методу Хаффмана. Видимо, благодаря этому bzip2 на­ходит все большее распространение в различных областях применения и де-факто уже становится одним из стандартов. Сортировка в bzip2 изменена незначительно по сравнению с bzip. В основном повышена устойчивость к избыточным данным и оптимизирован ряд процедур.

В BWC используются такие же методы, что и bzip и bzip2. А именно оп­тимизированная сортировка, MTF, 1-2-кодирование и интервальное коди­рование.

IMP использует собственную сортировку, очень быструю на обычных текстах, но буквально "зависающую" на данных, в которых встречаются длинные одинаковые последовательности символов. Сжатие полностью по­заимствовано из bzip2.

Алгоритм сжатия, используемый в bzip2, также включен и в архива­тор 7-Zip.

В szip, помимо упоминавшегося частичного сортирующего преобразова­ния, реализована и возможность использования BWT. Реализована, прямо скажем, только для примера, без затей. А вот для сжатия используются очень интересные решения, представляющие собой некий гибрид MTF-преобразования и адаптивного кодера, берущий статистику из короткого окна преобразованных с помощью BWT данных. С участием автора szip и с использованием описанных решений был также создан архиватор ICT UC.

В Zzip применяются все те же испытанные временем структурная мо­дель, сортировка Бентли - Седжвика и кодирование диапазонов.

ВА использует аналогичную сортировку. Но повышение устойчивости реализовано в ВА другим способом. Деление строк по ключу прекращается в том случае, когда оказывается, что этим строкам предшествуют одинако­вые символы. Еще одно новшество, реализованное в ВА, - это выбор струк­турной модели MTF в отдельном проходе. Также за счет динамического оп­ределения размера блока улучшено сжатие неоднородных файлов. Для уси­ления сжатия английских текстов используется переупорядочение алфавита.

В DC впервые реализован целый ряд новаторских идей. Во-первых, ко­нечно, это модель сжатия, отличная от MTF, - кодирование расстояний. Во-вторых, новый метод сортировки, очень быстрый на текстах, хотя и дающий слабину на сильно избыточных данных. И наконец, большой набор методов препроцессинга текстовых данных, позволяющий добиться особенного ус­пеха на английских текстах.

Отличительная особенность SBC - наличие мощной криптосистемы. Ни в одном из архиваторов, пожалуй, не реализовано столько алгоритмов шиф­рования, как в SBC. В SBC используется алгоритм BWT, ориентированный на большие блоки избыточных данных и позволяющий очень быстро сорти­ровать данные с большим количеством длинных похожих строк. Вместо MTF в архиваторе используется кодирование расстояний, хотя пока не так эффективно, как в YBS и DC, но это компенсируется большим количеством фильтров (методов препроцессинга), настроенных на определенные типы данных.

ARC (автор - Ian Sutton, которому также принадлежит РРМ-архиватор BOA). Как и многие другие, использует BWT на основе сортировки Бент-ли - Седжвика и MTF. Как и в SBC, дополнительно отслеживаются очень длинные повторы данных.

Первые версии YBS также использовали перемещение стопки книг, ко­торое затем было заменено на кодирование расстояний. Что дало заметный выигрыш в степени сжатия.

Среди не распространяемых свободно компрессоров, описание которых опубликовано в научных трудах, можно отметить BKS98 и BKS99, которые принадлежат сразу трем авторам [10]. Эти компрессоры используют суф-фиксную сортировку и многоконтекстовую модель MTF по трем последним кодам.

Сравнение BWT-архиваторов

Параметры, используемые для указания режима работы архиваторов, выбраны таким образом, чтобы добиться наилучших результатов в сжатии без особого ухудшения скорости.

Тестирование производилось на компьютере со следующей конфигура­цией:


Intel Pentium III 840 МГц

140 МГц

256 Мб SDRAM

Quantum FB 4.3 Гб

Windows NT 4.0 Service Pack 3

Процессор Частота шины Оперативная память Жесткий диск Операционная система

Начнем со сжатия русских текстов, потому что BWT-архиваторы осо­бенно эффективны именно для сжатия текстов. А русские тексты выбраны для того, чтобы показать эффективность сжатия в чистом виде, без исполь­зования текстовых фильтров, которые для русских текстов еще не созданы авторами описываемых программ. Файл имеет длину 1,639,139 байт.

Архиватор, версия и параметры

Размер сжатого файла, байт

Время сжатия, с

Время разжатия, с

YBS О.ОЗе

446,151

1.81

0.93

DC 0.99.298b -a

449,403

1.21

1.00

SBC 0.860

451,240

1.69

0.87

ARC (I.Sutton) b20

459,409

2.08

1.37

Compressia' Ь2048

462,873

2.92

2.66

ВА1.01Ь5-24-т

463,214

2.17

1.26

Zzip 0.36 -тх -Ь8

467,383

1.96

1.65

szip 1.12 Ь21 оО

470,894

3.34

0.78

ICTUC1.0

472,556

2.54

1.27

szip 1.12b21 о8

472,577

2.32

1.12

GCA 0.90g -v

477,999

2.17

1.17

BWC/PGCC 0.99 т2т

479,162

1.69

0.83

BWC/PGCC 0.99 т900к

503,556

1.56

0.83

szip 1.12b2l о4

506,348

0.48

0.94

IMP1.10-2ul000

506,524

1.07

0.64

bzip2/PGCC1.0b7-9

507,828

1.55

0.66

Как можно заметить, первенство удерживают компрессоры, использую­щие кодирование расстояний.

На английском тексте (2 042 760 байт) некоторые архиваторы использу­ют фильтры, тем самым заметно улучшая сжатие. Ниже приведены резуль­таты, принадлежащие тем программам, которые показали наилучшие ре­зультаты в первом тесте.

Архиватор, версия и параметры

Размер сжатого файла, байт

Время сжатия, с

Время разжатия, с

Использова­ние фильтров

DC 0.99.298b

476,215

1.58

1.28

+

SBC 0.860 b3ml

489,612

1.59

0.96

+

YBS 0.03e

496,703

2.32

1.09

DC 0.99.298b -a

500,421

1.50

1.18

ARC (I.Sutton) b20

508,737

2.62

1.71

BA1.01b5-24

512,696

2.87

1.53

+

Zzip 0.36 -mx -b8

515,672

2.84

2.08

+

Compressia b2048

517,484

3.67

2.12

BA1.01b5-24-x

517,626

2.75

1.42

При сжатии данных, представляющих собой исходные тексты программ, распределение среди лидеров тестов практически не меняется.

Для иллюстрации поведения BWT-архиваторов на неоднородных дан­ных применен исполнимый модуль из дистрибутива компилятора Watcom 10.0 wcc386.exe (536,624 байта). Для того чтобы можно было судить об эф­фективности различных методов и режимов, некоторые строки помечены специальными знаками:

Архиватор, вер­сия и параметры

Размер

сжатого

файла,

байт

Время сжа­тия, с

Время разжа­тия, с

3

е-

л

Ц S

е

Умень­шенный размер блока

Автомати­ческое опре­деление размера блока

YBS О.ОЗе -m5I2k

275,396

0.66

0.51

+

+

YBS О.ОЗе

276,035

0.66

0.57

+

SBC 0.860 m3a

278,061

0.98

0.69

+

+

ARC b5mml

278,392

1.33

0.48

+

+

DC 0.99.298b -Ь512

279,424

0.67

0.36

+

+

DC 0.99.298b

279,759

0.66

0.37

+

ARC mml

280,052

1.34

0.46

+

Zzip 0.36 -mx

291,199

0.74

0.66

ARC (I.Sutton) b5

291,345

0.58

0.48

+

ARC (I.Sutton)

292,979

0.58

0.48

BA1.01b5-24-z

293,489

0.82

0.64

+

DC 0.99.298b -a

293,807

0.52

0.39

IMP 1.10-2 ulOOO

294,679

0.38

0.18

+

Compressiab512

297,647

0.97

1.16

ICTUC1.0

298,348

0.75

0.53

BA 1.01b5

298,617

0.82

0.66

szip 1.12b21o0

298,668

0.76

0.31

szip 1.12 b21 o4

299,249

0.27

0.39

BWC/PGCC 0.99 тбООк

304,996

0.58

0.37

bzip2/PGCC 1.0b7 -6

308,624

0.63

0.26

В качестве файла, содержащего смесь текстовых и бинарных данных, использовался Fileware.doc размером 427,520 байт из поставки русского MS Office'95. Данный пример показывает, что иногда модель, использующая MTF, оказывается достаточно эффективной.

Архиватор, версия и параметры

Размер

сжатого

файла,

байт

Вре­мя сжа­тия, с

Вре-мя раз-жа-тия, с

3 О.

t-

Ц

S

е

Умень­шен­ный размер блока

Автомати­ческое оп­ределение размера блока

SBC 0.860 тЗа

126,811

0.69

0.42

+

+

DC 0.99.298b

127,377

0.38

0.18

+

ARCb2

128,685

0.38

0.23

+

+

YBS0.03e-m256k

130,356

0.37

0.24

+

Compressia Ь256

131,737

0.61

0.40

+

BA1.01b5-24-r

132,651

0.41

0.30

Zzip 0.36 -al

132,711

0.65

0.40

DC 0.99.298b -a

133,825

0.34

0.23

YBS О.ОЗе

133,915

0.37

0.25

BWC/PGCC 0.99 тбООк

134,183

0.33

0.19

+

bzip2/ PGCC1.0b7-6

134,932

0.44

0.14

+

szip 1.12 b21 oO

134,945

0.90

0.15

IMP 1.10-2 ulOOO

135,431

0.30

0.12

ICTUC1.0

136,842

0.41

0.29

BA1.01b5-24-z

137,566

0.49

0.31

+

szip 1.12 b21 o4

141,784

0.17

0.18

Заключение

Несмотря на то что преобразование Барроуза - Уилера было опублико­вано сравнительно недавно, оно пользуется большим вниманием со стороны разработчиков архиваторов. И пожалуй, еще впереди новые исследования, которые позволят повысить эффективность сжатия на основе BWT еще в большей степени.

Можно отметить характерные особенности архиваторов, использующих описанное преобразование, по сравнению с другими.

Скорость сжатия - на уровне архиваторов, применяющих словарные ме­тоды, например LZ77. Разжатие, как правило, в 3-4 раза быстрее сжатия. Степень сжатия сильно зависит от типа данных.

Наиболее эффективно применение BWT-архиваторов для текстов и лю­бых данных со стабильными контекстами. В этом случае рассматриваемые компрессоры по своим характеристикам близки к программам, использую­щим РРМ. На неоднородных данных существующие архиваторы на основе BWT немного уступают лучшим современным компрессорам, использующим словарные методы или РРМ. Впрочем, существуют способы компен­сировать этот недостаток.

Расходы памяти в режиме максимального сжатия довольно близки у всех современных архиваторов. Наибольшее отличие наблюдается при декоди­ровании. Наиболее скромными в этом отношении являются архиваторы, ис­пользующие алгоритмы семейства LZ77, а наиболее расточительными -РРМ-компрессоры, требующие столько же ресурсов, сколько им нужно при сжатии. Архиваторы на основе BWT занимают промежуточное положение.