16.9. Метод индекса совпадений Приведём теоретическое обоснование метода индекса совпадений. Пусть алфавит имеет размер $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) ~=~ \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)}. $$
Следовательно,
$$\begin{eqnarray}
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}.
\end{eqnarray}$$
Найдём теперь аналогичную вероятность $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\}. $$
В этом случае сумму по всем парам мы разделяем на три суммы: по парам внутри позиций первой строки, по парам внутри позиций второй строки и по парам, в которых первая позиция берётся из первой строки, а вторая – из второй:
$$\begin{eqnarray}
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 k_{p_1, p_2} \right),
\end{eqnarray}$$
где обозначено
$$ 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 } & \cdots & {X_{L/m} } \\
{Y_1 } & {Y_2 } & \cdots & {Y_{L/m} } \\
\vdots & \vdots & \ddots & \vdots \\
{Z_1 } & {Z_2 } & \cdots & {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\}. $$
Для вычисления вероятности того, что в случайно выбранной паре позиций будут одинаковые буквы, выполним суммирование по различным парам внутри строк и по парам между различными строками. Аналогично предыдущему случаю получим:
$$\begin{eqnarray}
I(\mathcal{P}_1, \mathcal{P}_2, \ldots, \mathcal{P}_m ) = \\
= \frac{2}{L(L - 1)} \left( \frac{L}{2m} \left( \frac{L}{m} - 1 \right) k_{p_1} + \frac{L}{2m} \left( \frac{L}{m} - 1 \right) k_{p_2} + \right. \\
+ \dots + \left. \frac{L}{2m} \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).
\end{eqnarray}$$
Первая сумма содержит $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}}. $$