Calgary Corpus

Перейти к навигацииПерейти к поиску

Calgary corpus - набор текстовых и двоичных файлов, часто использовавшийся в качестве стандартного теста алгоритмов сжатия данных и сравнения их эффективности. Набор был собран в Университете Калгари в 1987 году и широко применялся в 1990-х. В 1997 был предложен новый тестовый набор Canterbury corpus[1], в котором были учтены некоторые замечания к репрезентативности корпуса Калгари[2].

Состав корпуса

В наиболее часто используемой форме корпус Калгари состоит из 14 файлов общим объёмом 3141622 байт:

Размер (байт)Имя файлаОписание
111,261BIBТекст ASCII в формате утилиты UNIX "refer" с 725 библиографическими записями.
768,771BOOK1Неформатированный текст ASCII новеллы Томаса Харди Far from the Madding Crowd.
610,856BOOK2Текст ASCII в формате "troff" – Ian H. Witten: Principles of Computer Speech.
102,400GEOСейсмические данные в виде 32 битных чисел с плавающей запятой в формате IBM.
377,109NEWSТекст ASCII – набор сообщений из групп USENET.
21,504OBJ1Исполняемый файл для VAX, полученный компиляцией PROGP.
246,814OBJ2Исполняемый файл для Macintosh, программа "Knowledge Support System".
53,161PAPER1Статья в формате "troff" – Witten, Neal, Cleary: Arithmetic Coding for Data Compression.
82,199PAPER2Статья в формате "troff" – Witten: Computer (in)security.
513,216PICИзображение размером 1728 x 2376: текст на французском и линейные диаграммы.
39,611PROGCИсходный код на языке C – программа UNIX compress v4.0.
71,646PROGLИсходный код на языке Lisp – системное приложение.
49,379PROGPИсходный код на языке Pascal – программа для оценки сжатия PPM.
93,695TRANSТекст ASCII и управляющие последовательности - запись терминальной сессии.

Реже используется набор из 18 файлов, в который дополнительно включены 4 текстовых файла в формате "troff" - PAPER3-PAPER6.

Тестирование

Корпус Calgary часто использовался для сравнения эффективности сжатия в 1990-е годы. Результаты часто указывались в виде коэффициента бит на байт (среднее количество бит в сжатом файле, требуемое для кодирования 1 байта исходного файла) для каждого файла из набора, затем они усреднялись. Затем чаще стали указывать суммарный размер всех сжатых файлов.

Некоторые архиваторы допускали более эффективное сжатие при одновременной обработке всего корпуса (например, при их помещении в несжатый контейнер тира tar), за счет использования взаимной информации. Другие архиваторы, наоборот, хуже сжимали такой вариант из-за медленной реакции компрессора на изменение характеристик данных. Одновременное сжатие всего корпуса использовалось Matt Mahoney в его книге Data Compression Explained[3].

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

АрхиваторОпцииСжатие 14 отдельных файловОбъединенный tar архив
Без сжатия3,141,6223,152,896
compress1,272,7721,319,521
Info-ZIP 2.32-91,020,7811,023,042
gzip 1.3.5-91,017,6241,022,810
bzip2 1.0.3-9828,347860,097
7-zip 9.12b848,687824,573
ppmd Jr1-m256 -o16740,737754,243
ppmonstr J675,485669,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,88109/1997Malcolm Taylor
692,15408/2001Maxim Smirnov
680,55809/2001Maxim Smirnov
653,72011/2002Serge Voskoboynikov
645,66701/2004Matt Mahoney
637,11604/2004Alexander Ratushnyak
608,98012/2004Alexander Ratushnyak
603,41604/2005Przemysław Skibiński
596,31410/2005Alexander Ratushnyak
593,62012/2005Alexander Ratushnyak
589,86305/2006Alexander Ratushnyak
580,17007/2010Alexander Ratushnyak

Примечания

  1. ↑ Ian H. Witten, Alistair Moffat, Timothy C. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images (англ.). — Morgan Kaufmann, 1999. — P. 92.
  2. ↑ Salomon, David. Data Compression: The Complete Reference (неопр.). — Fourth. — Springer, 2007. — С. 12. — ISBN 9781846286032.
  3. ↑ Data Compression Explained. Дата обращения: 6 мая 2015. Архивировано 12 мая 2015 года.
  4. ↑ The Compression/SHA-1 Challenge. Дата обращения: 6 мая 2015. Архивировано 25 апреля 2015 года.

См. также