Таким образом, трудоёмкость разбиения текста длиной знаков на слова можно оценить величиной:

,

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

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

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



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

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

,

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

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

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

,

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

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

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

Таблица 3. Вычислительные сложности расчёта количественных характеристик текста

№	Характеристика	Вычислительная трудоёмкость
1-3	Набор частот различных N-грамм,	обращение к структуре частот
4-6	Набор частот различных буквенных N-грамм,	проверок символов + обращений к структуре частот
7	Набор частот различных частей речи	Составление списка слов по формуле (9) + обращений к списку слов + обращений к структуре частот
8	Количество предложений заданной длины в словах	Составление списка слов по формуле (9) + сохранений границ предложения + обращений к структуре частот
9	Количество слов заданной длины в символах	Составление списка слов по формуле (9) + обращений к списку слов + обращений к структуре частот
10-11	Количество различных пар частей речи в начале предложения или конце предложения	Составление списка слов по формуле (9) + обращений к списку слов + обращений к структуре частот
12-13	Количество различных троек частей речи в начале предложения или конце предложения	Составление списка слов по формуле (9) + обращений к списку слов + обращений к структуре частот
14	Словарный профиль	Составление списка слов по формуле (9) + обращений к списку слов + обращений к структуре частот
15-16	Относительная частота употребления служебных частей речи, коэффициент словарного состава	Составление списка слов по формуле (9) + обращений к списку слов

Замечание 10. В таблице 3 даны оценки сложности расчёта каждой характеристики при условии, что для заданного текста вычисляется только данная характеристика. В случае вычисления нескольких (всех) характеристик одновременно посимвольная обработка текста выполняется единожды, остальные операции также могут быть выполнены один раз для расчёта нескольких характеристик, поэтому суммарная сложность алгоритма расчёта всех количественных признаков текста значительно меньше суммы трудоёмкостей таблицы 3.

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

,

То есть, для нахождения слова в словаре потребуется не более 23 обращений к словарю.

Замечание 12. В реальной вычислительной среде посимвольная обработка текста осуществляется быстро. С учётом некоторых оптимизаций получение всех характеристик текста длиной до 0.5 млн. знаков в данной работе занимает менее 1 секунды на ЭВМ с частотой центрального процессора 2.6 ГГц.

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

Для расчёта статистики по формуле (3) в настоящей работе используется следующий алгоритм.

1. Двум текстам и ставятся в соответствие два распределения и , каждое из которых представляет собой множество пар вида , где каждая пара есть некоторый j-ый элемент i-го текста, а - его абсолютная частота, - число различных элементов в i-ом тексте;

2. Строится множество - совокупность всех элементов, входящих хотя бы в один из текстов или ;

3. Далее, по формуле (3) осуществляется вычисление статистики .

Сложность такого алгоритма есть сумма следующих величин:

1. операций обращения к структурам частот элементов текстов и для построения множества ;

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

3. арифметических операций при подсчёте статистики .

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

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

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

1. операций обращения к структурам частот элементов текстов и для построения множества ;

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

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

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

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

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

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

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

2. аналогичных операций для текста .

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

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

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

1. Трудоёмкость расчёта количественной характеристики каждого текста;

2. Трудоёмкость расчёта расстояния между текстами заданным в методе способом.

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

,

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

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

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

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

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

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

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

Таблица 4. Эмпирическая точность методов определения авторства

Номер метода	Длина сравниваемых текстов, тысяч знаков
	5	10	20	40	80	120	160	240	320	480
1	0.048	0.078	0.016	0.007	0.023	0.012	0.042	0.07	0.021	0.042
2	0.005	0.063	0.098	0.082	0.010	0.031	0.025	0.085	0.051	0.095
3	0.705	0.746	0.806	0.820	0.866	0.861	0.873	0.917	0.915	0.924
4	0.587	0.616	0.620	0.620	0.672	0.675	0.639	0.630	0.676	0.722
5	0.015	0.083	0.017	0.078	0.084	0.059	0.069	0.081	0.07	0.079
6	0.036	0.069	0.002	0.002	0.094	0.057	0.051	0.047	0.054	0.049
7	0.718	0.769	0.817	0.839	0.883	0.879	0.887	0.923	0.931	0.937
8	0.577	0.610	0.617	0.614	0.649	0.650	0.640	0.633	0.673	0.709
9	0.031	0.003	0.07	0.071	0.023	0.053	0.082	0.059	0.115	0.055
10	0.048	0.059	0.008	0.091	0.063	0.092	0.058	0.036	0.038	0.094
11	0.739	0.793	0.831	0.854	0.890	0.883	0.897	0.938	0.937	0.937
12	0.594	0.614	0.628	0.622	0.655	0.666	0.667	0.667	0.717	0.747
13	0.057	0.09	0.004	0.048	0.03	0.069	0.008	0.066	0.082	0.121
14	0.017	0.022	0.08	0.044	0.017	0.003	0.089	0.012	0.065	0.079
15	0.657	0.703	0.779	0.787	0.842	0.847	0.853	0.889	0.901	0.911
16	0.567	0.584	0.593	0.630	0.660	0.658	0.634	0.600	0.654	0.608
17	0.097	0.023	0.055	0.099	0.027	0.066	0.044	0.029	0.094	0.041
18	0.07	0.027	0.052	0.065	0.031	0.089	0.062	0.078	0.094	0.032
19	0.693	0.743	0.805	0.823	0.863	0.871	0.885	0.904	0.915	0.930
20	0.576	0.591	0.617	0.610	0.693	0.673	0.656	0.650	0.717	0.709
21	0.069	0.003	0.096	0.052	0.02	0.074	0.004	0.06	0.038	0.051
22	0.054	0.074	0.044	0.01	0.083	0.091	0.011	0.074	0.005	0.076
23	0.738	0.788	0.826	0.844	0.874	0.882	0.895	0.921	0.923	0.943
24	0.583	0.599	0.619	0.614	0.671	0.656	0.651	0.680	0.703	0.753
25	0.096	0.064	0.062	0.082	0.049	0.079	0.084	0.059	0.06	0.028
26	0.058	0.099	0.022	0.016	0.015	0.079	0.053	0.045	0.043	0.044
27	0.652	0.686	0.700	0.721	0.725	0.764	0.762	0.767	0.766	0.778
28	0.575	0.570	0.607	0.604	0.617	0.630	0.636	0.585	0.596	0.551
29	0.001	0.059	0.065	0.042	0.095	0.094	0.002	0.029	0.001	0.076
30	0.009	0.046	0.029	0.04	0.081	0.055	0.021	0.007	0.071	0.071
31	0.610	0.644	0.675	0.672	0.705	0.741	0.746	0.786	0.761	0.880
32	0.555	0.548	0.571	0.585	0.627	0.637	0.659	0.635	0.629	0.728
33	0.034	0.020	0.010	0.089	0.085	0.026	0.003	0.089	0.08	0.037
34	0.061	0.047	0.007	0.003	0.011	0.062	0.004	0.081	0.098	0.028
35	0.618	0.637	0.652	0.664	0.703	0.736	0.740	0.744	0.791	0.797
36	0.597	0.619	0.630	0.645	0.638	0.645	0.656	0.680	0.679	0.766
37	0.013	0.055	0.042	0.027	0.019	0.099	0.088	0.062	0.085	0.056
38	0.084	0.007	0.081	0.088	0.012	0.067	0.036	0.067	0.06	0.084
39	0.620	0.595	0.606	0.638	0.691	0.756	0.773	0.797	0.816	0.854
40	0.564	0.555	0.569	0.574	0.595	0.612	0.588	0.581	0.577	0.570
41	0.060	0.073	0.088	0.011	0.014	0.023	0.003	0.021	0.019	0.094
42	0.081	0.048	0.091	0.055	0.044	0.041	0.083	0.037	0.081	0.086
43	0.588	0.601	0.627	0.648	0.699	0.751	0.794	0.818	0.819	0.854
44	0.567	0.528	0.539	0.555	0.555	0.577	0.602	0.573	0.560	0.525
45	0.001	0.033	0.061	0.066	0.035	0.049	0.063	0.023	0.01	0.061
46	0.058	0.004	0.005	0.045	0.064	0.089	0.061	0.063	0.078	0.031
47	0.606	0.598	0.605	0.637	0.683	0.699	0.737	0.759	0.780	0.861
48	0.584	0.549	0.573	0.610	0.583	0.614	0.599	0.570	0.571	0.538
49	0.011	0.09	0.038	0.041	0.099	0.029	0.072	0.034	0.079	0.071
50	0.076	0.073	0.084	0.027	0.076	0.031	0.06	0.083	0.001	0.089
51	0.600	0.614	0.609	0.629	0.711	0.717	0.752	0.778	0.794	0.867
52	0.580	0.535	0.543	0.595	0.564	0.580	0.607	0.583	0.566	0.570
53	0.050	0.087	0.056	0.081	0.092	0.082	0.076	0.039	0.052	0.044
54	0.047	0.001	0.011	0.098	0.091	0.026	0.028	0.003	0.076	0.092
55	0.574	0.585	0.556	0.578	0.600	0.566	0.595	0.575	0.541	0.608
56	0.588	0.619	0.620	0.622	0.628	0.616	0.649	0.658	0.657	0.703
57	0.540	0.534	0.525	0.532	0.561	0.601	0.614	0.606	0.599	0.759
58	0.538	0.531	0.522	0.528	0.556	0.599	0.612	0.603	0.595	0.709

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

Таблица 5. Число опробований каждого метода в зависимости от длин сравниваемых текстов

Длина текста, симв.	Число опробований	Длина текста, симв.	Число опробований
5000	5962	120000	1106
10000	5720	160000	866
20000	4370	240000	532
40000	2636	320000	464
80000	1650	480000	358

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

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

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



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

Как можно увидеть из таблицы 4, наиболее правильно определяют истинного автора текста те методы, которые основаны на сравнении частот N-грамм. Таким методам соответствуют строки 1-24 таблицы 4. Наивысшая точность достигается именно при сравнении этой характеристики.

Различение текстов на основе распределения отдельных частей речи даёт удовлетворительные результаты только при использовании метода, вычисляющего расстояние по формуле (7), и только для текстов длиной свыше 120 тысяч знаков (строка 27 таблицы 4).

Использование распределений длин слов и предложений (строки 29-36 таблицы 4) даёт хорошие результаты только на больших длинах текстов и только при определённых способах сравнения.

Распределение различных пар и троек частей речи в начале и в конце предложения (строки 37-52 таблицы 4) также является авторским инвариантом только на больших длинах текстов.

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

Наконец, числовые характеристики, выраженные долей слов с некоторыми признаками от общего числа слов в тексте (строки 57-58 таблицы 4) имеют некоторую приемлемую точность только для текстов длиной от 480 000 знаков.

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

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

Как видно из таблицы 4, использование критерия (строки 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53) даёт очень низкий процент правильных результатов. Это связано с тем, что в подавляющем числе опробований p-значение оказалось очень низким как для текстов одного автора, так и для текстов разных авторов. Такие результаты позволяют сделать важный вывод.

Замечание 14. При представлении текста в виде выборки значений некоторой количественной характеристики с точки зрения критерия однородности хи-квадрат два любых текста не являются однородными в подавляющем большинстве случаев.

Результаты применения критерия однородности Колмогорова-Смирнова (строки 2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54 таблицы 4) также свидетельствуют в пользу неприменимости критерия для сравнения двух текстов на предмет установления авторства. Однако в данном случае наблюдалась противоположная ситуация: значения статистики не превышали критического как для текстов одного автора, так и для текстов разных авторов.

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

Наиболее эффективным оказывается метод, в основу которого положено вычисление расстояния между текстами по формуле (7). Напомним, что этот метод впервые предложен в работе [10]. Как видно из таблицы 4, метод даёт весьма точные результаты при анализе частот N-грамм (строки 3, 7, 11, 15, 19, 23), при анализе распределения частей речи для текстов длиной от 120 тысяч знаков (строка 27), при анализе распределения слов по длинам на текстах объёма от 160 тысяч знаков (строка 31), а также при анализе распределения пар и троек частей речи в начале и конце предложения для длинных текстов (строки 35, 39, 43, 47).

Применение энтропии для определения авторства текста даёт неплохую точность (свыше 0.7) только при очень длинных текстах (свыше 300 знаков). Однако для небольших текстов точности методов, построенных на её основе, оказывается недостаточно.

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

Результаты сравнений текстов разных длин позволяют сделать вывод, что для подавляющего большинства методов их точность увеличивается с увеличением длины текста. Для некоторых методов эта зависимость прослеживается не так отчётливо, однако, если принять к рассмотрению только те методы, которые можно считать надёжными на основе модели, описанной в параграфе §2.1, то такая зависимость оказывается устойчивой. На рисунке ниже проиллюстрирована зависимость от длины текста точности сравнения распределений N-грамм на основе формулы (7).

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



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

Результатов, представленных в таблице 4, достаточно для построения множества надёжных методов определения авторства в согласии с моделью, описанной в параграфе §2.1. Однако следует исключить из множества все методы, показывающие достаточную точность лишь для больших текстов длиной от 320 знаков. В реальных условиях тексты такой длины (свыше 160 книжных страниц) встречаются значительно реже коротких текстов, а наличие более надёжных методов позволит проводить сравнение с высокой точностью без необходимости добавления других менее точных методов.

Таким образом, структура итогового множества представлена в таблице ниже. Нумерация методов дана в соответствии с таблицами 2 и 4.

Таблица 6. Списки надёжных методов определения авторства для текстов различных длин

Длина текста	Список надёжных методов
5-100 тыс. знаков
100-200 тыс. знаков
>200 тыс. знаков

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

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

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

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

,

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

1. Ошибка I рода: гипотеза отвергнута, хотя она является верной;

2. Ошибка II рода: гипотеза принята, хотя является ошибочной.

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

В таблице ниже приведены оценки вероятности ошибки первого рода (б) для каждого метода множества . Для каждой категории текстов вероятность вычислена как арифметическое среднее значений для всех длин текстов, лежащих в заданном интервале. К примеру, для текстов короче 100 000 знаков брались значения для длин 5, 10, 20, 40 и 80 тысяч знаков из таблицы 4.



Таблица 7. Оценки вероятностей ошибок I рода для надёжных методов сравнения текстов

Тексты до 100 000 знаков
Метод
б	0.211	0.195	0.179	0.246	0.215	0.186
Тексты от 100 000 до 200 000 знаков
Метод
б	0.133	0.117	0.110	0.150	0.122	0.112	0.237	0.236
Тексты длиннее 200 000 знаков
Метод
б	0.081	0.070	0.063	0.100	0.084	0.071	0.230	0.191	0.178	0.170	0.200	0.187

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

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

Таким образом, при использовании данной методики вероятность ошибки второго рода можно оценить следующим образом:

,



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

Обобщённый метод определения авторства задан формулой (2), а более детально принцип его построения изложен в пункте 2.3.8 настоящей работы. Данная глава содержит результаты проверки метода на тестовой выборке.

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

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

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

Таблица 8. Результаты повышения точности определения авторства при помощи метода

	5	10	20	40	80	120	160	240	320	480
	0.871	0.903	0.938	0.947	0.951	0.956	0.963	0.971	0.973	0.975
	0.739	0.793	0.831	0.854	0.890	0.883	0.897	0.938	0.937	0.943
	0.132	0.110	0.107	0.093	0.061	0.074	0.066	0.033	0.036	0.032

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

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

Рис 3. Повышение точности определения авторства при совместном применении нескольких методов множества

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

Определение 14. Задачу определения авторства анонимного текста в случае, когда необходимо определить автора из списка N+1 кандидатов, где один автор является истинным, будем называть задачей определения авторства в случае N альтернатив.

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

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

,

Вероятность события вычисляется по формуле:

,

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

,

Вероятность события оценивается величиной - эмпирически рассчитанной точностью метода для текстов заданной длины .

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

,

Вероятность ошибочно определить автора в этом случае равна . Это означает, что в этом случае автор текста скорее будет определён ошибочно и накладывает довольно сильные ограничения на возможность использования метода , когда число альтернатив больше одной.

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

Таблица 9. Зависимость точности обобщённого метода от числа альтернатив

Число	Длина сравниваемых текстов, тысяч знаков
альт.	5	10	20	40	80	120	160	240	320	480
2	0.729	0.784	0.846	0.862	0.869	0.878	0.891	0.901	0.906	0.911
3	0.623	0.694	0.778	0.800	0.810	0.823	0.842	0.853	0.858	0.861
4	0.532	0.614	0.715	0.743	0.756	0.772	0.795	0.821	0.828	0.832
5	0.454	0.544	0.658	0.690	0.705	0.723	0.730	0.742	0.754	0.757
6	0.388	0.481	0.605	0.640	0.657	0.678	0.683	0.688	0.693	0.701
7	0.331	0.426	0.556	0.595	0.599	0.611	0.623	0.625	0.632	0.639

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

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

Данный параграф содержит заключительные положения и выводы о возможности применения построенного метода определения авторства анонимного текста, а также содержит рекомендации по его использованию:

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

2. Точность метода повышается с ростом объёма сравниваемых текстов.

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

4. Гипотеза об устойчивой однородности выборок N-грамм и других характеристик для текстов одного автора и об отсутствии таковой однородности для текстов разных авторов является неверной, что подтверждается результатами применения статистических критериев и Колмогорова-Смирнова.

5. Определение расстояния между текстами как расстояния между ПФР N-грамм является наиболее точным методом сравнения текстов из рассмотренных в данной работе.

6. Энтропия вероятностной схемы для распределения N-грамм приобретает устойчивость для одного и того же автора при рассмотрении текстов большой длины (приблизительно от 300 тысяч знаков).

7. Для коротких текстов (до 20 000 знаков) значение точности предложенного метода становится неприемлемым (ниже 0.65) при числе альтернативных кандидатов свыше четырёх. Для длинных текстов (свыше 300 тысяч знаков) приемлемое значение точности (не менее 0.65) сохраняется до тех пор, пока число альтернатив не превышает 6.

8. 

Заключение

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

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

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

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



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

1. Андрощук В.В. Судебные автороведческие исследования в криминалистике история возникновения и развития. // Право. Гражданин. Общество. Экономика - М.: Издательский дом ГУ-ВШЭ. - 2010. - C. 4-14

2. Geir Kjetsaa. The Authorship of “The Quiet Don” / Geir Kjetsaa, Sven Gustavsson, Bengt Beckman, Steinar Gil - Slavica Norvegica II. Oslo, 1984.

3. Морозов Н.А. Лингвистические спектры. // Известия АН ОРЯС. 1915. - Т. 10 №4. С. 239-242.

4. Марков А.А. Об одном применении статистического метода. // Известия Имп. Акад. наук. - 1916 - Серия VI. Т.X. №4. - С. 11-17.

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

6. Кукушкина О. В.. Поликарпов А. А.. Хмелeв Д.В.. Определение авторства текста с использованием буквенной и грамматической информации. // Пробл. передачи информ.. 37:2 - 2001. - С. 96-109.

7. Батура Т.В. Методы определения авторского стиля. // Программные системы и вычислительные методы - 2014. - №2. - С. 197-216.

8. Фоменко В.П., Фоменко Т.Г. Авторский инвариант русских литературных текстов. // Фоменко А.Т. Новая хронология Греции: Античность в средневековье. Т. 2. М.: Изд-во МГУ. - 1996. - C. 768-820.

9. Хоменко А.Ю.. Апробация методов математической статистики при атрибуции текста в рамках судебного автороведения. // В мире науки и искусства: вопросы филологии. искусствоведения и культурологии: сб. ст. по матер. XXI междунар. науч.-практ. конф. - Новосибирск: СибАК. - 2013.

10. Ю. Н. Орлов. К.П. Осминин. Определение жанра и автора литературного произведения статистическими методами. // Прикладная Информатика. - 2010. - вып. №2. - C. 95-108.

11. Т.Н. Романченко. Методы атрибуции в автороведческой экспертизе. // Вестник Саратовской государственной юридической академии №2. - 2013. - C. 228-233.

12. Zakaria Elberrichi. Badr Aljohar. N-grams in Texts Categorization. // Scientific Journal of King Faisal University (Basic and Applied Sciences) - Vol. 8 No. 2 1428H. - 2007. - P. 24-39.

13. Moshe Koppel. Yaron Winter. Determining if Two Documents are by the Same Author. // Journal of the Association for Information Science and Technology 65(1). - January 2014. - P. 7-43.

14. Романов А.С. Методика и программный комплекс для идентификации автора неизвестного текста. // Томский государственный университет. - 2010. - C. 26-39.

15. Moshe Koppel. Jonathan Schler. Computational Methods in Authorship Attribution. // Journal of the American Society for Information Science and Technology. - 2008. - P. 45-99.

16. Urszula Staсczyk. Krzysztof A. Cyran. Machine learning approach to authorship attribution of literary texts. // International Journal of applied mathematics and informatics. - 2007. - P. 151-158.

17. J. Diederich. J. Kindermann. E. Leopold. G. Paass. Authorship Attribution with Support Vector Machines. // Applied intelligence. - July 2003.

18. Романов А.С. Методика идентификации автора текста на основе аппарата опорных векторов. // Журнал Доклады Томского государственного университета систем управления и радиоэлектроники. - Ч. 1. - 2008. - No 2(18). - С. 106-109.

19. Larry M. Manevitz. Malik Yousef. One-Class SVMs for Document Classification. // Journal of Machine Learning Research. - 2001. - №2. - P. 139-154.

20. Fatma Howedi. Masnizah Mohd. Text Classification for Authorship Attribution Using Naive Bayes Classifier with Limited Training Data. // Computer Engineering and Intelligence systems. - 2014. - P. 48-56.

21. Sindhu Chandra Sekharan. Recent Approaches on Authorship Attribution Techniques-An Overview. // Conference Paper. - October 2017

22. Smita Nirkhi. Dr.R.V.Dharaska. Comparative study of Authorship Identification Techniques for Cyber Forensics Analysis. // Cornell University. - 2013.

23. Романов А. С. Мещеряков Р. В. Идентификация автора текста с помощью аппарата опорных векторов в случае двух возможных альтернатив. // ГОУ ВПО «Томский государственный университет систем управления и радиоэлектроники». - Томск. 2009.

24. Akiko Aizawa. An information-theoretic perspective of tf-idf measures. // National center for science information systems. - Tokyo, 2003. - P. 146-150.

25. Г.И. Ивченко. Ю. И. Медведев. Введение в математическую статистику. // Издательство «ЛКИ». - Москва 2009. - С. 340-342.

26. Rukhin A., Soto J., Nechvatal J., Smid M., Barker E., Leigh S., Levenson M., Vangel M., Banks D., Heckert A., Dray J., Vo S. A statistical test suite for the validation of random number generators and pseudorandom number generators for cryptographic applications", NIST Special Publication 800-22 Revision 1a, 27 April 2010.

Размещено на Allbest.ru

...