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

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

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

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

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

Размер стандартного 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