자기 상관(단어)

수학의 한 분야인 결합학에서 단어의 자기 상관은 이 단어의 기간 집합이다.더 정확히 말하면, 그것은 단어의 끝이 단어의 시작과 얼마나 닮았는지를 나타내는 일련의 값이다.이 값은 예를 들어 임의 문자열에서 이 단어의 첫 발생 평균값을 계산하는 데 사용할 수 있다.

정의

이 글에서 A는 알파벳이며,${\displaystyle }w{\displaystyle }$ = ${\displaystyle {}_{}{1}_{}}$ … ${\displaystyle {}_{}}$ n$${\$displaystyle$ w$=w_{1}\dots w_{n}}$는 길이 n의 A에 대한 단어다.$w{\displaystyle }$ ${\displaystyle w}$의 자기 상관관계는 w ${\displaystyle w}$과($와{\displaystyle }$) 자체와의 상관관계로 정의할 수 있다$$.그러나, 우리는 이 개념을 아래에 다시 정의한다.

자기 상관 벡터

The autocorrelation vector of ${\displaystyle w}$ is ${\displaystyle c=(c_{0},\dots ,c_{n-1})}$, with ${\displaystyle c_{i}}$ being 1 if the prefix of length ${\displaystyle n-i}$ equals the suffix of length ${\displaystyle n-i}$, and with ${\displays$$tyle c_{i}},$ 그렇지 않으면 0이$$ 된다.$즉{\displaystyle {}_{}}$, c ${\displaystyle i_{}}$ ${\$는 w ${\displaystyle {\mathrm{i}}_{}}$+ 1${\displaystyle {}_{}}$… ${\displaystyle w_{}}$= ${\displaystyle {}_{}}$ 1${\displaystyle {}_{}}$… ${\displaystyle w_{}}$ -${\displaystyle i_{}}$ ${\$을(를) 표시하는지 여부를 나타낸다$$$.$

예를 들어 ${\displaystyle aaa}$의 자기 상관 벡터는 분명히$$ $i{\displaystyle }$ ${\displaystyle$$$i$}$이(가) 0, 1 또는 2인 경우$$ $길이{\displaystyle }$ n${\displaystyle }$- i ${\displaystyn-i}$의 접두사가 n - $i{\displaystyle }$ ${\displaystyn-i$의 접미사와 같기 때문에$$(${\displaystyle 1,}$1$1$)이다$.$${\displaystyle b}$ ${\displaystyle abb}$의 자기 상관 벡터는 엄격한 접미사와 동일한 접두사가 없기 ${\displaystyle \mathrm{때문}}$에 $({\displaystyle 1}$,${\displaystyle }$0${\displaystyle ,}$ ${\displaystyle 0}$ )$${\$displaystyle ($1$,0,0)}$이다.마지막으로, a ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle aabbaa}$의 자기 상관 벡터는 다음 표와 같이 100011이다$$.

a	a	b	b	a	a
a	a	b	b	a	a						1
	a	a	b	b	a	a					0
		a	a	b	b	a	a				0
			a	a	b	b	a	a			0
				a	a	b	b	a	a		1
					a	a	b	b	a	a	1

$c{\displaystyle }$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$은(는) 길이 n ${\displaystyle n}$의 접두사와 접미사가 모두$$ $w{\displaystyle }$ ${\displaystyle w}$과(와$)$ 같기 때문에 항상 1과 같다는$$ 점에 유의하십시오$.$ $마찬가지$로, ${\displaystyle c_{}}$ ${\displaystyle {\mathrm{n}}_{}}$ -${\displaystyle {}_{}}$1 {\$displaystystyle c_{n-1}$은 첫$$ 번째와 같은 경우에만 1이다.

자기 상관 다항식

The autocorrelation polynomial of ${\displaystyle w}$ is defined as ${\displaystyle c(z)=c_{0}z^{0}+\dots +c_{n-1}z^{n-1}}$. It is a polynomial of degree at most ${\displaystyle n-1}$.

For example, the autocorrelation polynomial of ${\displaystyle aaa}$ is ${\displaystyle 1+z+z^{2}}$ and the autocorrelation polynomial of ${\displaystyle abb}$ is ${\displaystyle 1}$. Finally, the autocorrelation polynomial of ${\displaystyle aabbaa}$ is ${\displaystyle 1+z^4+z^5}$${\displaystyle$ 1+z$^{4}+z^{5$

속성

이제 자기 상관 다항식을 사용하여 계산할 수 있는 몇 가지 속성을 나타낸다.

임의 문자열에서 단어 처음 발생

$확률{\displaystyle }$ $1{\displaystyle \frac{\mathrm{}}{}}$ ${\displaystyle \frac{A}{}}$ $displaystyle {1}{{ A}$의 각 문자를 임의로 무한 $시퀀스$$$s {\$displaystyle$ $s$$\}$을(를$)$ 선택한다고 가정합시다. ${\displaystyle 여기}$서${\displaystyle }$A {\$displaystyle$ A$}$은(는$)$A {\$displaystystyle$ A}의$$문자 $.$ E {\$displaystystystystystystyte$}$$$E{\displaystyle }$$}$ $s{\displaystyle }$ ${\displaystyle s}$에서 m ${\displaystyle m}$이(가) 처음 발생할 것으로$$ 예상$.$그러면 $E{\displaystyle }$ ${\displaystyle E}$이(가) A ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$( ${\displaystyle \frac{1}{}}$ A${\displaystyle \frac{}{}}$) ${\$A$^{n}c\left({\frac$ {$1}{$ A$}\오른쪽)}$과 같다$.$즉, 접두사 및 접미사인 $w$ ${\displaystyle w}$의 각 하위 단어 $v{\displaystyle }$ ${\displaystyle v$$}$이($가)$ 나중에 $w{\displaystyle }$ $displaystyle w$$}$의 첫 번째 발생 평균 값을 ${\displaystyle {}^{}}$시킨다.여기서 ${\displaystyle v}$ $displaystyle$ v $}$은(는) ${\displaystyle v}$ $displaystyle$v$}$의 길이 입니다$.$

For example, over the binary alphabet ${\displaystyle A=\{a,b\}}$, the first occurrence of ${\displaystyle aa}$ is at position ${\displaystyle 2^{2}(1+{\frac {1}{2}})=6}$ while the average first occurrence of ${\displaystyle ab}$ is at position ${\disp$$레이스타일 2^{2}(1)=4$ 직관적으로 ${\$$디스플레이스타일$ $aa}$의 첫 발생이 ${\displaystyle b}$의$$첫 발생보다 늦다는$사실$은 다음 두 가지 방법으로 설명할 수 있다$$.

• 각 위치 $p{\displaystyle }$ ${\displaystyle p}$에 대해 $w{\displaystyle }$ ${\displaystyle w}$이$($가) $p{\displaystyle }$ ${\displaystyle p}$에서 처음 발생하기 위한 요구 사항은 무엇인지 고려할 수 있다$.$
  • ${\displaystyle b}$ ${\displaystyle ab}$의 첫 번째 발생은 두 경우 모두 한 가지 방법으로만 위치 1에 있을 수 있다$$.$s{\displaystyle }$ ${\displaystyle s}$이$($가) w ${\displaystyle$ w$}(으$)로 시작하는$$ 경우 w ${\displaystyle w$의 고려된 값 모두에 $대해{\displaystyle \frac{\mathrm{}}{}}$ ${\displaystyle \frac{\mathrm{확률}}{}}$ 1 4 ${\$1}{$4}}$가 있다.
  • ${\displaystyle \mathrm{길이}}$ 3의$$ $s{\displaystyle }$ ${\displaystyle s}$ 접두사가 ${\displaystyle b}$ ${\displaystyle aab}$이거나 ${\displaystyle b}$ ${\displaystyle bab$인 경우 b ${\displaystyle ab}$의 첫 번째 발생 위치가 2이다$$.$그러나{\displaystyle }$ 길이 3의$$ $s{\displaystyle }$ ${\displaystyle s}$ 접두사가 ${\displaystyle b}${\$displaystyle baa$인 경우에만 ${\displaystyle aa$$}$의 첫$$ 번째 ${\displaystyle \mathrm{발생}}$ 위치가$$ 1인 경우 ${\displaysty aa}$이다.
  • ${\displaystyle \mathrm{일반적}}$으로 길이 $n{\displaystyle }$+ 1 ${\displaystyle n+1}$의 접두사 수는 ${\displaystyle$ $aa}$이(가) 처음 $발생$하는 위치$$n {\$displaystyle$ n$}$이(가) ${\displaystyle b}$ ${\displaystyle ba$보다 작다$$.이는 평균적으로 첫 번째 ${\displaystyle a}$ ${\displaystyle aa}$이(가) 첫 번째 ${\displaystyle b}$ ${\displaystyle ab}$보다 늦게 도착하는$$ 이유를 설명한다$.$
• 길이 $l{\displaystyle }$ ${\displaystyle l}$의 임의 문자열에서$$ $w{\displaystyle }$ ${\displaystyle w}$의 평균 발생 횟수가 ${\displaystyle {}^{}}$ -${\displaystyle n^{}}$ ${\$A$^{l-n}$인 점도$$ 고려할 수 있다$.$이 숫자는 자기 상관 다항식과는 무관하다.$w{\displaystyle }$ ${\displaystyle w}$의 발생은 다른 방식으로 다른 발생과 겹칠 수 있다$$.더 정확히 말하면, 자기 상관 벡터의 각 1은 발생이 겹치는 방법에 해당한다.$w{\displaystyle }$ ${\displaystyle w}$의 많은 발생 횟수를 중첩을 사용하여 함께 포장할 수 있지만$$ 평균 발생 횟수는 변경되지 않으므로 자기 상관 벡터에 1의 발생 횟수가 많을 때 두 개의 비 겹치지 않는 발생 간 거리가 더 커진다.

일반생성함수

자기 상관 다항식에서는 많은 자연문제의 일반적인 생성 함수(OGF)에 대한 간단한 방정식을 제공할 수 있다.

• w ${\displaystyle w}$을(를) 포함하지 않는 단어의 언어 OGF는 c${\displaystyle \frac{}{}}$( z${\displaystyle \frac{}{}}$) ${\displaystyle \frac{z^{}}{}}$ ${\displaystyle \frac{{}^{}}{}}$+${\displaystyle \frac{}{}}$( 1${\displaystyle \frac{}{}}$- A ${\displaystyle \frac{z}{}}$) ${\displaystyle \frac{c}{}}$( ${\displaystyle \frac{z}{}}$) ${\$이다$.$
• w ${\displaystyle w}$을(를) 포함하는 단어의 언어 OGF는 $z{\displaystyle \frac{{}^{}}{}}$ ${\displaystyle \frac{n^{}}{}}$(${\displaystyle \frac{1}{}}$- A${\displaystyle \frac{z}{}}$ )${\displaystyle \frac{}{}}$(${\displaystyle \frac{1}{}}$- A z ${\displaystyle \frac{)}{}}$ (${\displaystyle \frac{1}{}}$- A z${\displaystyle \frac{}{}}$)$$){\$displaystyle {\\frac{z$^{$n}{n$}{(- A z$){z^{n}+(1-A z)}}}}$이다$.$
• $w{\displaystyle }$ ${\displaystyle w$의 단일한 발생을 포함하는 단어의 언어 OGF는 z $n{\displaystyle \frac{{}^{}}{}}$ ${\displaystyle \frac{z^{}}{}}$ ${\displaystyle \frac{n^{}}{}}$+${\displaystyle \frac{}{}}$( 1${\displaystyle \frac{}{}}$- A ${\displaystyle \frac{z}{}}$) ${\displaystyle \frac{c}{}}$( $){\$^{n}}{z$^{n}+(1- A)c(z)}}}}}}}}$이다$.$

참조

• Flajolet and Sedgewick (2010). Analytic Combinatorics. New York: Cambridge University Press. pp. 60-61. ISBN 978-0-521-89806-5.
• Rosen, Ned. "Expected waiting times for strings of coin flips" (PDF). Retrieved 3 December 2017.
• Odlyzko, A. M.; Guibas, L. J. (1981). "String overlaps, pattern matching, and nontransitive games". Journal of Combinatorial Theory. Series A 30 (2): 183–208. doi:10.1016/0097-3165(81)90005-4.