Вы находитесь на архивной версии сайта лаборатории, некоторые материалы можно найти только здесь.
Актуальная информация о деятельности лаборатории на lex.philol.msu.ru.
Сложностной подход к задаче определения авторства текста

Сложностной подход
к задаче определения авторства текста

Хмелёв Дмитрий Викторович

 

 

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

“Идеальное” определение относительной сложности в духе определения колмогоровской сложности (по поводу которой см. [2]) таково: относительная сложность K(A,B) текста A относительно текста B - это длина наименьшей программы в двоичном алфавите, которая переводит текст B в текст A. К сожалению, величина K(A,B) невычислима, а потому априори неясно, как можно ее использовать на практике.

В настоящем исследовании показано, что с точки зрения задачи определения авторства можно вместо невычислимой величины K(A,B) использовать величины, получаемые с помощью современных программ сжатия. Определим относительную сложность C(B, A) текста A относительно текста B как разность длин сжатого текста BA (который получается приписыванием текста A в конец текста B) и сжатого текста B. Чем меньше эта величина, тем больше текст A зависит от текста B. Данное определение содержит неоднозначность, поскольку не сказано, каким именно способом производится сжатие. В настоящем исследовании будет исследовано несколько алгоритмов сжатия, которые уже реализованы в компьютерных программах. Опишем теперь, как применять введенное понятие относительной сложности к определению авторства. Имеются тексты T1, …, Tn известных авторов. Для текста U определим разность C(Ti,U) длин сжатых текстов TiU и Ti. Текст U относится к автору i с наименьшим значением этой разности.

Аналогично [1] можно ввести много различных характеристик точности метода определения авторства: 1) простейшая характеристика - число точных угадываний; 2) более обобщенная характеристика - средний ранг автора в числе претендентов на его собственное произведение. Проверка характеристик проводилась на корпусе текстов, который уже использовался в [1] и который состоит из 385 текстов 82 писателей. Общий объем текстов составляет около 128 Мб. Тексты подверглись предварительной обработке. Во-первых, были склеены все слова, разделенные переносом. Далее были отброшены все слова, начинавшиеся с прописной буквы (таким образом мы избавляемся от шума, связанного с именами литературных героев). Оставшиеся слова помещены в том порядке, в котором они находились в исходном тексте с разделителем из символа перевода строки. У каждого из n = 82 авторов случайно было отобрано по контрольному произведению Ui. Остальные тексты у каждого автора i были объединены в обучающие тексты Ti, i =1, …, 82. Объем каждого контрольного произведения составлял не менее 50-100 тысяч букв. Результаты вычислений представлены в следующей таблице, где в первом столбце наряду с названием программы в скобках приведен используемый в ней алгоритм (Ar обозначает арифметическое кодирование, LZ - различные модификации алгоритма Лемпеля-Зива, DMC - так называемый алгоритм построения динамической цепи Маркова, PPM - алгоритмы, основанные на построении цепей Маркова высокого порядка). В последней строке таблицы приведены данные исследования [1] по применению цепей Маркова на той же выборке данных.

 

Архиватор

Ранг

 

1

2

3

4

5

і6

средний

7zip (Ar,LZ+Ar, PPM)

39

9

3

2

3

26

7.43

arj (LZSS+Хаффман)

46

5

2

7

2

20

6.16

bsa (LZ)

44

9

3

1

1

24

6.30

bzip2 (Барроу-Виллер + Хаффман)

38

5

5

1

 

33

14.68

compress (LZW)

12

1

1

3

2

63

25.37

dmc (DMC)

36

4

3

4

4

31

10.82

gzip (Шеннон-Фано, Хаффман)

50

4

1

2

1

24

5.55

ha (Ar)

47

8

1

3

3

20

6.60

huff1 (статический Хаффман)

10

11

4

4

2

51

16.37

lzari (LZSS+Ar)

17

5

4

2

6

48

15.99

lzss (LZSS)

14

3

1

1

3

60

21.05

ppm (PPM)

22

14

2

1

3

40

11.39

ppmd5 (PPM)

46

6

6

2

 

22

6.96

rar (LZ77+Хаффман)

58

1

1

1

 

21

8.22

rarw (LZ77+Хаффман)

71

3

 

2

1

5

2.44

rk (LZ+Хаффман)

52

9

3

1

 

17

5.20

Марковские цепи (см. [1])

69

3

2

1

 

7

3.35

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

 

Литература:

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

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