Вы находитесь на архивной версии сайта лаборатории, некоторые материалы можно найти только здесь.
Актуальная информация о деятельности лаборатории на lex.philol.msu.ru.
О.В.КУКУШКИНА, А.А.ПОЛИКАРПОВ, Д.В.ХМЕЛЁВ: ОПРЕДЕЛЕНИЕ АВТОРСТВА ТЕКСТА...

KOI WIN LATEX PS PDF

УДК 621.391.1

ОПРЕДЕЛЕНИЕ АВТОРСТВА ТЕКСТА С ИСПОЛЬЗОВАНИЕМ БУКВЕННОЙ И ГРАММАТИЧЕСКОЙ ИНФОРМАЦИИ

О.В. КУКУШКИНА, А.А.ПОЛИКАРПОВ, Д.В. ХМЕЛЁВ

Статья опубликована в журнале "Проблемы передачи информации", 2001, т.37, вып.2 (апрель-июнь), с.96-108. Translated in "Problems of Information Transmission", pp. 172-184.

Поступила в редакцию 08.08.2000. После переработки 11.01.2001.

Содержание

1  Введение
2  Предварительная обработка
3  Метод и его перекрестная проверка
4  Описание результатов
5  Заключение
A  Приложение
Применение алгоритмов сжатия данных
в задаче определения авторства


Метод, применяемый в данной статье для определения авторства текста, основывается на формальной математической модели встречаемости последовательности элементов текста как реализации цепи Маркова. В качестве элементов текста используются последовательности букв и последовательности грамматических классов слов. Оказывается, частоты употребления пар букв и пар грамматических классов в тексте на русском языке являются достаточно устойчивой характеристикой автора и, видимо, их можно использовать, чтобы решать проблемы спорного авторства текста. Проводится сопоставление результатов, полученных при использовании различных вариантов методики в указанных единицах. Эксперимент проводится на 385 текстах 82 писателей.

В Приложении описано исследование Д.В. Хмелёва о возможности применения алгоритмов сжатия данных в задаче определения авторства.

1  Введение

В настоящей работе задача определения авторства ставится следующим образом. Пусть имеются достаточно длинные фрагменты прозаических произведений ряда авторов на русском или ином языке, использующем фонологическую (неиероглифическую) письменность1. Про некоторый анонимный фрагмент известно, что он принадлежит одному из этих авторов, но какому - неизвестно. Требуется узнать, кому именно. На основе результатов экспериментальной проверки метода, предложенного Д.В. Хмелёвым в работе [1], утверждается, что с определенной, достаточно высокой степенью вероятности это возможно. Избранный метод базируется на учете статистики употребления пар элементов любой природы, идущих друг за другом в тексте (букв, морфем, словоформ и т.п.).

Традицию формального подхода к поиску методики определения авторства, по-видимому, следует отсчитывать от работы [2]. На эту работу откликнулся Марков [3], что свидетельствует о живом интересе создателя аппарата цепей Маркова к данной теме. Заметим также, что первое применение <<испытаний, связанных в цепь>>, Марков описал в работе [4], посвященной анализу распределения гласных и согласных среди первых 20000 букв <<Евгения Онегина>>.

Современное состояние методов определения авторства в нашей стране отражено в [5], а хороший обзор зарубежных авторов дан в работе [6]. Несмотря на огромное разнообразие описанных методов, ни один из них никогда не применялся к большому количеству текстов. Дело в том, что часто эти методы не поддаются автоматизации и требуют некоторого человеческого вмешательства, что приводит к практической невозможности обработки большого количества текстов большого объема. В связи с этими проблемами встает вопрос общности каждого из методов: можно ли применять какой-либо из них вне ситуации, в которой они были разработаны?

Примечательным исключением до последнего времени являлась работа [7], в которой избранный там метод был применен к достаточно большому количеству текстов. В ней исследовалась доля служебных слов, которые используются автором, и обнаружено, что она устойчива для каждого из авторов на большом количестве текстов русских писателей XVIII-XX-го веков. Данную методику авторы работы [7] применили к проблеме определения плагиата.

Новый метод определения авторства текстов, написанных на естественном языке (независимо от того, на каком именно), впервые предложен Хмелёвым в работе [1].

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

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

Марковские цепи разных порядков использовались в многочисленных работах 50-60-х годов XX века, описанных в книге [8], для оценки энтропии различных типов текстов. Однако ни в одной из этих работ не поднимался вопрос о применении марковских цепей в рамках задачи определения авторства. Более того, общепринятой была точка зрения, что на уровне букв и буквосочетаний характеристикилюбого литературного текста близки к средним по языку и, с практической точки зрения, неразличимы (см. [8] и [9,3]). Принцип максимального правдоподобия также никогда ранее не применялся в задаче определения авторства текстов в силу следующих причин: во-первых, до появления компьютеров и большого количества текстов в электронном виде было затруднительно производить подсчеты на материале большого объема; во-вторых, определённый психологический барьер представляло отсутствие теоретического обоснования такого подхода, поскольку цепь Маркова первого порядка может служить лишь первым и очень грубым приближением естественно-языкового текста, на что многократно указывалось в различных работах по оценке энтропии текста с помощью цепей Маркова больших порядков [8]; и, наконец, в-третьих, в самой задаче определения авторства считался перспективным поиск устойчивых количественных характеристик грамматического характера, позволяющих различать писателей, причем, по-видимому, единственный серьезный успех в этом направлении для русского языка был получен лишь недавно (см. [7]).

В настоящей работе мы развиваем процедуру проверки метода [1], а также проверяем возможности его применения с использованием разных единиц анализа:

(а) пар букв в их естественных последовательностях в тексте - в словах (в той форме, в которой они употреблены в тексте) и пробелах между ними;

(б) пар букв в последовательностях букв в приведенных (словарных, лемматизованных или исходных) формах слов; например, предыдущее предложение в таком случае предстает в виде <<пара буква в последовательность буква приведенный словарный лемматизованный или исходный форма слово>>;

(в) пар наиболее обобщенных (<<неполных>>) грамматических классов слов, частей речи, в их последовательностях в предложениях текста - существительные, глаголы, прилагательные и т.п.: всего 14 традиционно выделяемых грамматических классов слов - частей речи и 4 других условных категории вроде <<конец предложения>>, <<сокращение>> <<неясный класс>> и <<знак тире>>; категория <<неясный класс>> введена в связи с тем, что разбор по грамматическим классам проводился автоматически (и покрывал более 99% всех встреченных слов), но некоторые слова (например, с опечатками) не поддавались автоматической обработке, а потому их грамматический класс оставался неясным.

(г) пар менее обобщенных (<<полных>>) грамматических классов слов (а именно таких семантико-грамматических разрядов, как одушевленные существительные, неодушевленные существительные, прилагательные качественные, относительные, притяжательные и т.п.).

Была произведена перекрестная проверка метода на материале 385 текстов 82 авторов (результаты проверки приведены в табл. 1 и 2, а список авторов с указанием объема материала и числа текстов данного автора - в табл. 3).

Одним из показателей точности метода может служить процент правильно определенных произведений. На материале вариантов (а) и (б) получены наиболее точные результаты (73% и 62% точных определений соответственно). На материале варианта (в) получен 61% точных определений. На материале варианта (г) получены существенно более худшие результаты (4%).

В §2 описываются принципы и результаты предварительной обработки текстов. В §3 описана методика перекрестной проверки. Детальное описание результатов дано в §4 с представлением выводов в заключении §5. В Приложении, которое написано Д.В. Хмелёвым, изложен еще один подход к определению авторства с использованием алгоритмов сжатия данных.

2  Предварительная обработка

Исходный корпус текстов в результате предварительной обработки был представлен во всех ранее описанных вариантах (а)-(г).

Отличие варианта (а) от первоначального текста (и в этом одно из отличий данного исследования от [1]) состоит в том, что отброшены все слова, для которых не удалось автоматически определить грамматический класс (а следовательно, и найти словарную форму). Это было сделано, чтобы можно было сравнивать результаты с результатами варианта (б). При этом весь текст превращен в последовательность слов и пробелов между ними, вся пунктуация была отброшена, и, кроме того, были выкинуты все слова с заглавной буквы (включая слова, с которых начинаются предложения; такая уловка, как показано в работе [1], позволяет значительно увеличить точность определения авторства; по-видимому, это улучшение связано с тем, что отбрасываются имена литературных героев, как правило, не соотносящиеся со стилем автора литературного текста). В используемом алфавите буква <<ё>> склеивалась с буквой <<е>>, в результате чего вместе с пробелом получилось 33 буквы. Каждая буква кодировалась своим номером: буква<<а>> соответствовала 1, ..., <<я>> соответствовала 32. Пробелу сопоставлялся код 0. Общее количество буквоупотреблений составило 96209964. Общее число разных пар букв, обнаруженных на анализируемом массиве текстов, составило 1011 (из потенциально возможных 33×33 = 1089). Очевидно, 1011 несколько превосходит количество разных пар букв, действительно встречаемых в текстах на русском языке. Это является результатом определенного количества опечаток в электронных версиях книг и может приводить к погрешностям в вычислениях. Чтобы получить некоторую оценку этого шума, были отобраны все буквосочетания, которые вряд ли встречаются в русском языке, и их оказалось 121. Общее количество употреблений этих буквосочетаний равно 38495, что составляет около 0,04% от общего числа употреблений буквосочетаний, чем вполне можно пренебречь.

Преобразование исходных текстов для получения их в виде вариантов (б), (в) и (г) осуществлено на основе автоматического классификатора, разработанного О.В. Кукушкиной в Лаборатории общей и компьютерной лексикологии и лексикографии филологического факультета МГУ на основе грамматического словаря Зализняка [10] и академических грамматик [11,12].

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

Вариант (г) базируется на информации, получаемой при учете лексико-грамматического разряда слов данной части речи (одушевленные существительные, неодушевленные существительные и т.п.).

Приведем некоторую статистику по текстам, отвечающим вариантам (б)-(г).

В варианте (б) общее количество букв составило 110704464. Число разных пар букв в исходных формах слов составило 1029 (из потенциально возможных 33×33 = 1089). Как видно, оно увеличилось в сравнении с вариантом (а). Такой эффект связан с переводом косвенных форм в исходные.

В вариантах (в) и (г) число элементов составило 20262449. При этом в варианте (в) количество разных пар элементов - 302 (из потенциально возможных 18×18 = 324). В варианте (г) число разных пар элементов составило 8124 (из потенциально возможных 112×112 = 12544).

3  Метод и его перекрестная проверка

Анализ текстового материала по каждому из указанных выше вариантов произведен на основе комплекса программ, разработанного Хмелёвым. При обработке каждого варианта отображения корпуса текстов мы покажем результаты перекрестной проверки метода [1]. Перекрестная проверка выполняется следующим образом.

Напомним, что элементы текста кодируются числами от 0 до 32 (в вариантах (а) и (б)), 17 или 111 (в вариантах (в) и (г) соответственно). Код 0 всегда соответствует разграничителю между крупными единицами: в вариантах (а) и (в) код 0 соответствует пробелу между словами, а в вариантах (в) и (г) код 0 соответствует разделителю между предложениями (<<концу предложения>>).

Пусть у нас есть W писателей, у каждого из которых есть Nw текстов, где w = 0, ..., W-1. В первую очередь подсчитывается Qijwn - количество переходов из буквы i в букву j в тексте n (n = 0, ..., Nw-1) автора w (w = 0, ..., W-1). Чтобы найти предсказание автора текста [^n] (известного автора [^w]) с использованием информации об авторстве всех остальных текстов всех авторов (включая автора [^w]), мы подсчитываем
Qijk = Nw-1
е
 n = 0 
 Qijkn,  Qik =
е
 j 
 Qijk
для авторов k№ [^w], а для автора [^w] мы исключаем текст [^n] из обучающей выборки
Qij[^w] =
е
 n№ [^n] 
 Qij[^w]n,  Qi[^w] =
е
 j 
 Qij[^w].

Теперь мы вычисляем
Lk ( ^
w
 
 , ^
n
 
 ) =-
е
 i: Qik > 0 
е
 j: Qijk > 0 
 Qij[^w] [^n] ln Qijk
Qik
и
L[^w] ( ^
w
 
 , ^
n
 
 ) =-
е
 i: Qi[^w] > 0 
е
 j: Qij[^w] > 0 
 Qij[^w] [^n] ln Qij[^w]
Qi[^w]
 .
Если отвлечься от вырожденных случаев Qkij = 0 и Qki = 0, то легко увидеть, что каждоеLk([^w],[^n]) есть минус логарифм вероятности реализации текста [^n] писателя [^w] при условии, что он является реализацией марковской цепи с переходными интенсивностями Pkij = Qkij/Qki. Обоснование для отбрасывания вырожденных слагаемых дают результаты об оптимальной оценке максимума правдоподобия, приведенные в [13].

Также определим ранг Rk([^w],[^n]) как ранг Lk([^w],[^n]) среди {Lk([^w],[^n]), k = 0,ј, W-1}, причем мы отсчитываем начальный ранг с нуля: Rk([^w],[^n])О {0,ј,W-1}; наименьший ранг соответствует наименьшему числу. Если текст соотнесен правильному автору, то ранг R[^w]([^w],[^n]) = 0.

Если текст соотнесен какому-либо другому автору, а правильный автор оказался на втором месте, то R[^w]([^w],[^n]) = 1, и т.д.

В результате перекрестной проверки мы получаем набор рангов
{R[^w]( ^
w
 
 , ^
n
 
 )}[^w]О {0,ј,W-1},[^n]О {0,ј,N[^w]-1}.
Точность методики определения автора характеризуется этим набором рангов. Доля точных угадываний совпадает с долей нулевых рангов. Результаты, близкие к угаданному, характеризуются долей небольших рангов. В качестве характеристики точности угадывания может также служить среднее рангов:


M = 1
W-1
е
 [^w] = 0 
 N[^w]
 W-1
е
 [^w] = 0 
 N[^w]-1
е
 [^n] = 0 
 R[^w]( ^
w
 
 , ^
n
 
 ).
(1)
Мы также приведем результаты перекрестной проверки по методу сравнения частот одиночных букв (в вариантах (а) и (б)) и одиночных грамматических классов (в вариантах (в) и (г)). Этот метод работает так же, как уже описанный, но дополнительно рассчитываются величины
Qk =
е
 i 
 Qki и Q[^w] =
е
 i 
 Q[^w]i
и вместо величинLk([^w], [^n]) используются величины
Gk( ^
w
 
 , ^
n
 
 ) =-
е
 i: Qik > 0 
 ж
з
и
е
 j 
 Qij[^w] [^n] ц
ч
ш 		ln Qik
Qk
и
G[^w]( ^
w
 
 , ^
n
 
 ) =-
е
 i: Qi[^w] > 0 
 ж
з
и
е
 j 
 Qij[^w] [^n] ц
ч
ш 		ln Qi[^w]
Q[^w]
 .

4  Описание результатов

Таблица 1: Результаты перекрестной проверки правильности определения автора текста с использованием последовательности букв

Случай (а)Случай (б)
Словоформы текстаПриведенные формы
RПары буквОдиночныеRПары буквОдиночные
0282/38527/3850240/38512/385
121/385 55/385129/385 40/385
29/385 25/385217/385 19/385
35/385 24/38539/385 16/385
45/385 17/38546/385 16/385
і 563/385237/385і 584/385282/385
M3,3812,69M4,7717,88

Таблица 2: Результаты перекрестной проверки правильности определения автора текста с использованием последовательности грамматических классов

Случай (в)Случай (г)
Обобщенные<<Полные>>
грамматические классыграмматические классы
RПарныеОдиночныеRПарныеОдиночные
0235/385128/385015/3856/385
131/38543/385121/385 12/385
216/38529/38529/385 6/385
38/385 15/385312/385 6/385
411/38517/385419/385 8/385
і 584/385153/385і 5,309/385347/385
M5,4310,13M17,7631,93

Результаты проведенного исследования представлены в табл. 1 и 2. Столбец R отвечает рангам 0, ..., 4 и рангам, не меньшим 5. В строке с рангом 0 приведена доля правильно определенных произведений, в строке с рангом 1 приведена доля таких произведений, что истинный автор оказался на втором месте, и т.д., и наконец, в строке і 5 приведена доля таких произведений, что истинный автор оказался на месте не лучше шестого.

Строка M содержит средний ранг, определенный по формуле (1).

Сразу же отметим, что частоты одиночных букв и одиночных грамматических классов дают низкий, но все-таки существенно неслучайный уровень правильного определения авторства текстов (за исключением одиночных <<полных>> грамматических классов; причины этого нуждаются в дополнительном изучении).

Все расчеты с парами элементов (букв или грамматических классов) дают лучший результат по сравнению с расчетами по одиночным буквам и классам.

Теперь рассмотрим, чем различаются результаты анализа с использованием информации о статистике встречаемости пар букв в естественных словоформах в тексте от результатов использования статистики букв в приведенных (словарных) формах слов (см. табл. 1). Сопоставление показывает, что определение автора оказывается более успешным в случае работы со статистикой естественных последовательностей букв в тексте (73% против 62% точных определений авторства, и средний ранг 3,38 против 4,77). Видимо, <<уравнивание>> ряда словоформ одного слова при лемматизации снимает часть полезной для определения автора информации, связанной с окончаниями слов, что и приводит к ухудшению результатов в варианте (б) по сравнению со вариантом (а).

Сопоставление результатов определения авторства текста на основе статистики употребления пар букв и пар обобщенных (неполных) грамматических классов словоформ (варианты (а) и (в)) показывает, что результаты в том и в другом случае довольно высокие: 73% и 61% точных определений авторства соответственно. По среднему рангу успешного определения авторства обобщенные грамматические классы дают ошибку больше чем на 2 ранга. Относительно более низкая эффективность пар таких единиц как обобщенные грамматические классы (в сравнении с парами букв на естественных словоформах букв) на одном и том же материале может быть связана с меньшим объемом статистики по этим классам (как уже упоминалось, на одном и том же корпусе текстов имеется около 96 миллионов буквоупотреблений в варианте (а) против 20 миллионов употреблений грамматических классов в варианте (в)).

Вместе с тем, обращает на себя внимание тот факт, что использование в анализе одиночных грамматических классов в варианте (в) (см. табл. 2) оказывается существенно более эффективным, чем использование одиночных букв: 33% успешных определений авторства в варианте (в) против 7% в варианте (а). Средний ранг в варианте (в) почти на два с половиной меньше среднего ранга варианта (а). Этот результат, видимо, связан с тем, что одиночные обобщенные грамматические классы слов в отличие от одиночных букв текста несут в себе более специфическую информацию, более точно характеризующую устойчивые структурные характеристики текстов каждого из авторов.

Наименее эффективным оказалось использование <<полных>> грамматических классов словоформ текста (вариант (г)) как в случае их попарного учета, так и поодиночке. Причины этого нуждаются в дополнительном исследовании.

В табл. 3 приведены данные об авторах анализируемых текстов, количестве их текстов, которые подверглись анализу, разбросе объемов текстов этих авторов с указанием минимального, среднего (в скобках) и максимального объемов, эффективности определения авторства во всех четырех вариантах ((а)-(г)) с указанием минимального, среднего (в скобках) и максимального ранга контрольного текста на его истинном авторе.

В экспериментах использовался также материал переводных текстов (С. Лем, И. Хмелевская, Б. Райнов). Любопытно, что результаты распознавания этих текстов не хуже, чем текстов, написанных авторами, у которых родной язык русский (хотя в выборку попали переводы Лема сделанные разными переводчиками).

Таблица 3: Количество и объем использованных текстов по писателям
[(N0) || (п/п)]Писатель[(Кол-во) || текстов] [Объем текстов || (в тыс. букв)] (а)(б) (в)(г)
[(N0) || (п/п)]Писатель[(Кол-во) || текстов] [Объем текстов || (в тыс. букв)] (а)(б) (в)(г)
0О. Авраменко7223,7(279,5)395,10(0,0)00(0,0)00(0,0)010(13,9)22
1А. Больных70,8(185,0)298,80(4,1)240(5,9)371(12,1)794(15,3)75
2К. Булычев163,3(129,5)458,90(6,8)590(6,8)530(9,0)653(16,3)69
3А. Волков95,2(186,8)610,50(20,4)500(26,3)510(12,3)575(23,1)65
4Г. Глазов6184,5(263,7)326,10(0,0)00(0,0)00(0,0)09(13,2)19
5О. Гриневский296,1(127,4)158,60(0,0)00(0,0)00(0,0)00(0,5)1
6Н.В. Гоголь497,7(213,3)334,00(1,0)40(1,5)60(8,0)3214(22,8)42
7Н. Гумилев270,1(70,6)71,00(0,0)00(0,0)00(0,0)00(0,0)0
8Ф.М. Достоевский488,6(175,5)268,90(0,0)01(2,0)30(0,3)110(13,3)18
9М. и С. Дяченко623,3(325,1)553,20(0,0)00(0,2)10(0,0)07(11,5)17
10С. Есенин244,6(131,5)218,40(0,0)00(0,0)00(0,0)00(0,5)1
11А. Етоев62,7(57,9)114,80(1,0)40(4,3)190(2,2)132(3,0)5
12И. Ефремов2256,5(396,5)536,50(0,0)00(0,0)00(0,0)01(2,0)3
13А. Житинский3253,6(793,2)1207,60(0,3)10(0,0)00(9,0)2618(26,3)42
14А. Кабаков569,0(225,5)418,40(0,0)00(0,2)10(2,6)1115(19,2)26
15С. Казменко5132,8(400,5)1148,30(1,2)50(0,8)40(0,2)116(21,8)28
16В. Каплан719,3(91,9)305,20(4,1)250(5,6)240(5,0)239(23,0)40
17А. Кац281,7(461,4)841,00(0,0)00(0,0)00(0,0)01(2,5)4
18В. Климов458,5(107,5)179,90(7,0)150(7,0)200(1,5)63(6,8)9
19Е. Козловский2848,6(868,4)888,20(0,0)00(2,0)415(42,0)6940(56,5)73
20И. Крашевский3380,6(555,2)803,10(0,0)00(0,0)00(0,0)06(8,3)10
21И. Кублицкая2170,2(226,2)282,30(0,0)00(0,0)00(0,0)01(2,0)3
22Л. Кудрявцев4108,3(190,5)348,20(0,3)10(1,5)50(0,0)08(13,5)24
23В. Кунин4296,3(407,9)610,30(0,0)00(2,5)70(3,5)510(15,5)23
24А. Курков717,5(121,0)276,90(3,1)100(11,6)280(1,9)34(11,9)19
25А. Лазаревич411,3(101,3)274,70(14,3)475(20,3)542(11,0)184(9,3)15
26А. Лазарчук6141,4(434,2)786,90(0,0)00(0,8)20(0,0)019(25,5)34
27Ю. Латынина3116,8(970,7)2511,80(3,3)100(13,0)360(0,0)04(15,3)23
28С. Лем811,6(238,6)535,20(0,9)50(1,1)80(5,1)2711(26,5)44
29Н. Леонов3273,1(282,7)295,70(0,0)00(0,0)00(0,0)03(4,0)5
30С. Логинов141,3(153,4)916,20(15,9)364(18,1)370(18,9)4914(35,6)59
31Е. Лукин526,9(144,6)367,90(3,2)150(0,0)00(4,4)198(16,0)39
32Л. и Е. Лукины4105,2(239,9)564,70(0,3)12(3,8)60(0,5)24(12,8)20
33С. Лукьяненко156,0(277,6)542,90(3,0)220(6,9)760(9,1)589(25,4)73
34Н. Маркина293,6(179,8)266,00(0,0)00(0,0)01(2,5)40(1,5)3
35А. Мелихов2457,6(536,4)615,20(0,0)00(2,5)50(0,0)017(17,5)18
36В. Михайлов284,2(169,3)254,50(0,0)00(0,0)00(0,0)01(2,5)4
37А. Молчанов2206,5(302,4)398,30(0,0)00(0,0)00(0,5)14(5,5)7
38В. Набоков6102,0(310,6)599,80(2,0)110(0,8)30(3,0)155(12,7)18
39М. Наумова45,2(161,1)337,80(7,8)310(11,8)470(17,8)694(10,0)17
40Ю. Нестеренко271,1(212,0)352,80(1,0)21(3,5)60(0,0)01(3,5)6
41Ю. Никитин3656,9(681,4)702,20(11,3)340(17,0)510(0,7)15(6,7)8
42С. Павлов2375,6(414,5)453,40(0,0)00(0,5)10(0,0)06(6,5)7
43А.С. Пушкин257,1(113,7)170,30(0,0)00(0,0)00(0,0)00(0,0)0
44Б. Райнов5267,7(363,6)420,30(0,0)00(0,0)00(0,6)312(13,8)15
45Л. Резник279,6(97,8)115,90(0,0)00(0,0)00(0,0)01(1,0)1
46Н. Рерих484,5(305,6)608,70(5,5)220(3,5)140(2,3)90(2,5)9
47Н. Романецкий75,5(203,2)530,60(5,4)210(7,7)200(1,0)415(27,7)45
48А. Ромашов287,7(88,1)88,40(0,0)00(0,0)02(3,0)40(0,0)0
49В. Рыбаков79,7(119,5)366,10(9,0)240(9,0)210(16,4)3615(25,6)41
50М.Е. Салтыков-Щедрин2101,6(170,4)239,10(0,0)00(0,0)00(0,0)01(2,5)4
51Р. Светлов329,2(241,0)425,40(0,0)03(13,3)200(0,7)23(8,7)17
52А. Свиридов413,4(224,0)601,510(27,5)650(11,8)410(11,0)446(26,5)56
53В. Сегаль360,5(132,0)259,70(0,0)00(0,0)00(0,3)11(4,7)8
54К. Серафимов275,3(130,8)186,40(0,0)00(0,0)00(0,0)01(1,0)1
55И. Сергиевская250,7(79,8)108,90(0,0)00(1,0)20(0,0)00(0,5)1
56К. Ситников813,0(66,1)274,30(0,0)00(2,3)180(0,5)43(8,3)22
57С. Снегов3385,8(411,1)438,40(0,0)00(0,0)00(0,0)05(5,0)5
58С.М. Соловьев2159,9(1251,6)2343,30(0,0)00(0,0)00(0,0)00(2,5)5
59А. Степанов683,7(219,6)390,30(0,0)00(0,0)00(0,0)04(5,0)8
60А. Столяров2137,2(241,9)346,70(5,0)109(11,0)130(7,5)151(2,5)4
61А. и Б. Стругацкие3037,1(230,4)579,50(1,9)240(2,5)230(5,9)5415(36,4)79
62А. Стругацкий251,9(101,6)151,30(0,0)00(0,0)00(0,5)11(1,0)1
63Б. Стругацкий2260,7(279,6)298,40(0,0)00(0,0)00(0,0)07(8,0)9
64Е. Тильман3307,8(390,0)464,70(0,0)00(0,0)00(0,0)011(11,3)12
65А. Толстой297,9(113,8)129,70(0,0)00(0,0)00(0,0)00(0,0)0
66Л.Н. Толстой2199,9(712,5)1225,10(0,0)00(0,0)00(0,0)01(1,5)2
67Д. Трускиновская982,6(235,9)478,60(0,8)30(2,7)120(3,8)2813(23,8)53
68А. Тюрин191,3(222,0)832,70(2,3)200(1,2)130(2,6)2524(34,0)55
69Е. Федоров2221,3(667,2)1113,10(0,0)00(0,0)00(0,0)01(1,5)2
70Е. Хаецкая3204,1(309,0)414,31(10,3)2212(31,3)4254(57,0)6228(39,3)54
71Д. Хармс313,9(104,1)185,50(0,0)00(0,0)00(12,0)295(16,7)30
72В. Хлумов4183,3(242,9)395,50(3,8)150(11,3)386(15,3)3826(34,0)46
73И. Хмелевская5203,7(345,7)459,10(0,0)00(0,0)00(0,4)29(12,8)18
74В. Черняк3201,6(373,7)501,00(0,0)00(2,7)80(11,7)352(11,0)25
75А.П. Чехов3247,9(335,3)414,50(0,0)00(0,0)04(13,3)2018(18,7)20
76В. Шинкарев356,2(78,9)100,10(11,7)296(13,3)224(23,7)615(5,7)6
77В. Шукшин266,7(187,7)308,80(0,0)00(0,0)00(0,0)01(2,5)4
78С. Щеглов355,2(103,0)146,10(4,0)120(13,7)410(3,0)92(2,3)3
79А. Щеголев3105,6(318,0)561,70(0,0)00(0,0)00(0,0)012(18,7)32
80В. Югов666,7(149,2)304,30(0,5)20(0,7)20(1,8)108(10,7)18
81В. Ян2507,3(553,9)600,40(0,0)00(0,0)00(0,0)02(2,0)2

5  Заключение

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

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

Другими словами, подсчет частот употреблений пар букв позволяет в некотором виде учесть информацию о словаре, который используется автором, а также, косвенно, информацию о предпочитаемых им грамматических конструкциях. Несмотря на то, что различия в частотах употреблений конкретных пар букв, скорее всего, несущественны, поскольку сходятся к частотам, средним по языку, при увеличении объема текстов (такой эффект был подмечен еще Марковым [3]), <<правдоподобие>>, учитывающее <<общий>> эффект изменения употреблений пар букв позволяет всё же с высокой степенью точности определить истинного автора произведения, что и было показано ранее в работе [1], а в настоящем исследовании подтверждено с помощью перекрестной проверки.

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

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







A  Приложение
Применение алгоритмов сжатия данных
в задаче определения авторства

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

В [1] исследовалась выборка текстов 82 писателей. У каждого писателя был случайно отобран контрольный текст, а остальные тексты использовались в качестве обучающей выборки. После этого определялось авторство контрольного текста, и правильный ответ был получен в 69 случаях. Чтобы получить некоторую оценку того, насколько этот результат хорош в терминах вероятности правильного определения авторства, поставим следующий мысленный эксперимент. Предположим, что у нас имеется некоторый автомат, который при заданных двух текстах выводит 0, если это тексты разных авторов, и 1, если это тексты одного автора, причем вероятности ошибок первого и второго родов составляют некоторое число 0 < p < 1. Рассмотрим применение этого автомата в рамках задачи выбора правильного автора из 82. Тогда этот автомат должен вывести ровно 81 ноль, что отвечает сравнению контрольного текста с обучающими текстами неправильных авторов, и одну единицу, отвечающую сравнению контрольного текста с обучающим текстом истинного автора. Естественно рассматривать все остальные выводы как ошибочные. Тогда, если предположить, что все попарные сравнения независимы, вероятность правильного вывода составляет (1-p)82. При уровне доверия p = 0,05 мы получаем (1-0,05)82» 0,015, уровень p = 0,01 отвечает (1-0,01)82» 0,439, а при p = 0,005 получаем (1-0,005)82» 0,663. Заметим, что 69/82» 0,84 и если мы хотим, чтобы наш гипотетический автомат превзошел по точности метод [1], необходимо потребовать, например, чтобы p = 0,001, и лишь тогда окажется (1-0,001)82» 0,921. Таким образом, уровень правильного определения 69 контрольных текстов при выборе из 82 писателей следует расценивать как чрезвычайно высокий. С определенными оговорками это рассуждение применимо и к результатам основного текста статьи.

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

Дадим теперь <<идеальное>> определение относительной сложности в духе определения колмогоровской сложности (см. [14,15]): относительная сложность 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 авторов. Отберем у каждого автора по контрольному тексту U1, ..., Un. Все остальные тексты у каждого автора объединим в один текст T1, ..., Tn.

Для каждого контрольного текста i авторство определяется следующим образом. Сначала определяется ранг Ri числа C(Ui | Ti) в наборе чисел {C(Ui | T1),ј, C(Ui | Tn)}. Ранги принимают значения от 0 до n-1. Если ранг Ri равен 0, то авторство i-го контрольного текста определено верно. Аналогично [1] можно ввести много различных характеристик точности метода определения авторства. Например:

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

2. Более обобщенную характеристику даетсредний ранг
M = 1
n
 n
е
 i = 1 
 Ri.

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

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

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

Таблица 4: Программы сжатия

ПрограммаАвтор [ Используемые || алгоритмы]
1.7zip версия 2.11Игорь Павлов арифм. кодирование, LZ + арифм. кодирование, PPM
2.arj версия 2.60RAO Inc.LZSS + Хаффман
3.bsa версия 1.9.3Сергей БабичевLZ
4.bzip2Джулиан СьюардБарроуз-Виллер + Хаффман
5.compressSun 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.rarw версия 2.00Евгений Рошальвариант LZ77 + Хаффман
15.rar версия 2.70Евгений Рошальвариант LZ77 + Хаффман
16.rk версия 1.03aМалькольм ТейлорLZ, PPMZ

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

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

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

ПрограммаРанг
 01234і 5M
7zip399323266,43
arj465272205,16
bsa449311245,30
bzip238551 3313,68
compress1211326324,37
dmc364344319,81
gzip504121244,55
ha478133205,60
huff110114425115,37
lzari1754264814,99
lzss1431136020,05
ppm22142134010,39
ppmd546662 225,96
rar58111 217,22
rarw713 2151,44
rk52931 174,20
Цепи Маркова (см. [1])69321 72,35

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

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

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





СПИСОК ЛИТЕРАТУРЫ

[1]
Хмелёв Д.В. Распознавание автора текста с использованием цепей А.А. Маркова//Вестн. МГУ. Сер. 9, Филология. 2000. N02. С.115-126.
[2]
Морозов Н.А. Лингвистические спектры: средство для отличения плагиатов от истинных произведений того или иного известного автора. Стилеметрический этюд// Известия отд. русского языка и словесности Имп.акад.наук. 1915. Т.20, Кн.4.
[3]
Марков А.А. Об одном применении статистического метода//Изв.Имп.акад.наук, Сер. 6. 1916. N04, С.239-242.
[4]
Марков А.А., Пример статистического исследования над текстом "Евгения Онегина", иллюстрирующий связь испытаний в цепь//Изв.Имп.акад.наук, Сер. 6. 1913. N03, С.153-162.
[5]
От Нестора до Фонвизина. Новые методы определения авторства. М.: Издат. группа "Прогресс", 1994.
[6]
Holmes D.I. The Evolution of Stylometry in Humanities Scholarship//Literary and Linguistic Computing. 1998. V. 13. N03. P.111-117.
[7]
Фоменко В.П., Фоменко Т.Г. Авторский инвариант русских литературных текстов//Методы количественного анализа текстов нарративных источников. М.: Ин-т истории СССР, 1983. С.86-109.
[8]
Яглом А.М., Яглом И.М. Вероятность и информация. М.: Наука, 1960.
[9]
Добрушин Р.Л. Математические методы в лингвистике//Математическое просвещение. 1959. Вып.6.
[10]
Зализняк А.А. Грамматический словарь русского языка. М.: Рус. язык, 1977.
[11]
Грамматика современного русского литературного языка. М.: Наука. 1970.
[12]
Русская грамматика. Т.1,2. М.: Наука. 1980.
[13]
Ивченко Г.И., Медведев Ю.И. Математическая статистика. М.: Высш. шк., 1992.
[14]
Li M., Vitányi P. An Introduction to Kolmogorov Complexity and Its Applications. New York: Springer, 1997.
[15]
Колмогоров А.Н. Три подхода к определению понятия <<количество информации>>//Пробл. передачи информ. 1965. Т.1. N01, С.3-11.
[16]
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
[17]
Lempel A., Ziv J. On the Сomplexity of Finite Sequences//IEEE Trans. on Inform. Theory. 1976. V.22. N01. P.75-81.
[18]
Cleary J.G., Witten I.H. Data Compression Using Adaptive Coding and Partial String Matching//IEEE Trans. on Commun. 1984. V.32. N04. P.396-402.
[19]
Cormack G.V., Horspool R.N . Data Compression Using Dynamic Markov Modelling//Computer J. 1987. V.30. N06. P.541-550.

Содержание

1  Введение
2  Предварительная обработка
3  Метод и его перекрестная проверка
4  Описание результатов
5  Заключение
A  Приложение
Применение алгоритмов сжатия данных
в задаче определения авторства

Примечания:

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

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

3Jeff Gilchrist, jeffg@cips.ca

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

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

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

Last modified Sat May 25 21:50:01 BST 2002