Опрос

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

Новички

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

Сравнение алгоритмов по степени сжатия

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

В 1989 г. группа исследователей предложила оценивать коэффициент сжатия с помощью набора файлов, получившего название Calgary Compres­sion Corpus2 (CalgCC). Набор состоит из 14 файлов, большая часть которых представляет собой тексты на английском языке или языках программиро­вания. Позже к этим 14 файлам были добавлены еще 4 текста на английском :зыке. Тем не менее обычно оценка производится на наборе из 14 файлов назовем такой набор стандартным CalgCC), а не из 18 (назовем его полным JalgCC).

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

В таблице приведено описание файлов, составляющих стандартный CalgCC.

айл

Размер, байт

Описание

Bib

111261

Библиографический список в формате UNIX "refer", ASCII

Bookl

768771

Художественная книга: T.Hardy. "Far from the madding crowd", неформатированный текст ASCII. Содержит большое количество OCR-опечаток (не­правильно распознанных символов)

Book2

610856

Техническая книга: Witten. "Principles of computer speech", формат UNIX "troff \ ASCII

Geo

102400

Геофизические данные, 32-битовые числа

News

377109

Набор сообщений электронных конференций Usenet, формат ASCII

Obji

21504

Объектный файл для ЭВМ типа VAX

Obj2

246814

Объектный файл для ПК Apple Macintosh

Paperl

53161

Техническая статья: Witten, Neal, Geary. "Arithmetic coding for data compression", формат UNIX "troff', ASCII

Paper2

82199

Техническая статья: Witten. "Computer (insecurity", формат UNIX "troff', ASCII

Pic

513216

Факсимильная двухцветная картинка, 1728x2376 то­чек, представляет собой две страницы технической книги на французском языке, отсканированные с раз­решением 200 точек на дюйм

Progc

39611

Программа на языке Си, ASCII

Progl

71646

Программа на языке Лисп, ASCII

Progp

49379

Программа на языке Паскаль,

Trans

93695

Расшифровка терминальной сес pa "EMACS", ASCII

Размер стандартного CalgCC составляет 3,141,622 ба-занимает 3,251,493 байт.

Единственная кодировка текстовой информации в Caig~ поэтому все символы - 8-битовые. Нет ни одного файла с символами или символами в другой кодировке.

Очевидно, что набор серьезно устарел. Типы входящих отнюдь не являются типами файлов, обычно подвергаемы-временным пользователем ПК. Поэтому с учетом данного иш режения о настройке некоторых алгоритмов под CalgCC к г сравнения на этом наборе нужно относиться осторожно..

Среди конкурентов CalgCC отметим:

■ Canterbury Compression Corpus (CantCC), состоящий из двух -стандартного набора "Standard Set" (11 файлов общей длиной 2 байт) и набора больших файлов "Large Set" (4 файла, 16,005,61у предложен той же группой исследователей, что и CalgCC, в кач альтернативы морально устаревшему CalgCC;

■ наборы файлов из Archive Comparison Test (ACT): 3 текстовых фи.

3 исполнимых, 2 звуковых и 8 полноцветных 24-битовых изображе!... а также вышеописанные CalgCC полный, CantCC стандартный, и по­следний (седьмой) набор - это демо-версия игры Worms2 (159 файло* общим размером 17 Мб);

■ файлы из Compressors Comparison Test Вадима Юкина (VYCCT, 8 фай­лов разных типов);

■ наборы файлов из тестов Art Of Lossless Data Compression (ARTest):

♦ 627 полноцветных изображений, 2066 Мб в 12 наборах;

♦ 1231 текстовый файл общей длиной 500 Мб в 6 наборах, в том числе CantCC "Large Set" и 663 русских текста;

♦ 5960 разнородных файлов, 382 Мб в 10 наборах.

Среди стандартных наборов тестовых изображений наиболее известнь четыре: JPEG Set, PNG Set, Waterloo Images и Kodak True Color Images.

Все тестовые файлы хранятся на WWW и FTP-серверах Интернета, точные ссылки на них - в описаниях тестов:

ACT: http://compression.ca

ARTest: http://go.to/artest, http://artst.narod.ru

CalgCC: http://links.uwaterloo.ca/calgary.corpus.html

CantCC: http://corpus.canterbury.ac.nz

хостинг игровых серверов

VYCCT: http://compression.graphicon.ru./ybs