Алгоритмы сжатия в определении авторства

Д.В.Хмелев

Translate this page into:

Эта работа посвящена использованию алгоритмов сжатия данных в задаче определения авторства, а также приведем результаты проверки этого нового метода на примере той же выборки данных, что использовалась в в работе [1].

Вначале нам потребуется несколько определений, которые, впрочем, не должны испугать математически неподготовленного читателя в силу своей простоты. Под текстом здесь понимается последовательность букв из некоторого алфавита A. Длину текста B мы опять будем обозначать через |B|. Назовем конкатенацией текстов B и A последовательность S длины |B|+|A|, начало которой совпадает с B, а конец совпадает с A. При этом будем писать, что S = A.B.

Дадим теперь <<идеальное>> определение относительной сложности в духе определения колмогоровской сложности (по поводу которой см. [2], а также оригинальную работу А.Н. Колмогорова [3]): относительная сложность K(A | B) текста A относительно текста B - это длина наименьшей программы в двоичном алфавите, которая переводит текст B в текст A. К сожалению, K(A | B) невычислима и неясно как можно ее использовать на практике.

Некоторое грубое приближение к ней, впрочем, вполне достаточное, как мы увидим далее, для целей определения авторства, можно получить с помощью алгоритмов сжатия данных. Определим относительную сложность C(A | B) текста A по отношению к тексту B следующим образом. Сожмем текст B в текст B', и текст S = B.A в текст S'. Теперь положим C(A | B) = |S'|-|B'|. Данное определение содержит неоднозначность, ибо не сказано, каким именно способом производится сжатие. В настоящем исследовании будет использоваться несколько способов сжатия, которые описаны ниже.

Нас интересует применение функции C(A | B) в задаче определения авторства. Предположим, что у нас имеются тексты n авторов. Отберем у каждого автора по контрольному тексту U₁, ..., U_n. Все остальные тексты у каждого автора объединим в один текст T₁, ..., T_n.

Для каждого контрольного текста i авторство определяется следующим образом. Сначала определяется ранг R_i числа C(U_i | T_i) в наборе чисел {C(U_i | T₁), ..., C(U_i | T_n)}. Ранги принимают значения от 0 до n-1. Если ранг R_i равен 0, то авторство i-того контрольного текста определено верно. Аналогично [1] можно ввести много различных характеристик точности метода определения авторства. Например,

1) Простейшая характеристика - число нулевых рангов R_i

2) Более обобщенную характеристику дает средний ранг

M = 1 n n е i = 1  Ri.

Проверка различных алгоритмов сжатия проведена на корпусе текстов, который использовался в [1]. Как упомянуто ранее, корпус состоит из 385 текстов 82 писателей. Общий объем текстов составляет около 128 миллионов букв. Тексты подверглись предварительной обработке. Во-первых, были склеены все слова, разделенные переносом. Далее были выкинуты все слова, начинавшиеся с прописной буквы. Оставшиеся слова помещены в том порядке, в котором они находились в исходном файле с разделителем из символа перевода строки. У каждого из n писателей было отобрано по контрольному произведению U_i. Остальные тексты были слиты в обучающие тексты T_i, i = 1, ..., 82. Объем каждого контрольного произведения составлял не менее 50-100 тысяч букв.

Рассмотрим теперь возможные алгоритмы сжатия данных без потерь. Следующие алгоритмы наиболее популярны в последнее время: кодирование Хаффмана, арифметическое кодирование, метод Барроуза-Виллера [4] и множество вариаций метода Лемпеля-Зива [5]. Некоторые алгоритмы специально ориентированы на сжатие текста: это алгоритмы PPM [6] (использующие марковскую модель небольшого порядка) и DMC (использующий динамически изменяемую марковскую модель) [7]. Каждый алгоритм имеет большое число модификаций и параметров (например, существует динамическое кодирование Хаффмана, далее, варьируется объем используемого словаря и пр. и пр.). Кроме того, существует множество <<смешанных>> алгоритмов, где текст, сжатый, например, с помощью алгоритма PPM, дополнительно кодируется с помощью кода Хаффмана.

Все эти алгоритмы реализованы в многочисленных программах, которых в настоящий момент существует не менее 150. Каждая из них реализует, вообще говоря, разные варианты алгоритмов сжатия данных. Дополнительное разнообразие возникает из-за того, что у многих программ имеется несколько версий, которые также имеют разные алгоритмы сжатия. Было отобрано лишь несколько из них, широко представляющих весь спектр программ сжатия данных, которые и показаны в табл. 1.

Table 1: Программы сжатия

Программа	Автор	[Используемые || алгоритмы]
1. 7zip версия 2.11	Игорь Павлов	арифм. кодирование, LZ + арифметическое кодирование, PPM
2. arj версия 2.60	RAO Inc.	LZSS + Хаффман
3. bsa версия 1.9.3	Сергей Бабичев	LZ
4. bzip2	Джулиан Сьюард	Барроуз-Виллер + Хаффман
5. compress	Sun Inc.	LZW
6. dmc	Гордон В. Кормак	DMC
7. gzip	Жан-Луи Гаили	код Шеннона-Фано, Хаффман
8. ha версия 0.999c	Гарри Хирвола	Скользящее окно словаря + арифм.
9. huff1	Вильям Демас (LDS 1.1)	статический Хаффман
10. lzari	Харахико Окумура (LDS 1.1)	LZSS+арифм.
11. lzss	Харахико Окумура (LDS 1.1)	LZSS
12. ppm	Вильям Теахан	PPM
13. ppmd5 версия F	Дмитрий Шкарин	PPM
14. rar версия 2.00	Евгений Рошаль	вариант LZ77 + Хаффман
15. rar версия 2.70	Евгений Рошаль	вариант LZ77 + Хаффман
16. rk версия 1.03a	Малькольм Тейлор	LZ, PPMZ

Большинство из этих программ с описаниями можно получить из Индекса архиваторов¹, который поддерживает Джефф Гилхрист². Программа compress взята из операционной системы SunOS 5.6. Программа dmc доступна по ftp³. Заметим, что dmc имеет опцию максимума используемой оперативной памяти. В нашем случае использовалась опция в 100000000 байт. Пакет программ LDS 1.1 также доступен по ftp⁴. Программа ppm доступна с домашней страницы ее автора⁵.

Результаты применения этих программ представлены в табл. 2, где в последней строке приведены данные, которые получаются при применении цепей Маркова (см. [1]). на том же материале. Вычисления, выполненные при составлении табл. 2, проводились под несколькими операционными системами на разных платформах и заняли около трех недель непрерывного счета.

Table 2: Точность определения авторства текста с использованием алгоритмов сжатия данных

Программа	Ранг
	0	1	2	3	4	? 5	M
7zip	39	9	3	2	3	26	6.43
arj	46	5	2	7	2	20	5.16
bsa	44	9	3	1	1	24	5.30
bzip2	38	5	5	1		33	13.68
compress	12	1	1	3	2	63	24.37
dmc	36	4	3	4	4	31	9.81
gzip	50	4	1	2	1	24	4.55
ha	47	8	1	3	3	20	5.60
huff1	10	11	4	4	2	51	15.37
lzari	17	5	4	2	6	48	14.99
lzss	14	3	1	1	3	60	20.05
ppm	22	14	2	1	3	40	10.39
ppmd5	46	6	6	2		22	5.96
rar 2.70	58	1	1	1		21	7.22
rar 2.00	71	3		2	1	5	1.44
rk	52	9	3	1		17	4.20
Цепи Маркова (см. [1])	69	3	2	1		7	2.35

Из данных таблицы 2 следует, что программы сжатия угадывают истинных писателей весьма часто. Поэтому их использование, несомненно, имеет смысл. Заметим, что результаты применения программы rar 2.00 даже превосходят результаты, полученные ранее при использовании цепей Маркова. Хотя такое превосходство можно отнести на счет определенной статистической погрешности, этот результат является лучшим на нынешний день.

По-видимому, такие прекрасные результаты связаны с тем, что программы сжатия действительно лучше адаптируются к контрольному тексту, переработав к тому времени обучающий текст истинного автора, чем какого-либо другого. Недостатком этого метода по сравнению с методом цепей Маркова [1] является то, что сами алгоритмы сжатия менее <<прозрачны>>, а у коммерческих программ и вовсе недоступны для изучения. Тем не менее, многие среди представленных в табл. 1 программ, например, программы gzip и bzip имеют открытый исходный код и хорошо документированные открытые алгоритмы и дальнейшее их изучение может открыть причины эффективности изложенного подхода к определению авторства.

Несомненное достоинство представленного здесь метода определения авторства состоит в том, что он доступен буквально на каждом компьютере и не требует никаких специальных программ при выборе из небольшого числа авторов, поскольку большинство из описанных архиваторов широко распространены, а некоторые (вроде gzip или rar) имеют реализации на всех платформах и всех операционных системах.

По поводу объяснения эффективности этого подхода выдвигается гипотеза о том, что данный метод очень эффективно измеряет сложность текста относительны словаря, который используется автором. Заметим, однако, что с нашей точки зрения эта гипотеза все еще не является вполне удовлетворительной.

References

[1]

Хмелев Д.В. Распознавание автора текста с использованием цепей А.А. Маркова//Вестн. МГУ. Сер. 9, Филология. 2000. N2. с.115-126.

[2]

Li M. Vitányi P. An Introduction to Kolmogorov Complexity and Its Applications. Springer, New York, 2nd edition, 1997.

[3]

Колмогоров А.Н. Три подхода к определению понятия <<количество информации>>//Проблемы передачи информации, т.1, N1, с.3-11, 1965.

[4]

Burrows M. Wheeler D.J. A block-sorting lossless data compression algorithm//Digital SRC Research Report 124 1994. ftp://ftp.digital.com/pub/DEC/SRC/research-reports/SRC-124.ps.gz

[5]

Lempel A., Ziv J. On the complexity of finite sequences//IEEE Transactions on Information Theory. 1976. V.22 N1. P.75-81.

[6]

Cleary J.G., Witten I.H. Data compression using adaptive coding and partial string matching//IEEE Transactions on Communications. 1984. V.32. N4. P.396-402.

[7]

Cormack G.V. and Horspool R.N . Data Compression Using Dynamic Markov Modelling//The Computer Journal. 1987. V.30. N6. P.541-550.

---

Footnotes:

¹ http://web.act.by.net/~act/act-index.html

² Jeff Gilchrist, jeffg@cips.ca

³ http://plg.uwaterloo.ca/~ftp/dmc/

⁴ ftp://garbo.uwasa.fi/pc/programming/lds_11.zip

⁵ http://www.cs.waikato.ac.nz/~wjt/

---

File translated from T_EX by T_TH, version 2.70.
On 15 Oct 2001, 15:02.