Индекс совпадений

Рассмотрим текст, написанный на некотором языке. Алфавит данного языка будем полагать состоящим из ${\displaystyle m}$ символов. Рассмотрим достаточно длинную строку ${\displaystyle {\vec {x}}}$ из ${\displaystyle n}$ символов. Индексом совпадения называют вероятность совпадения двух произвольных символов в строке. Если ${\displaystyle f_{i}}$ — количество ${\displaystyle i}$-го символа алфавита в строке ${\displaystyle {\vec {x}}}$, то индекс совпадения вычисляется по формуле:

${\displaystyle I\left({\vec {x}}\right)=\sum \limits _{i=1}^{m}{\frac {f_{i}\left({f_{i}-1}\right)}{n\left({n-1}\right)}}}$      ${\displaystyle (1)}$

Допустим, строка ${\displaystyle {\vec {x}}}$ является открытым текстом либо получена из него простой перестановкой. В этом случае индекс совпадений удобно выразить через вероятности появления ${\displaystyle i}$-го символа. Обозначим их ${\displaystyle p_{i}}$. Тогда получим следующую формулу:

${\displaystyle I\left({\vec {x}}\right)=\sum \limits _{i=1}^{m}p_{i}^{2}}$      ${\displaystyle (2)}$

Т.к. величины ${\displaystyle p_{i}}$ имеют вполне определённые значения, то для открытого текста индекс совпадений не зависит от его содержания, а зависит только от языка, на котором написан текст. Более того, значения ${\displaystyle p_{i}}$ исследованы и известны, что позволяет рассчитать значения индекса совпадений открытого текста для различных языков.

Наконец, пусть ${\displaystyle {\vec {x}}}$ — случайная строка. Тогда вероятность появления каждого символа равна

${\displaystyle p_{i}={\frac {1}{m}}}$

Используя формулу ${\displaystyle (2)}$, получим:

${\displaystyle I\left({\vec {x}}\right)=\sum _{i=1}^{m}{1 \over m^{2}}={1 \over m}}$      ${\displaystyle (3)}$

Этой формулой можно пользоваться для оценки индекса совпадений полиалфавитного шифра. Для английского языка индекс совпадений полиалфавитного шифра составит 0,03846, для русского (без буквы «ё») — 0,03125.

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

Рассмотрим две строки ${\displaystyle {\vec {x}}}$ и ${\displaystyle {\vec {y}}}$ с длинами ${\displaystyle n}$ и ${\displaystyle n'}$ соответственно. Алфавит, как и прежде, состоит из ${\displaystyle m}$ символов. Взаимным индексом совпадений этих строк называют вероятность того, что символ, случайно выбранный из первой строки, совпадёт со случайно выбранным символом второй строки. Пусть ${\displaystyle f_{i},g_{i}}$ — количество ${\displaystyle i}$-го символа алфавита в первой и второй строках соответственно. Тогда взаимный индекс совпадений будет равен:

${\displaystyle MI\left({{\vec {x}},{\vec {y}}}\right)={\sum \limits _{i=1}^{m}{\frac {f_{i}g_{i}}{nn'}}}}$      ${\displaystyle (4)}$

Доказательство данной формулы аналогично доказательству формулы ${\displaystyle (1)}$.

Практически важным для метода индекса совпадений является частный случай, когда обе строки получены сдвигом алфавита открытого текста. Обозначим ${\displaystyle p_{i}}$ — вероятности появления ${\displaystyle i}$-го символа в строке ${\displaystyle {\vec {x}}}$, ${\displaystyle s}$ — сдвиг алфавита строки ${\displaystyle {\vec {y}}}$ относительно алфавита строки ${\displaystyle {\vec {x}}}$ (влево). Тогда вероятности появление ${\displaystyle i}$-го символа алфавита в строке ${\displaystyle {\vec {y}}}$ равны ${\displaystyle p_{i+s}}$ (используется нумерация алфавита строки ${\displaystyle {\vec {x}}}$). Для взаимного индекса совпадений получаем следующую формулу:

${\displaystyle MI\left({{\vec {x}},{\vec {y}}}\right)=\sum \limits _{i=1}^{m}{p_{i}p_{i+s}}}$      ${\displaystyle (5)}$

Заметим, что т.к. сдвиг циклический, то

${\displaystyle \sum \limits _{i=1}^{m}{p_{i}p_{i+s}}=\sum \limits _{i=1}^{m}{p_{i-s}p_{i}}=\sum \limits _{i=1}^{m}{p_{i+m-s}p_{i}}}$

и взаимный индекс совпадений для сдвигов ${\displaystyle s}$ и ${\displaystyle m-s}$ принимает одно и то же значение.

Ниже приведены значения взаимного индекса совпадений в зависимости от сдвига для русского и английского языков. Значения приведены для сдвигов от ${\displaystyle 0}$ до ${\displaystyle m/2}$. Как упоминалось выше, на основе этих значений взаимный индекс совпадений может быть вычислен для любого сдвига.

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