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

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

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

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

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

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

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

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

Конкурсы сжатия

21 мая 1996 года Leonid A. Broukhis начал конкурс "Calgary corpus Compression and SHA-1 crack Challenge"^[5], в котором проводилось соревнование по сжатию корпуса 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". Полный список рекордов в рамках конкурса:

Начиная с 2004 года рекордное сжатие достигалось различными вариантами архиватора PAQ, имеющими открытый исходный код (лицензия GPL).

Примечания