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 байта исходного файла) для каждого файла из набора, затем они усреднялись. Затем чаще стали указывать суммарный размер всех сжатых файлов[3].
Некоторые архиваторы допускали более эффективное сжатие при одновременной обработке всего корпуса (например, при их помещении в несжатый контейнер тира tar), за счет использования взаимной информации. Другие архиваторы, наоборот, хуже сжимали такой вариант из-за медленной реакции компрессора на изменение характеристик данных. Одновременное сжатие всего корпуса использовалось Matt Mahoney в его книге Data Compression Explained[4].
В таблице указаны размеры сжатого корпуса для нескольких популярных архиваторов.
| Архиватор | Опции | Сжатие 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 | |
| [compression.ru/ds/ ppmd] Jr1 | -m256 -o16 | 740,737 | 754,243 |
| [compression.ru/ds/ ppmonstr] J | 675,485 | 669,497 |
Конкурсы сжатия
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". Полный список рекордов в рамках конкурса:
| Размер (байт) | Месяц и год | Автор |
|---|---|---|
| 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 |
Начиная с 2004 года рекордное сжатие достигалось различными вариантами архиватора PAQ, имеющими открытый исходный код (лицензия GPL).
Напишите отзыв о статье "Calgary Corpus"
Примечания
- ↑ Ian H. Witten, Alistair Moffat, Timothy C. Bell. [books.google.com/books?id=2F74jyPl48EC&pg=PA92&dq=%22calgary+corpus%22+%22canterbury+corpus%22&hl=en Managing Gigabytes: Compressing and Indexing Documents and Images]. — Morgan Kaufmann, 1999. — P. 92.
- ↑ Salomon David. [books.google.com/books?id=ujnQogzx_2EC&pg=PA12&dq=%22calgary+corpus%22+%22canterbury+corpus+started%22&hl=en&sa=X&ei=KVwQUr3vFaSVygH19oAw&ved=0CDYQ6AEwAQ#v=onepage&q=%22calgary%20corpus%22%20%22canterbury%20corpus%20started%22&f=false Data Compression: The Complete Reference]. — Fourth. — Springer, 2007. — P. 12. — ISBN 9781846286032.
- ↑ uclc.info/calgary_corpus_compression_test.htm
- ↑ [mattmahoney.net/dc/dce.html#Section_214 Data Compression Explained]
- ↑ [mailcom.com/challenge/ The Compression/SHA-1 Challenge]
См. также
| ||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Отрывок, характеризующий Calgary Corpus
– Слава Богу, – сказала Соня, крестясь. – Но, может быть, она обманула тебя. Пойдем к maman.Петя молча ходил по комнате.
– Кабы я был на месте Николушки, я бы еще больше этих французов убил, – сказал он, – такие они мерзкие! Я бы их побил столько, что кучу из них сделали бы, – продолжал Петя.
– Молчи, Петя, какой ты дурак!…
– Не я дурак, а дуры те, кто от пустяков плачут, – сказал Петя.
– Ты его помнишь? – после минутного молчания вдруг спросила Наташа. Соня улыбнулась: «Помню ли Nicolas?»
– Нет, Соня, ты помнишь ли его так, чтоб хорошо помнить, чтобы всё помнить, – с старательным жестом сказала Наташа, видимо, желая придать своим словам самое серьезное значение. – И я помню Николеньку, я помню, – сказала она. – А Бориса не помню. Совсем не помню…
– Как? Не помнишь Бориса? – спросила Соня с удивлением.
– Не то, что не помню, – я знаю, какой он, но не так помню, как Николеньку. Его, я закрою глаза и помню, а Бориса нет (она закрыла глаза), так, нет – ничего!
– Ах, Наташа, – сказала Соня, восторженно и серьезно глядя на свою подругу, как будто она считала ее недостойной слышать то, что она намерена была сказать, и как будто она говорила это кому то другому, с кем нельзя шутить. – Я полюбила раз твоего брата, и, что бы ни случилось с ним, со мной, я никогда не перестану любить его во всю жизнь.
Наташа удивленно, любопытными глазами смотрела на Соню и молчала. Она чувствовала, что то, что говорила Соня, была правда, что была такая любовь, про которую говорила Соня; но Наташа ничего подобного еще не испытывала. Она верила, что это могло быть, но не понимала.
– Ты напишешь ему? – спросила она.
Соня задумалась. Вопрос о том, как писать к Nicolas и нужно ли писать и как писать, был вопрос, мучивший ее. Теперь, когда он был уже офицер и раненый герой, хорошо ли было с ее стороны напомнить ему о себе и как будто о том обязательстве, которое он взял на себя в отношении ее.
– Не знаю; я думаю, коли он пишет, – и я напишу, – краснея, сказала она.
– И тебе не стыдно будет писать ему?
Соня улыбнулась.
– Нет.
– А мне стыдно будет писать Борису, я не буду писать.
– Да отчего же стыдно?Да так, я не знаю. Неловко, стыдно.
– А я знаю, отчего ей стыдно будет, – сказал Петя, обиженный первым замечанием Наташи, – оттого, что она была влюблена в этого толстого с очками (так называл Петя своего тезку, нового графа Безухого); теперь влюблена в певца этого (Петя говорил об итальянце, Наташином учителе пенья): вот ей и стыдно.
– Петя, ты глуп, – сказала Наташа.
– Не глупее тебя, матушка, – сказал девятилетний Петя, точно как будто он был старый бригадир.
Графиня была приготовлена намеками Анны Михайловны во время обеда. Уйдя к себе, она, сидя на кресле, не спускала глаз с миниатюрного портрета сына, вделанного в табакерке, и слезы навертывались ей на глаза. Анна Михайловна с письмом на цыпочках подошла к комнате графини и остановилась.
– Не входите, – сказала она старому графу, шедшему за ней, – после, – и затворила за собой дверь.
Граф приложил ухо к замку и стал слушать.
Сначала он слышал звуки равнодушных речей, потом один звук голоса Анны Михайловны, говорившей длинную речь, потом вскрик, потом молчание, потом опять оба голоса вместе говорили с радостными интонациями, и потом шаги, и Анна Михайловна отворила ему дверь. На лице Анны Михайловны было гордое выражение оператора, окончившего трудную ампутацию и вводящего публику для того, чтоб она могла оценить его искусство.
– C'est fait! [Дело сделано!] – сказала она графу, торжественным жестом указывая на графиню, которая держала в одной руке табакерку с портретом, в другой – письмо и прижимала губы то к тому, то к другому.
Увидав графа, она протянула к нему руки, обняла его лысую голову и через лысую голову опять посмотрела на письмо и портрет и опять для того, чтобы прижать их к губам, слегка оттолкнула лысую голову. Вера, Наташа, Соня и Петя вошли в комнату, и началось чтение. В письме был кратко описан поход и два сражения, в которых участвовал Николушка, производство в офицеры и сказано, что он целует руки maman и papa, прося их благословения, и целует Веру, Наташу, Петю. Кроме того он кланяется m r Шелингу, и m mе Шос и няне, и, кроме того, просит поцеловать дорогую Соню, которую он всё так же любит и о которой всё так же вспоминает. Услыхав это, Соня покраснела так, что слезы выступили ей на глаза. И, не в силах выдержать обратившиеся на нее взгляды, она побежала в залу, разбежалась, закружилась и, раздув баллоном платье свое, раскрасневшаяся и улыбающаяся, села на пол. Графиня плакала.
– О чем же вы плачете, maman? – сказала Вера. – По всему, что он пишет, надо радоваться, а не плакать.
Это было совершенно справедливо, но и граф, и графиня, и Наташа – все с упреком посмотрели на нее. «И в кого она такая вышла!» подумала графиня.
Письмо Николушки было прочитано сотни раз, и те, которые считались достойными его слушать, должны были приходить к графине, которая не выпускала его из рук. Приходили гувернеры, няни, Митенька, некоторые знакомые, и графиня перечитывала письмо всякий раз с новым наслаждением и всякий раз открывала по этому письму новые добродетели в своем Николушке. Как странно, необычайно, радостно ей было, что сын ее – тот сын, который чуть заметно крошечными членами шевелился в ней самой 20 лет тому назад, тот сын, за которого она ссорилась с баловником графом, тот сын, который выучился говорить прежде: «груша», а потом «баба», что этот сын теперь там, в чужой земле, в чужой среде, мужественный воин, один, без помощи и руководства, делает там какое то свое мужское дело. Весь всемирный вековой опыт, указывающий на то, что дети незаметным путем от колыбели делаются мужами, не существовал для графини. Возмужание ее сына в каждой поре возмужания было для нее так же необычайно, как бы и не было никогда миллионов миллионов людей, точно так же возмужавших. Как не верилось 20 лет тому назад, чтобы то маленькое существо, которое жило где то там у ней под сердцем, закричало бы и стало сосать грудь и стало бы говорить, так и теперь не верилось ей, что это же существо могло быть тем сильным, храбрым мужчиной, образцом сыновей и людей, которым он был теперь, судя по этому письму.
