Русская Википедия:Calgary Corpus
Calgary corpus - набор текстовых и двоичных файлов, часто использовавшийся в качестве стандартного теста алгоритмов сжатия данных и сравнения их эффективности. Набор был собран в Университете Калгари в 1987 году и широко применялся в 1990-х. В 1997 был предложен новый тестовый набор Canterbury corpus[1], в котором были учтены некоторые замечания к репрезентативности корпуса Калгари[2].
Состав корпуса
В наиболее часто используемой форме корпус Калгари состоит из 14 файлов общим объёмом 3141622 байт:
| Размер (байт) | Имя файла | Описание |
|---|---|---|
| 111,261 | BIB | Текст ASCII в формате утилиты UNIX "refer" с 725 библиографическими записями. |
| 768,771 | BOOK1 | Неформатированный текст ASCII новеллы Томаса Харди Far from the Madding Crowd. |
| 610,856 | BOOK2 | Текст ASCII в формате "troff" – Ian H. Witten: Principles of Computer Speech. |
| 102,400 | GEO | Сейсмические данные в виде 32 битных чисел с плавающей запятой в формате IBM. |
| 377,109 | NEWS | Текст ASCII – набор сообщений из групп USENET. |
| 21,504 | OBJ1 | Исполняемый файл для VAX, полученный компиляцией PROGP. |
| 246,814 | OBJ2 | Исполняемый файл для Macintosh, программа "Knowledge Support System". |
| 53,161 | PAPER1 | Статья в формате "troff" – Witten, Neal, Cleary: Arithmetic Coding for Data Compression. |
| 82,199 | PAPER2 | Статья в формате "troff" – Witten: Computer (in)security. |
| 513,216 | PIC | Изображение размером 1728 x 2376: текст на французском и линейные диаграммы. |
| 39,611 | PROGC | Исходный код на языке C – программа UNIX compress v4.0. |
| 71,646 | PROGL | Исходный код на языке Lisp – системное приложение. |
| 49,379 | PROGP | Исходный код на языке Pascal – программа для оценки сжатия PPM. |
| 93,695 | TRANS | Текст ASCII и управляющие последовательности - запись терминальной сессии. |
Реже используется набор из 18 файлов, в который дополнительно включены 4 текстовых файла в формате "troff" - PAPER3-PAPER6.
Тестирование
Корпус Calgary часто использовался для сравнения эффективности сжатия в 1990-е годы. Результаты часто указывались в виде коэффициента бит на байт (среднее количество бит в сжатом файле, требуемое для кодирования 1 байта исходного файла) для каждого файла из набора, затем они усреднялись. Затем чаще стали указывать суммарный размер всех сжатых файлов.
Некоторые архиваторы допускали более эффективное сжатие при одновременной обработке всего корпуса (например, при их помещении в несжатый контейнер тира tar), за счет использования взаимной информации. Другие архиваторы, наоборот, хуже сжимали такой вариант из-за медленной реакции компрессора на изменение характеристик данных. Одновременное сжатие всего корпуса использовалось Matt Mahoney в его книге Data Compression Explained[3].
В таблице указаны размеры сжатого корпуса для нескольких популярных архиваторов.
| Архиватор | Опции | Сжатие 14 отдельных файлов | Объединенный tar архив |
|---|---|---|---|
| Без сжатия | 3,141,622 | 3,152,896 | |
| compress | 1,272,772 | 1,319,521 | |
| Info-ZIP 2.32 | -9 | 1,020,781 | 1,023,042 |
| gzip 1.3.5 | -9 | 1,017,624 | 1,022,810 |
| bzip2 1.0.3 | -9 | 828,347 | 860,097 |
| 7-zip 9.12b | 848,687 | 824,573 | |
| ppmd Jr1 | -m256 -o16 | 740,737 | 754,243 |
| ppmonstr J | 675,485 | 669,497 |
Конкурсы сжатия
21 мая 1996 года Leonid A. Broukhis начал конкурс "Calgary corpus Compression and SHA-1 crack Challenge"[4], в котором проводилось соревнование по сжатию корпуса Calgary с небольшими денежными призами. После 2010-го приз составляет 1 доллар США за каждое дополнительное уменьшение сжатого файла на 111 байт.
По условиям конкурса, сжиматься должны не только входные файлы корпуса, но и программа для их распаковки. Для этого сначала сжимаются файлы корпуса, затем полученные файлы и распаковщик сжимаются одним из широко распространенных архиваторов. Ограничения на время сжатия и количество используемой памяти постепенно изменяются, и после 2010 допустимо работа в течение 24 часов на компьютере с производительностью в 2000 MIPS (ОС Windows или Linux) и использование до 800 МБ ОЗУ. Позже было добавлено соревнование с SHA-1: распаковщик может создать не оригинальный файл из корпуса, а какой-то другой, но имеющий ту же криптографическую хеш-сумму по алгоритму SHA-1 (таким образом, требуется совершить атаку нахождения коллизии для заданного файла).
Первым приз получил Malcolm Taylor, автор архиваторов RK и WinRK, сжав набор до 759881 байт (сентябрь 1997). Последним приз получил 2 июля 2010 года Alexander Ratushnyak, сжав набор до 572465 байт и используя распаковщик на C++, сжимаемый до 7700 байт при помощи "PPMd var. I". Полный список рекордов в рамках конкурса:
| Размер (байт) | Месяц и год | Автор |
|---|---|---|
| 759,881 | 09/1997 | Malcolm Taylor |
| 692,154 | 08/2001 | Maxim Smirnov |
| 680,558 | 09/2001 | Maxim Smirnov |
| 653,720 | 11/2002 | Serge Voskoboynikov |
| 645,667 | 01/2004 | Matt Mahoney |
| 637,116 | 04/2004 | Alexander Ratushnyak |
| 608,980 | 12/2004 | Alexander Ratushnyak |
| 603,416 | 04/2005 | Przemysław Skibiński |
| 596,314 | 10/2005 | Alexander Ratushnyak |
| 593,620 | 12/2005 | Alexander Ratushnyak |
| 589,863 | 05/2006 | Alexander Ratushnyak |
| 580,170 | 07/2010 | Alexander Ratushnyak |
Примечания
См. также
Шаблон:Стандартные тестовые объекты
