自己相関（単語）

数学の一分野である組合せ論では、単語の自己相関とは、その単語の周期の集合のことです。より正確には、単語の末尾が単語の先頭にどの程度似ているかを示す値のシーケンスです。この値を使用して、たとえば、ランダムな文字列内でこの単語が最初に出現する平均値を計算できます。

この記事では、A はアルファベットであり、長さnのA上の単語です。 の自己相関は、と自身と の相関として定義できます。 ただし、この概念を以下で再定義します。${\displaystyle w=w_{1}\dots w_{n}}$${\displaystyle w}$${\displaystyle w}$

の自己相関ベクトルは であり、長さ の接頭辞が長さ の接尾辞と等しい場合は 1 になり、それ以外の場合は 0 になります。つまり、 かどうかを示します。 ${\displaystyle w}$${\displaystyle c=(c_{0},\dots,c_{n-1})}$${\displaystyle c_{i}}$${\displaystyle に}$${\displaystyle に}$${\displaystyle c_{i}}$${\displaystyle c_{i}}$${\displaystyle w_{i+1}\dots w_{n}=w_{1}\dots w_{ni}}$

たとえば、 の自己相関ベクトルはです。これは、 が 0、1、または 2 の場合、長さ のプレフィックスは長さ のサフィックスに等しいことは明らかだからです。の自己相関ベクトルはです。これは、厳密なプレフィックスは厳密なサフィックスに等しくないからです。最後に、 の自己相関ベクトルは、次の表に示すように 100011 です。 ${\displaystyle aaa}$${\displaystyle (1,1,1)}$${\displaystyle i}$${\displaystyle に}$${\displaystyle に}$${\displaystyle abb}$${\displaystyle (1,0,0)}$${\displaystyle aabbaa}$

長さ の接頭辞と接尾辞は両方とも単語 に等しいため、 は常に 1 に等しいことに注意してください。同様に、最初と最後の文字が同じ場合のみ は 1 になります。 ${\displaystyle c_{0}}$${\displaystyle n}$${\displaystyle w}$${\displaystyle c_{n-1}}$

の自己相関多項式は と定義されます。これは最大次数の多項式です。 ${\displaystyle w}$${\displaystyle c(z)=c_{0}z^{0}+\dots +c_{n-1}z^{n-1}}$${\displaystyle n-1}$

たとえば、 の自己相関多項式はであり、 の自己相関多項式は です。最後に、 の自己相関多項式はです。 ${\displaystyle aaa}$${\displaystyle 1+z+z^{2}}$${\displaystyle abb}$${\displaystyle 1}$${\displaystyle aabbaa}$${\displaystyle 1+z^{4}+z^{5}}$

ここで、自己相関多項式を使用して計算できるいくつかの特性を示します。

の文字の無限シーケンスをランダムに選択するとします。各文字は確率 で選択され、は の文字数です。?における? の最初の出現の期待値を と呼びます。すると、 は に等しくなります。つまり、 が接頭辞と接尾辞の両方である各サブワードにより、 文字後にの最初の出現の平均値が生成されることになります。これがv の長さです。 ${\displaystyle s}$${\displaystyle A}$${\displaystyle {\frac {1}{|A|}}}$${\displaystyle |A|}$${\displaystyle A}$${\displaystyle E}$${\displaystyle m}$${\displaystyle s}$${\displaystyle E}$${\displaystyle |A|^{n}c\left({\frac {1}{|A|}}\right)}$${\displaystyle v}$${\displaystyle w}$${\displaystyle w}$${\displaystyle |A|^{|v|}}$${\displaystyle |v|}$

たとえば、2 進アルファベット では、 の最初の出現は位置 で起こります が、 の平均最初の出現は位置 です。 直感的に、 の最初の出現が の最初の出現よりも後であるという事実は、次の2 つの方法で説明できます。 ${\displaystyle A=\{a,b\}}$${\displaystyle aa}$${\displaystyle 2^{2}(1+{\frac {1}{2}})=6}$${\displaystyle ab}$${\displaystyle 2^{2}(1)=4}$${\displaystyle aa}$${\displaystyle ab}$

• 各位置 について、が最初に で出現するための要件は何かを検討することができます。 ${\displaystyle p}$${\displaystyle w}$${\displaystyle p}$
  • どちらの場合も、の最初の出現が位置 1 に存在する方法は 1 つだけです。が で始まる場合、の両方の考慮される値に対して、この確率が存在します。${\displaystyle ab}$${\displaystyle s}$${\displaystyle w}$${\displaystyle {\frac {1}{4}}}$${\displaystyle w}$
  • 長さ 3 ののプレフィックスがまたは である場合、の最初の出現は位置 2 にあります。ただし、長さ 3の のプレフィックスが である場合に限り、の最初の出現は位置 2 にあります。(におけるの最初の出現は位置 1 にあることに注意してください。)${\displaystyle ab}$${\displaystyle s}$${\displaystyle aab}$${\displaystyle バブ}$${\displaystyle aa}$${\displaystyle s}$${\displaystyle baa}$${\displaystyle aa}$${\displaystyle aaa}$
  • 一般に、が位置 に最初に出現するような長さ のプレフィックスの数は、の場合の方が の場合よりも少なくなります。これは、平均して最初のが最初の よりも後に到着する理由を説明しています。${\displaystyle n+1}$${\displaystyle aa}$${\displaystyle n}$${\displaystyle aa}$${\displaystyle ba}$${\displaystyle aa}$${\displaystyle ab}$
• また、長さのランダムな文字列におけるの平均出現回数は であるという事実も考慮に入れることができます。この数は、自己相関多項式とは無関係です。 の出現は、さまざまな方法で別の出現と重なることがあります。より正確には、自己相関ベクトル内の各 1 は、出現が重なる方法に対応します。 の出現は、重なりを利用して多数まとめてパックできますが、平均出現回数は変わらないため、自己相関ベクトルに 1 が多数含まれる場合、重なり合わない 2 つの出現間の距離は大きくなります。${\displaystyle w}$${\displaystyle l}$${\displaystyle |A|^{ln}}$${\displaystyle w}$${\displaystyle w}$

自己相関多項式を使用すると、多くの自然な問題の通常の生成関数(OGF)に対して簡単な方程式を与えることができます。

• を含まない単語の言語の OGF は です。${\displaystyle w}$${\displaystyle {\frac {c(z)}{z^{n}+(1-|A|z)c(z)}}}$
• を含む単語の言語の OGF は です。${\displaystyle w}$${\displaystyle {\frac {z^{n}}{(1-|A|z)(z^{n}+(1-|A|z)c(z))}}$
• 単語の末尾に が1 回だけ含まれる単語の言語の OGF はです。${\displaystyle w}$${\displaystyle {\frac {z^{n}}{z^{n}+(1-|A|z)c(z)}}}$

• Flajolet と Sedgewick (2010)。解析的組合せ論。ニューヨーク: Cambridge University Press。pp. 60-61。ISBN 978-0-521-89806-5。
• Rosen, Ned. 「コイン投げの連続に対する予想待ち時間」(PDF) 。2017年12 月 3 日閲覧。
• Odlyzko, AM; Guibas , LJ (1981). 「文字列の重複、パターンマッチング、および非推移的ゲーム」。組み合わせ理論ジャーナル。シリーズ A 30 (2): 183–208。doi :10.1016/0097-3165(81)90005-4。