Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Московский институт электроники и математики им. А.Н. Тихонова

Выпускная квалификационная работа

Построение методов определения авторства на основе текстовой информации

по специальности 10.05.01 «Компьютерная безопасность»

Румянцев Д.А. студента образовательной программы специалитета «Компьютерная безопасность»

Руководитель старший преподаватель Миронкин В.О

Соруководитель профессор, д.т.н.

Рожков М.И

Рецензент Технический директор ООО «СэйфТек», к.т.н.

Мельниченко П.А.

Москва 2020



Аннотация

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

This graduation thesis is aimed at development of authorship attribution methods applicable to problem of detecting probable author of text within limited number of candidates. The relevance of the research is relied on wide consumption of authorship attribution applications in linguistics, jurisprudence, forensics and cryptography. Current work describes mathematical models and results of practical testing for different approaches to classification of texts by their authors. The common method of detecting an author is introduced. This method operates the results of most accurate observed approaches to text classification. The mathematical software implementation is developed for suggested common method of authorship attribution.



Оглавление

Введение

Глава 1. Обзор существующих решений

Глава 2. Построение методов сравнения текстовой информации

2.1 Математическая модель

2.2 Выделение количественных характеристик текстов для построения на их основе методов сравнения

2.3 Построение методов сравнения текстов на основе заданных количественных характеристик

2.3.1 Представление текста в виде последовательности реализаций некоторой случайной величины

2.3.2 Использование статистического критерия для сравнения текстов

2.3.3 Применение критерия Колмогорова-Смирнова

2.3.4 Применение выборочной функции распределения и её плотности

2.3.5 Использование энтропии как меры различия текстов

2.3.6 Применение примитивных количественных признаков в алгоритмах сравнения текстов

2.3.7 Итоговый список методов вычисления расстояний между текстами

2.3.8 Принцип построения обобщённого метода определения вероятного автора

Глава 3. Практическая реализация предлагаемой методики

3.1 Подготовка тестовой выборки и морфологического словаря русского языка

3.2 Общий алгоритм проверки предлагаемой методики

3.3 Описание программной реализации проводимого исследования

3.3.1 Общая характеристика программного комплекса

3.3.2 Структура реализуемой программы

3.4 Оценка вычислительной трудоёмкости реализуемых алгоритмов и объёма потребляемой ими памяти

3.4.1 Трудоёмкость подсчёта частот N-грамм

3.4.2 Трудоёмкость разбиения текста на слова

3.4.3 Трудоёмкость подсчёта частот слов с определёнными признаками

3.4.4 Трудоёмкость разбиения текста на предложения

3.4.5 Трудоёмкость подсчёта частот различных последовательностей частей речи в начале и конце предложения

3.4.6 Перечень вычислительных трудоёмкостей для подсчёта каждой характеристики

3.4.7 Трудоёмкость вычисления статистики

3.4.8 Трудоёмкость вычисления статистики для проведения теста Колмогорова-Смирнова

3.4.9 Трудоёмкость вычисления расстояния между плотностями функций распределения

3.4.10 Трудоёмкость вычисления разности значений энтропии двух вероятностных схем

3.4.11 Общий принцип расчёта вычислительной трудоёмкости предлагаемых методов

Глава 4. Результаты проверки предлагаемых методов

4.1 Эмпирически установленные значения точности методов для разных длин текстов

4.2 Анализ полученных результатов

4.2.1 Зависимость точности метода от выбираемой для сравнения количественной характеристики текста

4.2.2 Зависимость точности метода от выбираемого способа сравнения числовых характеристик

4.2.3 Зависимость точности метода от длин сравниваемых текстов

4.3 Определение множества надёжных методов

4.4 Оценка вероятностей ошибок первого и второго рода

Глава 5. Результаты проверки обобщённого метода определения авторства

5.1 Эмпирически установленные значения точности обобщённого метода

5.2 Общие рекомендации к применению построенного метода

Заключение

Список литературы



Введение

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

Наиболее распространённой формой представления информации на цифровых носителях является текст:

· электронные документы;

· статьи, заметки и записи в блогах и социальных сетях;

· электронные издания книг;

· прочие текстовые данные.

Задачи, связанные с установлением авторства, находят своё применение в лингвистике, юриспруденции, криминалистике, различных видах экспертизы:

· установление факта плагиата;

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

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

Так, в частности, вопросы установления авторства конкретного текста призвана решать автороведческая экспертиза.

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

Наиболее мощным инструментом при проведении данной экспертизы является атрибуция текста.

Определение 2. Атрибуция текста - это представление исследуемого текста в виде формального набора признаков, которые можно сравнить с соответствующими признаками других текстов предполагаемых авторов.

Столь широкий спектр применения механизмов защиты информации в части идентификации данных и пользователей определяет актуальность и практическую значимость настоящего исследования.

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

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

Объектом настоящего исследования являются реализованные на практике методы установления авторства, как не зависящие от выбора анализируемого языка, так и специально построенные исключительно для русскоязычных текстов.

Дипломная работа состоит из введения, пяти глав, разделенных на параграфы, и заключения.

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

Глава 2 посвящена описанию математической модели предлагаемого в настоящей дипломной работе алгоритмического решения. Кроме того, глава 2 описывает принцип построения обобщённого метода определения авторства на основе композиции существующих решений. Данный принцип базируется на совместном использовании результатов применения нескольких наиболее точных методов сравнения текстов.

Глава 3 описывает структуру и характеристики разработанного в рамках выполнения настоящей дипломной работы программного обеспечения, используемого для реализации предложенного в главе 2 метода определения авторства. Кроме того, в главе 3 представлена оценка вычислительной сложности и используемой памяти соответствующих методов.

В главе 4 представлены практические результаты исследования предложенного метода, а также классификация исследуемых методов определения авторства по степени надежности.

Наконец, глава 5 описывает результаты исследования обобщённого метода определения авторства, предложенного в главе 2. Кроме того, глава 5 содержит общие выводы о возможности применения предлагаемого метода на практике, а также даёт рекомендации по адаптации метода к различным наборам исходных данных.



Глава 1. Обзор существующих решений

Вплоть до середины XX века для установления возможности авторства над текстом исследовались биография автора, его причастность к описываемым в тексте произведения событиям, индивидуальный авторский стиль - употребление различных фразеологических оборотов, синонимов, речевых форм [1]. Однако, уже в XIX - начале XX вв. в лингвистических исследованиях стал использоваться статистический анализ данных, основанных на численных характеристиках языка [11]. Так в 1915 году в работе [3] Н.А. Морозовым были исследованы распределения частей речи в произведениях различных русских авторов. А уже в 1916 году русский учёный А.А. Марков выступил с критикой Н.А. Морозова, ссылаясь на некачественные статистические свойства исследуемых параметров. Взамен Марковым была выдвинута гипотеза о зависимости вероятности появления текущей буквы от ранее использованных, что позволило в дальнейшем построить Марковскую модель текста. [4].

Современные исследования показывают, что анализ частотности отдельных букв практически не даёт никакой информации об авторе исследуемого текста. Д.В. Хмелёв [5] предложил использовать метод «сравнения текстов», основанный на анализе частоты употребления биграмм и имеющий вероятность успеха, равную 0,84 (вероятность успеха такого метода «частотного анализа» встречаемости отдельных букв всего лишь 0,03).

В [6] изучался метод, основанный на представлении в виде Марковской цепи не только биграмм символов, но и пар грамматических конструкций, например, частей речи. Авторами применён метод аналогичный [5] к таким единицам анализа, как пары грамматических классов слов (относительные, качественные и притяжательные прилагательные, одушевлённые и неодушевлённые существительные и др.). Однако вероятность успеха такой модификации составила всего лишь 0,04.

В [8] вводится понятие авторского инварианта.

Определение 3. Авторским инвариантом называется количественная характеристика текста, однозначно характеризующая некую группу авторов и заметно отличающаяся для других групп.

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

Большую роль в развитии настоящей проблематики играют результаты, определяющие границы применения методов. В работе [9] показано, что методика атрибуции текстов, основанная на анализе распределения конкретных лексем (некоторых местоимений, качественных прилагательных и других лексем, неявно характеризующих отношение автора к действительности) работает только в условиях большого набора параметров.

Крайне важными являются выводы, полученные в [10]. Авторы данной работы предложили отказаться от рассмотрения вероятностей появления в тексте отдельных букв и биграмм как достоверных авторских инвариантов. Вместо этого они рассмотрели способ вычисления расстояния между распределениями букв и биграмм. Определив понятие расстояния между эмпирическими функциями распределения, авторы построили метод сравнения текстов, который при анализе распределения биграмм обеспечил 95% точности для определения авторства и 85% точности при определении жанра.

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

Определение 4. мера - произведение частоты употребления слова (term frequency) в документе на обратную частоту документа в выборке (inverse document frequency).

Таким образом, мера определяет «важность» некоторого слова во всей выборке документов. Введя оптимальный способ вычисления расстояния между векторами значений 4-грамм и определив порог, при котором два текста считаются написанными одним человеком, авторам работы [13] удалось достичь 75% точности метода.

В работе [2] предложено несколько методов сравнения текстов для решения проблемы спорного авторства над романом «Тихий Дон». Данные методы основаны на сравнении распределений частей речи в начале и в конце предложения, распределений предложений и слов по длинам. Такие методы интересны для анализа тем, что были применены для решения конкретной задачи, в то время как в открытых источниках отсутствуют исследования, проверяющие точность данных подходов на большой выборке.

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

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

Для классификации документов по жанрам, авторам, времени создания и другим признакам широкое распространение получили методы, основанные на использовании машины опорных векторов (SVM), на применении Байесовского классификатора, деревьев решений и методе ближайших соседей [14], [15].

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

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

Замечание 2. Подобный подход на сегодняшний день является одним из самых популярных в автороведческой экспертизе и был опробован во множестве исследований [21, 22]. Однако он подразумевает наличие значительного объёма памяти и вычислительных ресурсов компьютера.

Другим достаточно эффективным и более легковесным алгоритмом классификации текстов является наивный Байесовский классификатор (NBC), основанный на применении формулы Байеса [21]. Так, например, в работе [20] показано, что применение NBC для очень коротких текстов (от 290 до 800 слов) даёт лучшие результаты классификации по сравнению с SVM. В свою очередь применение наивного Байесовского классификатора к векторам, состоящим из частот отдельных слов, позволяет достичь вероятности верного установления авторства, равной 0,96, в то время как при анализе векторов частот 3-грамм и 4-грамм NBC даёт 93% правильных результатов.

Наряду с указанными подходами для создания классификаторов активно используются нейронные сети. В работе [16] для разделения двух классов текстов был применён многослойный персептрон (вид нейронной сети), гарантирующий успех с вероятностью 0,95.

Среди существующих программных анализаторов следует выделить следующие.

«Лингвоанализатор», использующий аппарат, основанный на энтропийных характеристиках текста [24], позволяет загружать текст и сравнивать его с имеющейся базой авторов. Результатом его работы является совокупность не более чем из трех предполагаемых кандидатов. Однако параметры данного классификатора строго не описаны.

Программный комплекс «Атрибутор» позволяет загрузить некоторый текст и сравнить его с имеющейся базой романов 103 писателей. В случае отсутствия автора искомого текста в базе предлагается наиболее близкий автор из имеющихся [25].

В [14] дано описание программного комплекса «Авторовед», реализующего механизм SVM для проведения авторской атрибуции. Однако получить свободный доступ к данному программному обеспечению не представляется возможным.

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

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

Результаты настоящей дипломной работы позволяют получить обоснованные ответы на эти вопросы.



Глава 2. Построение методов сравнения текстовой информации

В настоящей главе описана методика сравнения различных количественных признаков текстов, на основе которой составляется перечень наиболее точных методов определения авторства.

2.1 Математическая модель

Пусть задан список } авторов, для каждого из которых заданы множества написанных ими текстов. А именно, через - обозначим множество текстов, написанных автором .

Совокупность образует выборку из текстов, для которых априори известны их авторы.

Требуется построить множество функций , где

,

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

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

Очевидно, что использование таких методов для определения возможного автора текста не приемлемо, поэтому разобьём всё множество построенных методов на два класса: надёжные и ненадёжные методы сравнения текстов.

Для каждого метода проведём серию опробований следующего вида. Случайным образом выберем условно анонимный текст . Далее, случайным образом выберем два текста , такие, что тексты и написаны неким автором , а текст - автором . Далее вычислим расстояния и между текстами , и , соответственно. Если , то будем считать, что метод отработал корректно.

Затем построим множество результатов работы каждого метода:

.

Здесь - доля корректных срабатываний метода от общего числа опробований метода. Введём некоторое - пороговое значение, при помощи которого поделим методы из множества на два подмножества:

,

,

Определение 5. Подмножество назовём классом надёжных методов сравнения текстов, а подмножество - классом ненадёжных методов сравнения текстов.

И, наконец, построим функцию определения авторства, имеющую вид:



,

Здесь - последовательность из текстов и их авторов (), а ? текст, автора которого нужно определить. Результат работы функции - имя наиболее вероятного автора текста - элемент множества . При этом, в своей внутренней реализации функция должна при помощи определённого алгоритма использовать результаты применения методов множества к парам текстов , ,…,.

2.2 Выделение количественных характеристик текстов для построения на их основе методов сравнения

Для того чтобы построить множество методов сравнения текстов, необходимо определить два параметра для каждого метода: количественную характеристику текста и способ вычисления на её основе расстояния между двумя текстами.

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

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

Напомним некоторые определения и понятия, используемые в настоящей работе.

Определение 6. N-грамма - последовательность из любых N символов текста, расположенных друг за другом.

Далее будем проводить подсчёт количества различных биграмм, триграмм, а также 4-грамм в каждом тексте, так как сравнение текстов на основе этой характеристики даёт довольно точные результаты. Во многих исследованиях, в частности, в работках [5, 6, 10, 12, 13, 18, 20] представлены различные методы определения авторства, оперирующие различными способами сравнения частот N-грамм.

Определение 7. Буквенная N-грамма ? последовательность из любых N подряд идущих в тексте букв русского алфавита, среди которых также могут быть символы «-» (дефис) и «_» (пробел), если они выступают в роли разделителя простых слов в составе сложного.

В работе [12] показаны весьма точные результаты сравнений текстов на основе подсчёта частот N-грамм, входящих в состав слов, то есть соответствующих определению 7. В свою очередь, распределение частот таких N-грамм отражает стиль письма автора, его словарный запас.

Определение 8. Словоформой называется слово, представленное в тексте в одной конкретной грамматической форме.

Определение 9. Лексема ? слово, рассматриваемое как единица словарного состава языка в совокупности всех его конкретных грамматических форм (словоформ).

Определение 10. Коэффициент словарного состава - отношение числа различных лексем в тексте к общему числу слов в тексте.

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

Определение 11. Словарным профилем текста называется совокупность пар вида , где - абсолютная частота употребления слова в тексте, - число слов с заданной частотой.

Определения 8-11 являются общепринятыми терминами в лингвистике и даны в работе [2].

На основе представленных определений сформулируем список количественных характеристик, которые войдут в основу построения множества методов сравнения текстов.

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

Таблица 1. Перечень количественных характеристик текста

№	Характеристика	Использовано в работах
1	Набор частот различных биграмм	[5, 6, 10, 12, 18, 20]
2	Набор частот различных триграмм	[12, 18, 20]
3	Набор частот различных 4-грамм	[12, 13, 20]
4	Набор частот различных буквенных биграмм	[20]
5	Набор частот различных буквенных триграмм	[20]
6	Набор частот различных буквенных 4-грамм	[20]
7	Набор частот различных частей речи	[2]
8	Количество слов заданной длины в символах	[2]
9	Количество предложений заданной длины в словах	[2]
10	Количество различных пар частей речи в начале предложения	[2]
11	Количество различных пар частей речи в конце предложения	[2]
12	Количество различных троек частей речи в начале предложения	[2]
13	Количество различных троек частей речи в конце предложения	[2]
14	Словарный профиль	[2]
15	Относительная частота употребления служебных частей речи	[8]
16	Коэффициент словарного состава	[2]

В данный список не вошли некоторые характеристики, для которых было установлено, что они не могут являться авторскими инвариантами. В частности, в работе [5] показано, что частота употребления отдельных символов никак не характеризует конкретного автора. В работе [8] представлено доказательство того, что средняя длина слова, средняя длина предложения и частота употребления отдельных частей речи с ростом объёмов выборки становятся очень близкими для всех текстов и не позволяют разделять тексты на разные классы.

Тем не менее, распределение слов и предложений по длинам может точнее характеризовать автора и поэтому будет использовано при анализе в данной работе.

2.3 Построение методов сравнения текстов на основе заданных количественных характеристик

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

2.3.1 Представление текста в виде последовательности реализаций некоторой случайной величины

Рассмотрим первую характеристику из таблицы 1 - наборы частот различных биграмм символов.

Представим исследуемый текст в виде последовательности , где - последовательность из двух подряд идущих символов, . Пусть - множество всех возможных в русском языке пар подряд идущих символов.

Определим для каждого элемента множества частоту его встречаемости в последовательности .

Множеству поставим в соответствие множество относительных частот элементов в тексте :

,

и рассмотрим эксперимент, заключающийся в случайном выборе биграммы из текста .

В этом случае множество элементарных исходов эксперимента , а вероятность каждого исхода согласно классическому определению вероятности задается равенством .

Таким образом, вероятностная модель эксперимента принимает вид , где ? ? сигма-алгебра событий, а - введённая нами вероятностная мера. При этом последовательность биграмм текста есть последовательность независимых одинаково распределённых случайных величин , где случайная величина о определена как .

Определённая для каждого текста случайная величина о подчиняется некоторому закону распределения. Становится естественным представить процедуру сравнения текстов на основе частот встречаемости биграмм как процедуру сравнения распределений случайной величины о.

Замечание 4. Аналогичным образом строится вероятностное пространство и определяется случайная величина о для характеристик 2-14 таблицы 1.

2.3.2 Использование статистического критерия для сравнения текстов

В современной статистике одним из распространённых критериев проверки гипотезы того, что набор случайных величин подчиняется одному закону распределения, является критерий однородности [27]. Рассмотрим применение данного критерия для сравнения распределений биграмм двух текстов. Для остальных характеристик данный критерий будет применяться аналогичным образом.

Пусть заданы два текста длиной и символов соответственно. Тогда каждый текст является последовательностью из и биграмм соответственно. Такие последовательности представляют собой реализацию и независимых одинаково распределённых дискретных случайных величин. Закон распределения количества биграмм для каждого текста определяется относительной частотностью этих биграмм в тексте.

Пусть - множество различных биграмм в тексте , а - множество различных биграмм в тексте . Построим множество - множество всех различных биграмм, присутствующих в любом из текстов. Далее построим множество абсолютных частот каждой биграммы для обоих текстов: - множество частот всех биграмм в тексте , - множество частот соответствующих биграмм в тексте .

Статистика:

,

при больших имеет распределение с степенями свободы [27].

Обозначим за гипотезу, заключающуюся в том, что распределение биграмм в обоих текстах подчиняется одному закону распределения. Для проверки гипотезы применим критерий на основе p-значений, активно используемый, например, в статистическом пакете NIST STS [28] для проверки качества генераторов случайных чисел.

Согласно данному критерию, для уровня значимости 0.01 гипотеза принимается с вероятностью 99%, если p-значение превышает 0.01, в противном случае с вероятностью 99% гипотеза отвергается. При этом, если случайная величина распределена по закону распределения с степенями свободы, то p-значение вычисляется по формуле:

,

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

На основе описанного выше построим следующую функцию определения расстояния между двумя текстами:

,

Здесь - распределение биграмм соответственно в текстах и . Таким образом, мы полагаем равным нулю расстояние между двумя текстами, если распределение биграмм в них подчиняется одному закону распределения и бесконечности в противном случае.

Замечание 5. Представленный способ вычисления расстояния между текстами аналогично можно построить на основе других распределений, представленных в таблице 1.

2.3.3 Применение критерия Колмогорова-Смирнова

Ещё одним критерием проверки гипотезы об однородности двух распределений является критерий Колмогорова-Смирнова [27].

Пусть для выборок и объёмов и соответственно известны эмпирические функции распределения и . Статистика критерия строится следующим образом:



,

Гипотеза об однородности двух выборок принимается при условии:

,

Величина может быть определена по таблице критических значений для необходимого уровня значимости б.

На основе критерия Колмогорова-Смирнова возможно построить метод определения расстояния между двумя текстами для каждой из характеристик 1-14 таблицы 1 следующим образом:

,

Здесь - распределение для заданной количественной характеристики соответственно в текстах и .

2.3.4 Применение выборочной функции распределения и её плотности

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

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

,

Таким образом, формула (7) определяет расстояние между двумя плотностями выборочных функций распределения (далее - ПФР) Подробное доказательство корректности вычисления расстояния по формуле (7) представлено в работе [10].

Аналогичным образом можно вычислить расстояние между текстами, опираясь на распределение других количественных характеристик таблицы 1.

2.3.5 Использование энтропии как меры различия текстов

В работах [12, 20] энтропия текста использовалась для построения методов классификации текста при помощи обучающей выборки, а в программном комплексе [24] энтропия текста применяется в качестве авторского инварианта и позволяет выбрать наиболее вероятного автора анонимного текста из заранее подготовленной базы.

Определение 12. Энтропией Шеннона вероятностной схемы называется величина

,

где - вероятность i-ого исхода из всех возможных исходов вероятностной схемы.

Построение вероятностной модели текста на основе частот встречаемости N-грамм, отдельных частей речи, слов заданной длины и других количественных признаков позволяет вычислить расстояние между текстами как модуль разности значений энтропии каждого текста:

.

Таким образом, описано 4 метода вычисления расстояния между двумя текстами на основе признаков, представимых в виде распределений некоторых значений.

2.3.6 Применение примитивных количественных признаков в алгоритмах сравнения текстов

Характеристики текста «доля служебных слов» и «коэффициент словарного состава» выражаются рациональным числом, поэтому расстояние между текстами на основе этих данных может быть вычислено как модуль разности соответствующих значений признаков для первого и второго текста:

.

2.3.7 Итоговый список методов вычисления расстояний между текстами

Таблица 1 включает в себя 14 характеристик текста, каждая из которых представлена распределением некоторого количественного признака. В разделах 2.3.2 - 2.3.5. настоящей работы предложено 4 способа определения меры различия таких характеристик. Применяя каждый из способов ко всем характеристикам, можно получить 56 методов сравнения текстов.

Остальные две характеристики текста, представляющие собой значение относительной частоты в тексте слов с некоторыми признаками, сравниваются единственным образом - модулем разности значений - и задают ещё два способа сравнения текстов.

Полный перечень методов сравнения текстов, которые в рамках настоящей работы опробуются на тестовой выборке, приведён в таблице ниже.



Таблица 2. Методы вычисления расстояния между двумя текстами одинаковой длины

Метод	Характеристика текста	Способ сравнения
	Набор частот биграмм
		Колмогоров-Смирнов
		Расстояние между ПФР
		Энтропия
	Набор частот триграмм
		Колмогоров-Смирнов
		Расстояние между ПФР
		Энтропия
	Набор частот 4-грамм
		Колмогоров-Смирнов
		Расстояние между ПФР
		Энтропия
	Набор частот буквенных биграмм
		Колмогоров-Смирнов
		Расстояние между ПФР
		Энтропия
	Набор частот буквенных триграмм
		Колмогоров-Смирнов
		Расстояние между ПФР
		Энтропия
	Набор частот буквенных 4-грамм
		Колмогоров-Смирнов
		Расстояние между ПФР
		Энтропия
	Набор частот различных частей речи
		Колмогоров-Смирнов
		Расстояние между ПФР
		Энтропия
	Количество слов заданной длины в символах
		Колмогоров-Смирнов
		Расстояние между ПФР
		Энтропия
	Количество предложений заданной длины в словах
		Колмогоров-Смирнов
		Расстояние между ПФР
		Энтропия
	Количество различных пар частей речи в начале предложения
		Колмогоров-Смирнов
		Расстояние между ПФР
		Энтропия
	Количество различных пар частей речи в конце предложения
		Колмогоров-Смирнов
		Расстояние между ПФР
		Энтропия
	Количество различных троек частей речи в начале предложения
		Колмогоров-Смирнов
		Расстояние между ПФР
		Энтропия
	Количество различных троек частей речи в конце предложения
		Колмогоров-Смирнов
		Расстояние между ПФР
		Энтропия
	Словарный профиль текста
		Колмогоров-Смирнов
		Расстояние между ПФР
		Энтропия
	Относительная частота употребления служебных частей речи	Модуль разности значений
	Коэффициент словарного состава	Модуль разности значений

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

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



2.3.8 Принцип построения обобщённого метода определения вероятного автора

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

Пусть для заданных текстов из формулы (2) определено множество надёжных методов сравнения

,

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

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

Чем больше индекс текста в последовательности, тем меньше расстояние между данным текстом и анонимным текстом с точки зрения метода .

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

Использование весов при подсчёте суммы индексов позволяет повысить точность результирующего метода за счёт минимизации количества ситуаций, в которых несколько текстов будут иметь одинаковую сумму индексов.



Глава 3. Практическая реализация предлагаемой методики

Предложенная в главе 2 методика поиска оптимального метода определения авторства может быть полностью автоматизирована. Эта глава посвящена описанию предлагаемой программной реализации вышеизложенной методики, а также описанию процедуры проведения анализа.

3.1 Подготовка тестовой выборки и морфологического словаря русского языка

Для проведения серии экспериментов над предлагаемыми методами была подготовлена выборка объёмом 800 художественных произведений 140 различных авторов XX и XXI века.

Замечание 7. Анализируемые тексты были выбраны из открытой бесплатной онлайн-библиотеки lib.ru. В выборку вошли только произведения русских писателей. Переводы иностранных текстов на русский язык в выборку намеренно не добавлялись.

Над всей выборкой была произведена обработка, в результате которой были удалены лишние данные (аннотации издательства, сведения об авторе, предисловия и т.д.).

Все произведения сохранены в кодировке Windows-1251 в виде простого текста. Минимальная длина текста в выборке составляет около 5 тысяч символов, максимальная - порядка 1,6 млн. символов. Основную часть выборки составляют тексты длиной от 10 до 160 тысяч знаков.

Для корректного определения границ слова и обнаружения составных слов, в которых простые слова разделяются пробелами, необходимо использование морфологического словаря. Кроме того, использование морфологического словаря требуется для правильного определения части речи слова.

В данной работе был использован морфологический словарь М. Хагена, содержащий более 173 тысяч лемм и свыше 4,8 млн. словоформ.

Таким образом, представление текста в виде последовательности слов, реализуется автоматизированным алгоритмом на основе данного словаря.

3.2 Общий алгоритм проверки предлагаемой методики

Для построения класса надёжных методов сравнения текстов вся выборка разбивается на части различной длины (с целью проверить исследуемые методы на предмет возможности их применения для текстов разного объёма).

Алгоритм проверки предлагаемой методики выглядит следующим образом:

1. Задаётся множество пороговых длин текстов (в символах):

,

,

2. Для каждого значения формируется выборка из текстов , где - множество всех текстов генеральной выборки, а - множество текстов длины не менее .

3. Для каждого текста из выборки выделяется отрезок длиной , и для этого отрезка подсчитываются характеристики 1-16 таблицы 1.

4. Для каждой длины случайным образом сформируется список из троек текстов так, чтобы для любых двух троек из списка в них было не более одного одинакового текста. Это позволит избежать повторных попарных сравнений, влияющих на достоверность результатов. Число тем больше, чем больше количество текстов с длиной не менее . Значение определяется в практической реализации алгоритма, как некоторое число, после которого не удаётся за фиксированное количество попыток случайным образом выбрать такую тройку текстов, которой не было выбрано ранее.

5. Для каждой длины для каждого элемента множества исследуемых методов строится соответствующее множество точностей по методике, описанной в параграфе §2.1. Каждый метод опробуется на всех тройках текстов из выборки способом, описанным в параграфе §2.1. Для методов, использующих критерий однородности Колмогорова-Смирнова, выбирается уровень значимости .

6. Введя пороговое значение точности для текстов длиной или (коротких текстов) и для текстов длиной более , определяется класс надёжных методов сравнения текстов для заданной длины .

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

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

3.3 Описание программной реализации проводимого исследования

В данном параграфе приведены общие сведения, описывающие особенности программной реализации предложенного в параграфе §3.2 алгоритма.

3.3.1 Общая характеристика программного комплекса

Описанный в параграфе §3.2 алгоритм был реализован на языке C++ в совместимости со стандартом C++17.

Замечание 8. Компиляция и запуск исходного кода производились на компьютере под управлением ОС Linux Mint 19, однако исходный код программы может быть скомпилирован для любой операционной системы и архитектуры процессора при наличии соответствующего компилятора.

Реализованный программный комплекс работает под управлением консоли и не использует элементы графического интерфейса с целью получения максимального быстродействия и возможности запуска на серверах и кластерах с удалённым управлением.

Все анализируемые тексты представлены в однобайтовой кодировке Windows-1251 и обрабатываются как последовательности байтов, сторонние библиотеки для осуществления лингвистического анализа не используются. Это сделано для повышения скорости обработки текстов при анализе.

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

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

Таким образом, программный комплекс спроектирован так, чтобы все вычислительные операции происходили максимально быстро.

3.3.2 Структура реализуемой программы

Исходный код программы написан в виде объектно-ориентированной парадигмы программирования и поделён на несколько пространств имён, представляющих различные компоненты системы:

1. Корневое пространство имён ta включает в себя весь код по анализу текстов.

2. Пространство имён ta/utils включает в себя служебные компоненты для ведения журнала событий, форматирования данных и прочих вспомогательных операций.

3. Пространство имён ta/grammar описывает грамматику русского языка и включает классы word и text, описывающие свойства слова и текста как единиц русской грамматики.

4. Пространство имён ta/tools включает инструменты словаря и анализатора текстов, описываемые классами dictionary и analysis соответственно. Класс analysis содержит всю основную логику работы программного комплекса.

Общая структура основных логических компонентов программы представлена на рисунке 1.

Рис. 1. Основные логические компоненты программы

3.4 Оценка вычислительной трудоёмкости реализуемых алгоритмов и объёма потребляемой ими памяти

Для осуществления процедуры анализа, описанной в параграфе §3.2, проводится ряд математических вычислений и шагов по обработке данных. В данном параграфе приведена оценка вычислительной трудоёмкости различных этапов анализа.

Общая последовательность действий при сравнении двух текстов любым из методов, представленных в таблице 2, включает:

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

2. Вычисление характеристики для каждого текста, на которую опирается данный метод сравнения;

3. Сравнение текстов при помощи данного метода.

Сложность первой стадии одинакова при сравнении текстов любым методом, и её можно считать некоторой константной сложностью подготовительного этапа.

Сложность второй стадии зависит от рассматриваемой характеристики текста. Ниже описаны особенности вычислительной сложности нахождения различных количественных признаков текста.

3.4.1 Трудоёмкость подсчёта частот N-грамм

Текст длиной символов содержит N-грамм. При этом для подсчёта и хранения частот некоторых элементов в прикладных программах, как правило, используется структура данных, называемая отображением вида . В языке C++ такой структурой является контейнер std::map. Сложность заполнения такой структуры можно оценить как операций обращения к структуре, где за одно обращение либо увеличивается число вхождений ранее добавленной N-граммы, либо осуществляется вставка новой N-граммы с начальной частотой, равной единице.

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

,

где первое слагаемое - число операций проверки принадлежности знака допустимому набору, а второе слагаемое - количество обращений к структуре, содержащей информацию о частотах.

Для хранения N-граммы (при и её частоты используется два 4-байтовых значения, поэтому общий объём памяти, занимаемой структурой частот можно оценить величиной (в байтах):

,

где 50 обозначает количество различных символов в тексте, включая 33 буквы алфавита (регистр не различим), и знаки препинания. Для буквенных N-грамм величина не превосходит значения , где 35 - это число букв в алфавите с учётом пробела и дефиса, которые могут входить в состав слова. Замечание 9. На практике далеко не все буквосочетания возможны в русском языке, и далеко не все грамматически корректные N-граммы присутствуют в одном и том же тексте, поэтому величина меньше величины (или буквенных N-грамм) в несколько десятков раз.

3.4.2 Трудоёмкость разбиения текста на слова

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

...