16.9. Метод индекса совпадений

Приведём теоретическое обоснование метода индекса совпадений. Пусть алфавит имеет размер $A$ . Пронумеруем его буквы числами от $1$ до $A$ . Пусть заданы вероятности появления каждой буквы:

P = {p_{1}, p_{2}, \dots, p_{A}} .

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

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

X = [X_{1}, X_{2}, \dots, X_{L}]

– случайный текст с распределением

P_{1} = {p_{11}, p_{12}, \dots, p_{1 A}} .

Найдём индекс совпадений

I_{c} (P_{1}),

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

Для пары позиций $(k, j)$ найдём условную вероятность того, что на этих позициях находятся одинаковый символ:

P (X_{k} = X_{j} ∣ (k, j)) = \sum_{i = 1}^{A} p_{1 i}^{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{array}{r} I (P_{1}) = \sum_{1 \leq k < j \leq L} P_{(K, J)} (k, j) \cdot P (X_{k} = X_{j} ∣ (k, j)) = \\ = \sum_{1 \leq k < j \leq L} \frac{2}{L (L - 1)} k_{p_{1}} = k_{p_{1}} . \end{array}

Найдём теперь аналогичную вероятность $I (P_{1}, P_{2})$ для случая, когда последовательность независимых случайных букв может быть представлена в виде

X = [\begin{matrix} X_{1}, \\ Y_{1}, \end{matrix} \begin{matrix} X_{2}, \\ Y_{2}, \end{matrix} \begin{matrix} \dots, \\ \dots, \end{matrix} \begin{matrix} X_{L / 2} \\ Y_{L / 2} \end{matrix}],

где одинаково распределённые случайные буквы в первой строке имеют распределение:

P_{1} = {p_{11}, p_{12}, \dots, p_{1 A}},

а одинаково распределённые случайные буквы во второй строке имеют другое распределение:

P_{2} = {p_{21}, p_{22}, \dots, p_{2 A}} .

В этом случае сумму по всем парам мы разделяем на три суммы: по парам внутри позиций первой строки, по парам внутри позиций второй строки и по парам, в которых первая позиция берётся из первой строки, а вторая – из второй:

\begin{array}{r} I (P_{1}, P_{2}) = \frac{2}{L (L - 1)} \cdot (\sum_{1 \leq k < j \leq L / 2} P (X_{k} = X_{j} ∣ (k, j)) + \\ + \sum_{1 \leq k < j \leq L / 2} P (Y_{k} = Y_{j} ∣ (k, j)) + \sum_{k = 1}^{L / 2} \sum_{j = 1}^{L / 2} P (X_{k} = Y_{j} ∣ (k, j))) = \\ = \frac{2}{L (L - 1)} (\frac{1}{2} \frac{L}{2} (\frac{L}{2} - 1) k_{p_{1}} + \frac{1}{2} \frac{L}{2} (\frac{L}{2} - 1) k_{p_{2}} + {(\frac{L}{2})}^{2} k_{p_{1}, p_{2}}), \end{array}

где обозначено

k_{p_{1}, p_{2}} = \sum_{i = 1}^{A} p_{1, i} p_{2, i} .

В общем случае рассмотрим последовательность, представленную в виде матрицы, состоящей из $m$ строк и $\frac{L}{m}$ столбцов, где

X = [\begin{matrix} X_{1} & X_{2} & \dots & X_{L / m} \\ Y_{1} & Y_{2} & \dots & Y_{L / m} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ Z_{1} & Z_{2} & \dots & Z_{L / m} \end{matrix}] .

Считаем, что одинаково распределённые случайные буквы в первой строке имеют распределение

P_{1} = {p_{11}, p_{12}, \dots, p_{1 A}},

одинаково распределённые случайные буквы во второй строке имеют распределение

P_{2} = {p_{21}, p_{22}, \dots, p_{2 A}}

и т. д., одинаково распределённые случайные буквы $m$ -й строки имеют распределение

P_{m} = {p_{m 1}, p_{m 2}, \dots, p_{m A}} .

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

\begin{array}{r} I (P_{1}, P_{2}, \dots, P_{m}) = \\ = \frac{2}{L (L - 1)} (\frac{L}{2 m} (\frac{L}{m} - 1) k_{p_{1}} + \frac{L}{2 m} (\frac{L}{m} - 1) k_{p_{2}} + \\ + \dots + \frac{L}{2 m} (\frac{L}{m} - 1) k_{p_{m}}) + \\ + \frac{2}{L (L - 1)} ({(\frac{L}{m})}^{2} k_{p_{1}, p_{2}} + {(\frac{L}{m})}^{2} k_{p_{1}, p_{3}} + \dots + {(\frac{L}{m})}^{2} k_{p_{m - 1}, p_{m}}) . \end{array}

Первая сумма содержит $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 \neq j,

получим после несложных выкладок

m = \frac{k_{p} - k_{r}}{I - k_{r} + \frac{k_{p} - I}{L}} .