|
Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://www.philol.msu.ru/~lex/khmelev/proceedings/ruscongr/tez.html
Дата изменения: Unknown Дата индексирования: Fri Feb 28 19:08:18 2014 Кодировка: Windows-1251 Поисковые слова: шеннон |
Сложностной подход
к задаче определения авторства текстаХмелев Дмитрий Викторович
Как было показано в работе [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.