Автокорреляция (слова)

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

Определение

В этой статье A — алфавит , а $w=w_{1}\dots w_{n}$ слово на A длины n . Автокорреляция $w$ можно определить соотношение как $w$ с самим собой. Однако ниже мы переопределим это понятие.

Вектор автокорреляции

Вектор автокорреляции $w$ является $c=(c_{0},\dots ,c_{n-1})$ , с $c_{i}$ равно 1, если префикс длины $n-i$ равен суффиксу длины $n-i$ , и с $c_{i}$ в противном случае будет 0. То есть $c_{i}$ указывает, есть ли $w_{i+1}\dots w_{n}=w_{1}\dots w_{n-i}$ .

Например, вектор автокорреляции $aaa$ является $(1,1,1)$ поскольку, очевидно, для $i$ равны 0, 1 или 2, префикс длины $n-i$ равен суффиксу длины $n-i$ . Вектор автокорреляции $abb$ является $(1,0,0)$ поскольку никакой строгий префикс не равен строгому суффиксу. Наконец, вектор автокорреляции $aabbaa$ равно 100011, как показано в следующей таблице:

а	а	б	б	а	а
а	а	б	б	а	а						1
	а	а	б	б	а	а					0
		а	а	б	б	а	а				0
			а	а	б	б	а	а			0
				а	а	б	б	а	а		1
					а	а	б	б	а	а	1

Обратите внимание, что $c_{0}$ всегда равен 1, поскольку префикс и суффикс длины $n$ оба равны слову $w$ . Сходным образом, $c_{n-1}$ равно 1 тогда и только тогда, когда первая и последняя буквы совпадают.

Автокорреляционный полином

Автокорреляционный полином $w$ определяется как $c(z)=c_{0}z^{0}+\dots +c_{n-1}z^{n-1}$ . Это многочлен степени не более $n-1$ .

Например, автокорреляционный полином $aaa$ является $1+z+z^{2}$ и автокорреляционный полином $abb$ является $1$ . Наконец, автокорреляционный полином $aabbaa$ является $1+z^{4}+z^{5}$ .

Свойство

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

Первое появление слова в случайной строке

Предположим, вы выбрали бесконечную последовательность $s$ писем $A$ , случайно, каждая буква с вероятностью ${\frac {1}{|A|}}$ , где $|A|$ это количество букв $A$ . Давайте позвоним $E$ ожидание первого появления ? $m$ в $s$ ? . Затем $E$ равно $|A|^{n}c\left({\frac {1}{|A|}}\right)$ . То есть каждое подслово $v$ из $w$ который является одновременно префиксом и суффиксом, приводит к получению среднего значения первого вхождения $w$ произойти $|A|^{|v|}$ письма позже. Здесь $|v|$ длина v.

Например, над двоичным алфавитом $A=\{a,b\}$ , первое появление $aa$ находится на позиции $2^{2}(1+{\frac {1}{2}})=6$ в то время как среднее первое появление $ab$ находится на позиции $2^{2}(1)=4$ . Интуитивно тот факт, что первое появление $aa$ позже, чем первое появление $ab$ можно объяснить двумя способами:

Мы можем рассмотреть для каждой позиции $p$ ${\ displaystyle p}$ , какие требования к $w$ $ш$ первое появление на $p$ ${\ displaystyle p}$ .
- Первое появление $ab$ в обоих случаях может находиться в позиции 1 только одним способом. Если $s$ начинается с $w$ . Это имеет вероятность ${\frac {1}{4}}$ для обоих рассматриваемых значений $w$ .
- Первое появление $ab$ находится в позиции 2, если префикс $s$ длины 3 $aab$ или есть $bab$ . Однако первое появление $aa$ находится в позиции 2 тогда и только тогда, когда префикс $s$ длины 3 $baa$ . (Обратите внимание, что первое появление $aa$ в $aaa$ находится в позиции 1.).
- В целом количество префиксов длины $n+1$ так, что первое появление $aa$ находится на позиции $n$ меньше для $aa$ чем для $ba$ . Это объясняет, почему в среднем первый $aa$ прибыть позже первого $ab$ .
Мы также можем принять во внимание тот факт, что среднее количество появлений $w$ в случайной строке длины $l$ является $|A|^{l-n}$ . Это число не зависит от полинома автокорреляции. Возникновение $w$ может перекрывать другое событие по-разному. Точнее, каждая единица в векторе автокорреляции соответствует способу перекрытия вхождений. Поскольку многие случаи $w$ могут быть упакованы вместе с использованием перекрытия, но среднее количество вхождений не меняется, из этого следует, что расстояние между двумя непересекающимися вхождениями больше, когда вектор автокорреляции содержит много единиц.

Обыкновенные производящие функции

Автокорреляционные полиномы позволяют дать простые уравнения для обычных производящих функций (ОПФ) многих естественных вопросов.

ОГФ языков слов, не содержащих $w$ является ${\frac {c(z)}{z^{n}+(1-|A|z)c(z)}}$ .
OGF языков слов, содержащих $w$ является ${\frac {z^{n}}{(1-|A|z)(z^{n}+(1-|A|z)c(z))}}$ .
OGF языков слов, содержащих одно вхождение слова $w$ , в конце слова есть ${\frac {z^{n}}{z^{n}+(1-|A|z)c(z)}}$ .

Ссылки

Флажоле и Седжвик (2010). Аналитическая комбинаторика . Нью-Йорк: Издательство Кембриджского университета. стр. 60 -61. ISBN 978-0-521-89806-5 .
Розен, Нед. «Ожидаемое время ожидания подбрасывания монеты» (PDF) . Проверено 3 декабря 2017 г.
Одлыжко А.М.; Гибас, ЖЖ (1981). «Перекрытие строк, сопоставление с образцом и нетранзитивные игры». Журнал комбинаторной теории . Серия А 30 (2): 183–208. дои : 10.1016/0097-3165(81)90005-4 .