Автокорреляционный многочлен — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Added article)
 
Строка 16: Строка 16:
  
 
== Пример построения автокорреляционного многочлена ==
 
== Пример построения автокорреляционного многочлена ==
Пусть имеем алфавит <tex>\Sigma = \{0, 1\}</tex>, рассмотрим строку <tex>p=001100</tex>. Будем проверять факт совпадения суффикса и префикса строки <tex>p</tex>, используя следующую таблицу:
+
Пусть имеем алфавит <tex>\Sigma = \{0, 1\}</tex>, рассмотрим строку <tex>p=001100</tex>. Будем проверять факт совпадения суффикса и префикса строки <tex>p</tex>, используя следующую таблицу: '''Не очень понятная таблица. Ну, субъективно, не очень помогает понять. Может, переформатировать?'''
 
{| class="wikitable"
 
{| class="wikitable"
 
!0
 
!0
Строка 118: Строка 118:
 
| definition = Пусть <tex>\Sigma</tex> {{---}} данный алфавит, <tex>p</tex> {{---}} данная непустая строка над алфавитом <tex>\Sigma</tex>. Найти производящую функцию множества слов, не содержащих <tex>p</tex> как подстроку.
 
| definition = Пусть <tex>\Sigma</tex> {{---}} данный алфавит, <tex>p</tex> {{---}} данная непустая строка над алфавитом <tex>\Sigma</tex>. Найти производящую функцию множества слов, не содержащих <tex>p</tex> как подстроку.
 
}}
 
}}
Пусть <tex>|\Sigma| = m</tex> {{---}} мощность алфавита <tex>\Sigma</tex>, <tex>S</tex> {{---}} множество слов, не содержащих <tex>p</tex> как подстроку, <tex>\alpha \in S</tex> {{---}} произвольное слово из <tex>S</tex>, <tex>T</tex> {{---}} множество слов, содержащих <tex>p</tex> как подстроку только в самом конце. Рассмотрим все слова вида <tex>\alpha \sigma_1, \alpha \sigma_2, \dots, \alpha \sigma_m</tex>, где <tex>\sigma_1, \sigma_2, \dots, \sigma_m</tex> {{---}} все символы алфавита <tex>\Sigma</tex>. Так как слово <tex>\alpha</tex> не содержало подстроку <tex>p</tex>, то после добавления символа <tex>\sigma_i</tex> новая строка либо так же не содержит <tex>p</tex> как подстроку, и, следовательно, <tex>\alpha\sigma_i \in S</tex>, либо содержит, но только в самом конце, и тогда <tex>\alpha\sigma_i \in T</tex>. Очевидно также, что от удаления последнего символа  у слова из <tex>T</tex> всегда получается слово из <tex>S</tex>, то есть, путём добавления ко всем <tex>\alpha \in S</tex> символа <tex>\sigma_i \in \Sigma, i=\overline{1,m},</tex> мы получим все непустые слова из <tex>T</tex> и <tex>S</tex>. В контексте комбинаторных объектов это выражается в равенстве <tex> \{\epsilon\} + S \times \Sigma = \Sigma + T</tex>, где <tex>\epsilon </tex> {{---}} комбинаторный объект веса 0, соответствующий пустой строке.
+
Пусть <tex>|\Sigma| = m</tex> {{---}} мощность алфавита <tex>\Sigma</tex>, <tex>S</tex> {{---}} множество слов, не содержащих <tex>p</tex> как подстроку, <tex>\alpha \in S</tex> {{---}} произвольное слово из <tex>S</tex>, <tex>T</tex> {{---}} множество слов, содержащих <tex>p</tex> как подстроку только в самом конце. Рассмотрим все слова вида <tex>\alpha \sigma_1, \alpha \sigma_2, \dots, \alpha \sigma_m</tex>, где <tex>\sigma_1, \sigma_2, \dots, \sigma_m</tex> {{---}} все символы алфавита <tex>\Sigma</tex>. Так как слово <tex>\alpha</tex> не содержало подстроку <tex>p</tex>, то после добавления символа <tex>\sigma_i</tex> новая строка либо так же не содержит <tex>p</tex> как подстроку, и, следовательно, <tex>\alpha\sigma_i \in S</tex>, либо содержит, но только в самом конце, и тогда <tex>\alpha\sigma_i \in T</tex>. Очевидно также, что от удаления последнего символа  у слова из <tex>T</tex> всегда получается слово из <tex>S</tex>, то есть, путём добавления ко всем <tex>\alpha \in S</tex> символа <tex>\sigma_i \in \Sigma, i=\overline{1,m},</tex> мы получим все непустые слова из <tex>T</tex> и <tex>S</tex>. В контексте комбинаторных объектов это выражается в равенстве <tex> \{\epsilon\} + S \times \Sigma = \Sigma + T</tex>, где <tex>\epsilon </tex> {{---}} комбинаторный объект веса 0, соответствующий пустой строке. '''Тут справа не S + T?'''
  
 
Рассмотрим теперь слова вида <tex>\alpha p</tex>. После добавления к слову <tex>\alpha</tex> строки <tex>p</tex> мы точно получим все строки из <tex>T</tex>, но, кроме них, могут также получиться строки, имеющие первое вхождение <tex>p</tex> не в самом конце, следовательно, нельзя утверждать, что <tex>\alpha p</tex> всегда принадлежит <tex>T</tex>. Несложно заметить, что <tex> \alpha p \notin T </tex> тогда и только тогда, когда <tex> \alpha p </tex> имеет 2 перекрывающихся вхождения строки <tex>p</tex>. Для того чтобы <tex> \alpha p </tex> имело 2 перекрывающихся вхождения строки <tex>p</tex> необходимо, чтобы <tex>p</tex> имела какой-нибудь суффикс, совпадающий с каким-нибудь префиксом, иначе говоря, чтобы <tex>p</tex> имело автокорреляционный многочлен <tex>C(z) \ne 1</tex>. В результате выходит, что при добавлении ко всем <tex>\alpha \in S</tex> строки <tex>p</tex> получим все строки из <tex>T</tex>, а также все строки, имеющие 2 перекрывающиеся вхождения строки <tex>p</tex>, иными словами, все строки вида <tex>\gamma p_0p_1 \dots p_i \dots p_{k-1} p_{k-i} p_{k-i+1} \dots p_{k-1}</tex> (или, что то же, <tex>\gamma p_0p_1 \dots p_{i-1} p_1 p_2 \dots p_{k-1}</tex>), где <tex>\gamma</tex> {{---}} некоторый префикс <tex>\alpha</tex>, <tex>i \in \overline{1, k-1}</tex>, {{---}} номер некоторого ненулевого коэффициента автокорреляционного многочлена <tex>C(z)</tex> строки <tex>p</tex>. Нетрудно заметить, что <tex>\gamma p_0p_1 \dots p_i \dots p_{k-1} p_{k-i} p_{k-i+1} \dots p_{k-1}</tex> можно представить как некую строку <tex>t \in T</tex> с приписанным в конец суффиксом строки <tex>p</tex> длины <tex>i</tex>. В контексте комбинаторных объектов суффикс строки <tex>p</tex> длины <tex>i</tex> является комбинаторным объектом веса <tex>i</tex>, а его производящей функцией является <tex>z^i</tex>, то есть, по сути, это слагаемое автокорреляционного многочлена <tex>C(z)</tex>. Тогда получаем следующее равенство: <tex>S \times \{p\} = T + \dots + T \times \{p_{k-i} p_{k-i+1} \dots p_{k-1}\} + \dots = T \times C</tex>, где <tex>C</tex> {{---}} комбинаторный класс, соответствующий автокорреляционному многочлену <tex>C(z)</tex>.
 
Рассмотрим теперь слова вида <tex>\alpha p</tex>. После добавления к слову <tex>\alpha</tex> строки <tex>p</tex> мы точно получим все строки из <tex>T</tex>, но, кроме них, могут также получиться строки, имеющие первое вхождение <tex>p</tex> не в самом конце, следовательно, нельзя утверждать, что <tex>\alpha p</tex> всегда принадлежит <tex>T</tex>. Несложно заметить, что <tex> \alpha p \notin T </tex> тогда и только тогда, когда <tex> \alpha p </tex> имеет 2 перекрывающихся вхождения строки <tex>p</tex>. Для того чтобы <tex> \alpha p </tex> имело 2 перекрывающихся вхождения строки <tex>p</tex> необходимо, чтобы <tex>p</tex> имела какой-нибудь суффикс, совпадающий с каким-нибудь префиксом, иначе говоря, чтобы <tex>p</tex> имело автокорреляционный многочлен <tex>C(z) \ne 1</tex>. В результате выходит, что при добавлении ко всем <tex>\alpha \in S</tex> строки <tex>p</tex> получим все строки из <tex>T</tex>, а также все строки, имеющие 2 перекрывающиеся вхождения строки <tex>p</tex>, иными словами, все строки вида <tex>\gamma p_0p_1 \dots p_i \dots p_{k-1} p_{k-i} p_{k-i+1} \dots p_{k-1}</tex> (или, что то же, <tex>\gamma p_0p_1 \dots p_{i-1} p_1 p_2 \dots p_{k-1}</tex>), где <tex>\gamma</tex> {{---}} некоторый префикс <tex>\alpha</tex>, <tex>i \in \overline{1, k-1}</tex>, {{---}} номер некоторого ненулевого коэффициента автокорреляционного многочлена <tex>C(z)</tex> строки <tex>p</tex>. Нетрудно заметить, что <tex>\gamma p_0p_1 \dots p_i \dots p_{k-1} p_{k-i} p_{k-i+1} \dots p_{k-1}</tex> можно представить как некую строку <tex>t \in T</tex> с приписанным в конец суффиксом строки <tex>p</tex> длины <tex>i</tex>. В контексте комбинаторных объектов суффикс строки <tex>p</tex> длины <tex>i</tex> является комбинаторным объектом веса <tex>i</tex>, а его производящей функцией является <tex>z^i</tex>, то есть, по сути, это слагаемое автокорреляционного многочлена <tex>C(z)</tex>. Тогда получаем следующее равенство: <tex>S \times \{p\} = T + \dots + T \times \{p_{k-i} p_{k-i+1} \dots p_{k-1}\} + \dots = T \times C</tex>, где <tex>C</tex> {{---}} комбинаторный класс, соответствующий автокорреляционному многочлену <tex>C(z)</tex>.
Строка 125: Строка 125:
 
:<tex>
 
:<tex>
 
\begin{cases}
 
\begin{cases}
   \{\epsilon\} + S \times \Sigma = \Sigma + T \\
+
   \{\epsilon\} + S \times \Sigma = \Sigma + T '''и тут тоже S'''\\
 
   S \times \{p\} = T \times C \\
 
   S \times \{p\} = T \times C \\
 
\end{cases}
 
\end{cases}

Версия 23:07, 23 июня 2020

Определение:
Автокорреляционный многочлен (англ. autocorrelation polynomial) для строки [math]p[/math] длины [math]k[/math] — это многочлен вида [math]C(z)=\sum\limits_{i=0}^{k-1} c_i z^i[/math], причем [math]c_i = 1[/math], если префикс строки [math]p[/math] длины [math]k-i[/math] совпадает с суффиксом строки [math]p[/math] длины [math]k-i[/math], иначе [math]c_i = 0[/math]:

[math]c_i(x) = \begin{cases} 1,\ \ p_0 \dots p_{k-i-1} = p_i \dots p_{k-1} \\ 0,\ \ p_0 \dots p_{k-i-1} \ne p_i \dots p_{k-1} \\ \end{cases} [/math]


Пример построения автокорреляционного многочлена

Пусть имеем алфавит [math]\Sigma = \{0, 1\}[/math], рассмотрим строку [math]p=001100[/math]. Будем проверять факт совпадения суффикса и префикса строки [math]p[/math], используя следующую таблицу: Не очень понятная таблица. Ну, субъективно, не очень помогает понять. Может, переформатировать?

0 0 1 1 0 0 ci
0 0 1 1 0 0 1
0 0 1 1 0 0 0
0 0 1 1 0 0 0
0 0 1 1 0 0 0
0 0 1 1 0 0 1
0 0 1 1 0 0 1

В итоге автокорреляционный многочлен строки [math]p=001100[/math] это [math]C(z) = 1 + z^4 + z^5[/math].

Несложно заметить, что [math]c_0[/math] всегда равняется [math]1[/math], ибо префикс и суффикс длины [math]n[/math] являются исходной строкой и, следовательно, всегда совпадают. [math]c_{n-1}[/math] равняется [math]1[/math] только в том случае, если первый и последний символы строки совпадают.

Примеры решений задач с использованием автокорреляционного многочлена

Задача:
Пусть [math]\Sigma[/math] — данный алфавит, [math]p[/math] — данная непустая строка над алфавитом [math]\Sigma[/math]. Найти производящую функцию множества слов, не содержащих [math]p[/math] как подстроку.

Пусть [math]|\Sigma| = m[/math] — мощность алфавита [math]\Sigma[/math], [math]S[/math] — множество слов, не содержащих [math]p[/math] как подстроку, [math]\alpha \in S[/math] — произвольное слово из [math]S[/math], [math]T[/math] — множество слов, содержащих [math]p[/math] как подстроку только в самом конце. Рассмотрим все слова вида [math]\alpha \sigma_1, \alpha \sigma_2, \dots, \alpha \sigma_m[/math], где [math]\sigma_1, \sigma_2, \dots, \sigma_m[/math] — все символы алфавита [math]\Sigma[/math]. Так как слово [math]\alpha[/math] не содержало подстроку [math]p[/math], то после добавления символа [math]\sigma_i[/math] новая строка либо так же не содержит [math]p[/math] как подстроку, и, следовательно, [math]\alpha\sigma_i \in S[/math], либо содержит, но только в самом конце, и тогда [math]\alpha\sigma_i \in T[/math]. Очевидно также, что от удаления последнего символа у слова из [math]T[/math] всегда получается слово из [math]S[/math], то есть, путём добавления ко всем [math]\alpha \in S[/math] символа [math]\sigma_i \in \Sigma, i=\overline{1,m},[/math] мы получим все непустые слова из [math]T[/math] и [math]S[/math]. В контексте комбинаторных объектов это выражается в равенстве [math] \{\epsilon\} + S \times \Sigma = \Sigma + T[/math], где [math]\epsilon [/math] — комбинаторный объект веса 0, соответствующий пустой строке. Тут справа не S + T?

Рассмотрим теперь слова вида [math]\alpha p[/math]. После добавления к слову [math]\alpha[/math] строки [math]p[/math] мы точно получим все строки из [math]T[/math], но, кроме них, могут также получиться строки, имеющие первое вхождение [math]p[/math] не в самом конце, следовательно, нельзя утверждать, что [math]\alpha p[/math] всегда принадлежит [math]T[/math]. Несложно заметить, что [math] \alpha p \notin T [/math] тогда и только тогда, когда [math] \alpha p [/math] имеет 2 перекрывающихся вхождения строки [math]p[/math]. Для того чтобы [math] \alpha p [/math] имело 2 перекрывающихся вхождения строки [math]p[/math] необходимо, чтобы [math]p[/math] имела какой-нибудь суффикс, совпадающий с каким-нибудь префиксом, иначе говоря, чтобы [math]p[/math] имело автокорреляционный многочлен [math]C(z) \ne 1[/math]. В результате выходит, что при добавлении ко всем [math]\alpha \in S[/math] строки [math]p[/math] получим все строки из [math]T[/math], а также все строки, имеющие 2 перекрывающиеся вхождения строки [math]p[/math], иными словами, все строки вида [math]\gamma p_0p_1 \dots p_i \dots p_{k-1} p_{k-i} p_{k-i+1} \dots p_{k-1}[/math] (или, что то же, [math]\gamma p_0p_1 \dots p_{i-1} p_1 p_2 \dots p_{k-1}[/math]), где [math]\gamma[/math] — некоторый префикс [math]\alpha[/math], [math]i \in \overline{1, k-1}[/math], — номер некоторого ненулевого коэффициента автокорреляционного многочлена [math]C(z)[/math] строки [math]p[/math]. Нетрудно заметить, что [math]\gamma p_0p_1 \dots p_i \dots p_{k-1} p_{k-i} p_{k-i+1} \dots p_{k-1}[/math] можно представить как некую строку [math]t \in T[/math] с приписанным в конец суффиксом строки [math]p[/math] длины [math]i[/math]. В контексте комбинаторных объектов суффикс строки [math]p[/math] длины [math]i[/math] является комбинаторным объектом веса [math]i[/math], а его производящей функцией является [math]z^i[/math], то есть, по сути, это слагаемое автокорреляционного многочлена [math]C(z)[/math]. Тогда получаем следующее равенство: [math]S \times \{p\} = T + \dots + T \times \{p_{k-i} p_{k-i+1} \dots p_{k-1}\} + \dots = T \times C[/math], где [math]C[/math] — комбинаторный класс, соответствующий автокорреляционному многочлену [math]C(z)[/math].

В результате имеем 2 уравнения:

[math] \begin{cases} \{\epsilon\} + S \times \Sigma = \Sigma + T '''и тут тоже S'''\\ S \times \{p\} = T \times C \\ \end{cases} [/math]

В терминах производящих функций эти уравнения выглядят так:

[math] \begin{cases} 1 + S(z) \cdot mz = S(z) + T(z) \\ S(z) \cdot z^k = T(z) \cdot C(z) \\ \end{cases} [/math]

Решим полученную систему относительно [math]S(z)[/math]:

[math] \begin{cases} T(z) = 1 + (mz-1)S(z) \\ S(z) \cdot z^k = (1 + (mz-1)S(z)) \cdot C(z) \\ \end{cases} [/math]
[math] S(z) \cdot (z^k - (mz-1)C(z)) = C(z) \\ [/math]

В итоге получаем искомую производящую функцию множества [math]S[/math] слов, не содержащих данную непустую [math]p[/math] как подстроку:

[math] S(z) = \dfrac{C(z)}{z^k - (mz-1)C(z)} \\ [/math], где [math]C(z)[/math] — автокорреляционный многочлен [math]p[/math], [math]m = |\Sigma|[/math], [math]k = |p|[/math].


Задача:
Пусть [math]\Sigma[/math] — данный алфавит, [math]p[/math] — данная непустая строка над алфавитом [math]\Sigma[/math]. Найти производящую функцию множества слов, содержащих [math]p[/math] как подстроку.

Пусть [math]m[/math] — мощность данного алфавита [math]\Sigma[/math]. Ясно, что слов длины [math]n[/math] над алфавитом мощности [math]m[/math] будет [math]m^n[/math] штук. Тогда производящей функцией множества всех слов над алфавитом мощности [math]m[/math] будет [math]\dfrac{1}{1-mz}[/math]. Вычтя из нее полученную ранее производящую функцию множества слов, не содержащих [math]p[/math] как подстроку, получим искомую производящую функцию: [math]\dfrac{1}{1-mz} - \dfrac{C(z)}{z^k - (mz-1)C(z)} = \dfrac{z^k - (mz-1)C(z) - (1-mz)C(z)}{(1-mz)(z^k - (mz-1)C(z))} = \dfrac{z^k}{(1-mz)(z^k + (1-mz)C(z))}[/math], где [math]C(z)[/math] — автокорреляционный многочлен [math]p[/math], [math]k = |p|[/math].


Задача:
Пусть [math]\Sigma[/math] — данный алфавит, [math]p[/math] — данная непустая строка над алфавитом [math]\Sigma[/math]. Найти производящую функцию множества слов, имеющих единственное вхождение [math]p[/math] как подстроки в самом конце.

Пусть [math]T[/math] — множество слов, содержащих [math]p[/math] как подстроку только в самом конце. Вернемся к системе уравнений, полученной при решении первой задачи, и воспользуемся найденным выражением [math]S(z)[/math]:

[math] \begin{cases} T(z) = 1 + (mz-1)S(z) \\ S(z) = \dfrac{C(z)}{z^k - (mz-1)C(z)} \\ \end{cases} [/math]
[math] T(z) = 1 + (mz-1)\dfrac{C(z)}{z^k - (mz-1)C(z)} \\ [/math]

В результате получаем искомую производящую функцию [math]T(z)[/math]:

[math] T(z) = \dfrac{z^k}{z^k - (mz-1)C(z)} \\ [/math], где [math]C(z)[/math] — автокорреляционный многочлен [math]p[/math], [math]m = |\Sigma|[/math], [math]k = |p|[/math].

См. также

Источники информации