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

Примечания

  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
  4. ↑ The Compression/SHA-1 Challenge

См. также


Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Calgary_Corpus&oldid=10419712