forked from vlsergey/infosec
-
Notifications
You must be signed in to change notification settings - Fork 0
/
coincide-index_method.tex
106 lines (98 loc) · 7.24 KB
/
coincide-index_method.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
\section{Метод индекса совпадений}
\selectlanguage{russian}
\label{chap:coincide-index}
Приведем теоретическое обоснование метода индекса совпадений. Пусть алфавит имеет размер $A$. Перенумеруем его буквы числами от $1$ до $A$. Пусть заданы вероятности появления каждой буквы
\[ \mathcal{P} = \left\{ {p_1 ,p_2 , \ldots , p_A } \right\}. \]
В простейшей модели языка предполагается, что тексты состоят из последовательности букв, порождаемых источником независимо друг от друга с известным распределением $\mathcal{P}$.
Найдем индекс совпадений для различных предположений относительно распределений букв последовательности. Сначала рассмотрим случай, когда вероятности всех букв одинаковы. Пусть
\[ \mathbf{X} = \left[ X_1, X_2, \dots, X_L \right] \]
случайный текст с распределением
\[ \mathcal{P}_1 = \left\{ p_{11}, p_{12}, \dots, p_{1A} \right\}. \]
Найдем индекс совпадений
\[ I_c(\mathcal{P}_1), \]
то есть, вероятность того, что в случайно выбранной паре позиций находятся одинаковые буквы.
Для пары позиций $(k,j)$ найдем условную вероятность $P \left( X_k = X_j \mid (k,j) \right)$:
\[ P \left( X_k = X_j \mid (k,j) \right) ~=~ \sum\limits_{i=1}^A p_{1i}^2 ~\equiv~ k_{p_1}. \]
Эта вероятность не зависит от выбора пары позиций $(k,j)$.
Так как число различных пар равно $\frac{L(L - 1)}{2}$, то вероятность случайного выбора пары $(k,j)$ равна
\[ P_{(K,J)} (k,j) = \frac{2}{L(L - 1)}. \]
Следовательно,
\[
I(\mathcal{P}_1) ~= \sum \limits_{1 \leq k < j \leq L} P_{(K,J)}(k,j) ~\cdot~ P(X_k = X_j \mid (k,j)) =
\] \[
= \sum \limits_{1 \leq k < j \leq L} \frac{2}{L(L - 1)} k_{p_1} = k_{p_1}.
\]
Найдем теперь аналогичную вероятность $I\left( {\mathcal{P}_1 ,\mathcal{P}_2 } \right)$ для случая, когда последовательность независимых случайных букв может быть представлена в виде
\[
\mathbf{X} = \left[ {\begin{array}{*{20}c}
{X_1 ,} \\
{Y_1 ,} \\
\end{array} \begin{array}{*{20}c}
{X_2 ,} \\
{Y_2 ,} \\
\end{array} \begin{array}{*{20}c}
{ \ldots ,} \\
{ \ldots ,} \\
\end{array} \begin{array}{*{20}c}
{X_{L/2} } \\
{Y_{L/2} } \\
\end{array} } \right],
\]
где одинаково распределенные случайные буквы в первой строке имеют распределение
\[ \mathcal{P}_1 = \left\{ {p_{11} ,p_{12} , \ldots , p_{1A} } \right\}, \]
а одинаково распределенные случайные буквы во второй строке имеют другое распределение
\[ \mathcal{P}_2 = \left\{ {p_{21} ,p_{22} , \ldots , p_{2A} } \right\}. \]
В этом случае сумму по всем парам мы разделяем на три суммы: по парам внутри позиций первой строки, по парам внутри позиций второй строки и по парам, когда первая позиция берется из первой строки, а вторая –- из второй:
{ \small
\[
I(\mathcal{P}_1, \mathcal{P}_2) =
\frac{2}{L(L - 1)} \cdot \left(
\sum \limits_{1 \leq k < j \leq L/2} P( X_k = X_j \mid ( k,j )) ~~ + \right.
\] \[
\left. + \sum\limits_{1 \leq k < j \leq L/2} P(Y_k = Y_j \mid (k,j)) ~~+~~
\sum\limits_{k=1}^{L/2} \sum\limits_{j=1}^{L/2} {P(X_k = Y_j \mid (k,j))} \right) =
\] \[
= \frac{2}{L(L - 1)} \left( \frac{1}{2} \frac{L}{2} \left( \frac{L}{2} - 1 \right) k_{p_1} +
\frac{1}{2} \frac{L}{2} \left( \frac{L}{2} - 1 \right) k_{p_2} +
\left( \frac{L}{2} \right)^2 \sum \limits_{i = 1}^A p_{1,i} p_{2,i} \right) =
\] \[
= \frac{2}{L(L - 1)} \left( \frac{1}{2} \frac{L}{2} \left( \frac{L}{2} - 1 \right) k_{p_1} +
\frac{1}{2} \frac{L}{2} \left( \frac{L}{2} - 1 \right) k_{p_2} +
\left( \frac{L}{2} \right)^2 k_{p_1, p_2} \right),
\] }
где обозначено
\[ k_{p_1, p_2} = \sum\limits_{i=1}^A p_{1,i} p_{2,i}. \]
В общем случае рассмотрим последовательность, представленную в виде матрицы, состоящей из $m$ строк и $\frac{L}{m}$ столбцов, где
\[
{\mathbf X} = \left[ {\begin{array}{*{20}c}
{X_1 } & {X_2 } & \ldots & {X_{L/m} } \\
{Y_1 } & {Y_2 } & \ldots & {Y_{L/m} } \\
\vdots & \vdots & \vdots & \vdots \\
{Z_1 } & {Z_2 } & \ldots & {Z_{L/m} } \\
\end{array}} \right].
\]
Считаем, что одинаково распределенные случайные буквы в первой строке имеют распределение
\[ P_1 = \left\{ {p_{11} ,p_{12} , \ldots , p_{1A} } \right\}, \]
одинаково распределенные случайные буквы во второй строке имеют распределение
\[ P_2 = \left\{ {p_{21} ,p_{22} , \ldots , p_{2A} } \right\} \]
и т.д., одинаково распределенные случайные буквы $m$-й строки имеют распределение
\[ P_m = \left\{ {p_{m1},p_{m2} , \ldots , p_{mA} } \right\}. \]
Для вычисления вероятности того, что в случайно выбранной паре позиций будут одинаковые буквы, выполним суммирование по различным парам внутри строк и по парам между различными строками. Аналогично предыдущему случаю получим
{ \small
\[
I(\mathcal{P}_1, \mathcal{P}_2, \ldots, \mathcal{P}_m ) ~=
\] \[
=~ \frac{2}{L(L - 1)} \left( \frac{1}{2} \frac{L}{m} \left( \frac{L}{m} - 1 \right) k_{p_1} ~+~
\frac{1}{2} \frac{L}{m} \left( \frac{L}{m} - 1 \right) k_{p_2} ~+ \right.
\] \[
+~ \dots ~+~ \left. \frac{1}{2} \frac{L}{m} \left( \frac{L}{m} - 1 \right) k_{p_m} \right) ~+
\] \[
+~ \frac{2}{L(L - 1)} \left( \left( \frac{L}{m} \right)^2 k_{p_1, p_2} +
\left( \frac{L}{m} \right)^2 k_{p_1, p_3} + \dots +
\left( \frac{L}{m} \right)^2 k_{p_{m - 1}, p_m } \right).
\] }
Первая фигурная скобка содержит $m$ слагаемых, вторая -- $ \frac{m(m-1)}{2}$ слагаемых. Полагая
\[ k_{p_1} = k_{p_2} = \dots = k_{p_m} = k_p, \]
\[ k_{p_i p_j } = k_r = \frac{1}{A}, ~ i \ne j, \]
получим после несложных выкладок
\[ m = \frac{k_p - k_r}{I - k_r + \frac{k_p - I}{L}}. \]