サフィックスオートマトン

Deterministic finite automaton accepting set of all suffixes of particular string

サフィックスオートマトン
タイプ	部分文字列インデックス
発明された	1983
発明者	アンセルム・ブルマー。ジャネット・ブルーマー。アンジェイ・エーレンフォイヒト;デヴィッド・ハウスラー;ロス・マッコーネル
ビッグO記法による時間計算量 手術 平均 最悪の場合 空間複雑性 空間 ${\displaystyle O(n)}$ ${\displaystyle O(n)}$

コンピュータサイエンスにおいて、サフィックス・オートマトンとは、与えられた文字列の部分文字列インデックスを表す効率的なデータ構造であり、これにより、そのすべての部分文字列に関する圧縮された情報の保存、処理、および取得が可能になります。文字列のサフィックス・オートマトンとは、専用の開始頂点と「最終」頂点の集合を持つ最小の有向非巡回グラフであり、開始頂点から最終頂点へのパスが文字列のサフィックスを表します。 ${\displaystyle S}$

オートマトン理論において、サフィックス・オートマトンとは、与えられた文字列のサフィックス集合を認識する最小の部分決定性有限オートマトンである。サフィックス・オートマトンの状態グラフは、有向非巡回語グラフ（DAWG）と呼ばれ、この用語は、決定性非巡回有限状態オートマトン全般を指すために使用されることもある。 ${\displaystyle S=s_{1}s_{2}\dots s_{n}}$

サフィックス・オートマトン（接尾辞オートマトン）は、1983年にデンバー大学とコロラド大学ボルダー校の科学者グループによって導入されました。彼らは、その構築に線形時間 オンラインアルゴリズムを提案し、長さが2文字以上の文字列のサフィックス・オートマトンが最大で 状態と遷移を持つことを示しました。その後の研究により、サフィックス・オートマトンとサフィックス・ツリーの間には密接な関連性が示され、単一の出力アークを持つノードを圧縮することで得られるコンパクト・サフィックス・オートマトンなど、サフィックス・オートマトンに関するいくつかの一般化が概説されました。 ${\displaystyle S}$ ${\textstyle 2|S|-1}$ ${\textstyle 3|S|-4}$

サフィックスオートマトンでは、部分文字列の検索や2 つ以上の文字列の最大共通部分文字列の計算などの問題に対して効率的なソリューションを提供します。

歴史

アンセルム・ブルーマーと、文字列ababcおよびabcabの一般化された CDAWG の図

サフィックスオートマトンの概念は、デンバー大学とコロラド大学ボルダー校のアンセルム・ブルーマー、ジャネット・ブルーマー、アンジェイ・エーレンフォイヒト、デイヴィッド・ハウスラー、ロス・マッコーネルからなる科学者グループによって1983年^[1]に導入されましたが、同様の概念はそれ以前にもピーター・ワイナー^[2] 、ヴォーン・プラット^[3]、アナトール・スリセンコ^[4]らの研究においてサフィックスツリーと並んで研究されていました。初期の研究で、ブルーマーらは最大で状態と遷移を持つよりも長い文字列用に構築されたサフィックスオートマトンを示し、オートマトン構築のための線形アルゴリズムを提案しました^{[5] 。} ${\displaystyle S}$ ${\displaystyle 1}$ ${\displaystyle 2|S|-1}$ ${\displaystyle 3|S|-4}$

1983年、Mu-Tian ChenとJoel Seiferasはそれぞれ独立に、Weinerの1973年のサフィックスツリー構築アルゴリズム^[2]が、文字列のサフィックスツリーを構築する際に、逆順にした文字列のサフィックスオートマトンを補助構造として構築することを示した。^[6] 1987年、Blumerらはサフィックスツリーで使用される圧縮技術をサフィックスオートマトンに適用し、コンパクトサフィックスオートマトンを発明した。これは、コンパクト有向非巡回ワードグラフ（CDAWG）とも呼ばれる。^[7] 1997年、Maxime CrochemoreとRenaud Vérinは、直接CDAWG構築のための線形アルゴリズムを開発した。^[1] 2001年、Shunsuke Inenagaらは、トライによって与えられた単語の集合に対してCDAWGを構築するアルゴリズムを開発した。^[8] ${\displaystyle S}$ ${\textstyle S^{R}}$

定義

通常、接尾辞オートマトンと関連概念について話すときは、形式言語理論とオートマトン理論の概念が使われます。特に：^[9]

• 「アルファベット」とは、単語を構成するために用いられる有限の集合です。その要素は「文字」と呼ばれます。 ${\displaystyle \Sigma }$
• 「単語」は有限個の文字列です。単語の「長さ」は と表されます。 ${\displaystyle \omega =\omega _{1}\omega _{2}\dots \omega _{n}}$ ${\displaystyle \omega }$ ${\displaystyle |\omega |=n}$
• 「形式言語」とは、与えられたアルファベット上の単語の集合です。
• 「すべての単語の言語」は（文字「*」はクリーネ星を表す）として表され、「空の単語」（長さがゼロの単語）は 文字で表されます。 ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \varepsilon }$
• 「単語の連結」と はまたはと表され、の右側にと書いて得られる単語 に対応します。 ${\displaystyle \alpha =\alpha _{1}\alpha _{2}\dots \alpha _{n}}$ ${\displaystyle \beta =\beta _{1}\beta _{2}\dots \beta _{m}}$ ${\displaystyle \alpha \cdot \beta }$ ${\displaystyle \alpha \beta }$ ${\displaystyle \beta }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha \beta =\alpha _{1}\alpha _{2}\dots \alpha _{n}\beta _{1}\beta _{2}\dots \beta _{m}}$
• 「言語の連結」およびはまたはで表され、ペアワイズ連結の集合に対応します。 ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A\cdot B}$ ${\displaystyle AB}$ ${\displaystyle AB=\{\alpha \beta :\alpha \in A,\beta \in B\}}$
• 単語が （ ）と表される場合、単語 、 、はそれぞれ単語の「接頭辞」、「接尾辞」、および「部分語」（部分文字列）と呼ばれます。 ${\displaystyle \omega \in \Sigma ^{*}}$ ${\displaystyle \omega =\alpha \gamma \beta }$ ${\displaystyle \alpha ,\beta ,\gamma \in \Sigma ^{*}}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$ ${\displaystyle \omega }$
• と（）の場合、 は部分語としてに「出現する」と言われます。ここで、 と はそれぞれにおけるの出現位置の左と右と呼ばれます。 ${\displaystyle T=T_{1}\dots T_{n}}$ ${\displaystyle T_{l}T_{l+1}\dots T_{r}=S}$ ${\displaystyle 1\leq l\leq r\leq n}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle l}$ ${\displaystyle r}$ ${\displaystyle S}$ ${\displaystyle T}$

オートマトン構造

正式には、決定性有限オートマトンは次の5組 で決定される。^[10] ${\displaystyle {\mathcal {A}}=(\Sigma ,Q,q_{0},F,\delta )}$

• ${\displaystyle \Sigma }$単語を構成するのに使われる「アルファベット」です。
• ${\displaystyle Q}$オートマトン「状態」の集合であり、
• ${\displaystyle q_{0}\in Q}$オートマトンの初期状態であり、
• ${\displaystyle F\subset Q}$オートマトンにおける「最終」状態の集合である。
• ${\displaystyle \delta :Q\times \Sigma \mapsto Q}$は、オートマトンの部分的な「遷移」関数であり、およびについては、未定義であるか、文字から への遷移を定義します。 ${\displaystyle \delta (q,\sigma )}$ ${\displaystyle q\in Q}$ ${\displaystyle \sigma \in \Sigma }$ ${\displaystyle q}$ ${\displaystyle \sigma }$

最も一般的には、決定性有限オートマトンは次の有向グラフ（「ダイアグラム」）として表現される：^[10]

• グラフの頂点の集合は状態の状態に対応し、 ${\displaystyle Q}$
• グラフには初期状態に対応する特定のマークされた頂点があり、 ${\displaystyle q_{0}}$
• グラフには、最終状態の集合に対応するいくつかのマークされた頂点があります。 ${\displaystyle F}$
• グラフ弧の集合は遷移の集合に対応する。 ${\displaystyle \delta }$
• 具体的には、すべての遷移はからへの弧で表され、 という記号が付きます。この遷移は と表記されることもあります。 ${\textstyle \delta (q_{1},\sigma )=q_{2}}$ ${\displaystyle q_{1}}$ ${\displaystyle q_{2}}$ ${\displaystyle \sigma }$ ${\textstyle q_{1}{\begin{smallmatrix}{\sigma }\\[-5pt]{\longrightarrow }\end{smallmatrix}}q_{2}}$

図式的に言えば、オートマトンが単語を認識するのは、最初の頂点からある最後の頂点への経路が存在し、その経路上の文字の連結が を形成する場合のみです。オートマトンによって認識される単語の集合は、オートマトンによって認識されるように設定された言語を形成します。この用語において、 の接尾辞オートマトンによって認識される言語は、その（おそらく空の）接尾辞の言語です。^[9] ${\displaystyle \omega =\omega _{1}\omega _{2}\dots \omega _{m}}$ ${\displaystyle q_{0}}$ ${\displaystyle q\in F}$ ${\displaystyle \omega }$ ${\displaystyle S}$

オートマトン状態

言語に関する単語の「右文脈」とは、単語の集合であって、それらを で連結すると から の単語が形成されるような単語の集合である。右文脈は、すべての単語の集合に自然な同値関係を誘導する。言語が何らかの決定論的有限オートマトンによって認識される場合、同じ言語を認識し、状態数が最小となる、同型性を除く唯一のオートマトンが存在する。このようなオートマトンを、与えられた言語 に対する最小オートマトンと呼ぶ。マイヒル・ネローデ定理は、右文脈を用いてこれを明示的に定義することを可能にする。^{[11] [12]} ${\displaystyle \omega }$ ${\displaystyle L}$ ${\displaystyle [\omega ]_{R}=\{\alpha :\omega \alpha \in L\}}$ ${\displaystyle \alpha }$ ${\displaystyle \omega }$ ${\displaystyle L}$ ${\displaystyle [\alpha ]_{R}=[\beta ]_{R}}$ ${\displaystyle L}$ ${\displaystyle L}$

定理—アルファベット上の言語を認識する最小オートマトンを次のように明示的に定義できます。 ${\displaystyle L}$ ${\displaystyle \Sigma }$

• アルファベットは同じまま、 ${\displaystyle \Sigma }$
• 状態はすべての可能な単語の正しい文脈に対応し、 ${\displaystyle Q}$ ${\displaystyle [\omega ]_{R}}$ ${\displaystyle \omega \in \Sigma ^{*}}$
• 初期状態は空語の右文脈に対応し、 ${\displaystyle q_{0}}$ ${\displaystyle [\varepsilon ]_{R}}$
• 最終状態は、以下の単語の正しい文脈に対応する。 ${\displaystyle F}$ ${\displaystyle [\omega ]_{R}}$ ${\displaystyle \omega \in L}$
• 遷移は によって与えられます。ここで、および です。 ${\displaystyle \delta }$ ${\displaystyle [\omega ]_{R}{\begin{smallmatrix}{\sigma }\\[-5pt]{\longrightarrow }\end{smallmatrix}}[\omega \sigma ]_{R}}$ ${\displaystyle \omega \in \Sigma ^{*}}$ ${\displaystyle \sigma \in \Sigma }$

これらの用語において、「接尾辞オートマトン」とは、単語 の接尾辞の言語を認識する最小の決定論的有限オートマトンである。この言語における単語 の右文脈は、が の接尾辞である単語 から構成される。これにより、単語 の右文脈と におけるその出現の右位置の集合との間の一対一関係を定義する以下の補題が定式化される。[ ^{13] [14]} ${\displaystyle S=s_{1}s_{2}\dots s_{n}}$ ${\displaystyle \omega }$ ${\displaystyle \alpha }$ ${\displaystyle \omega \alpha }$ ${\displaystyle S}$ ${\displaystyle S}$

定理—におけるの出現の正しい位置の集合をとします。 ${\displaystyle endpos(\omega )=\{r:\omega =s_{l}\dots s_{r}\}}$ ${\displaystyle \omega }$ ${\displaystyle S}$

との間には次の一対一の関係があります。 ${\displaystyle endpos(\omega )}$ ${\displaystyle [\omega ]_{R}}$

• もしならば; ${\displaystyle x\in endpos(\omega )}$ ${\displaystyle s_{x+1}s_{x+2}\dots s_{n}\in [\omega ]_{R}}$
• もし なら、。 ${\displaystyle \alpha \in [\omega ]_{R}}$ ${\displaystyle n-\vert \alpha \vert \in endpos(\omega )}$

例えば、単語とその部分語については、と が成り立ちます。非公式には、は の出現に続く単語から の末尾までで構成され、はそれらの出現の右位置によって形成されます。この例では、要素 は単語 に対応し、単語 は要素 に対応します。 ${\displaystyle S=abacaba}$ ${\displaystyle \omega =ab}$ ${\displaystyle endpos(ab)=\{2,6\}}$ ${\displaystyle [ab]_{R}=\{a,acaba\}}$ ${\displaystyle [ab]_{R}}$ ${\displaystyle ab}$ ${\displaystyle S}$ ${\displaystyle endpos(ab)}$ ${\displaystyle x=2\in endpos(ab)}$ ${\displaystyle s_{3}s_{4}s_{5}s_{6}s_{7}=acaba\in [ab]_{R}}$ ${\displaystyle a\in [ab]_{R}}$ ${\displaystyle 7-|a|=6\in endpos(ab)}$

これはサフィックスオートマトンの状態のいくつかの構造特性を意味する。とすると、次のようになる。^[14] ${\displaystyle |\alpha |\leq |\beta |}$

• と が少なくとも1つの共通元 を持つ場合、と も共通元を持ちます。これはが の接尾辞であり、したがって とであることを意味します。前述の例では、 なのでは の接尾辞であり、したがって とです。 ${\displaystyle [\alpha ]_{R}}$ ${\displaystyle [\beta ]_{R}}$ ${\displaystyle x}$ ${\displaystyle endpos(\alpha )}$ ${\displaystyle endpos(\beta )}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle endpos(\beta )\subset endpos(\alpha )}$ ${\displaystyle [\beta ]_{R}\subset [\alpha ]_{R}}$ ${\displaystyle a\in [ab]_{R}\cap [cab]_{R}}$ ${\displaystyle ab}$ ${\displaystyle cab}$ ${\displaystyle [cab]_{R}=\{a\}\subset \{a,acaba\}=[ab]_{R}}$ ${\displaystyle endpos(cab)=\{6\}\subset \{2,6\}=endpos(ab)}$
• ならば、はの接尾辞としてのみに出現します。例えば、と の場合、およびが成り立ちます。 ${\displaystyle [\alpha ]_{R}=[\beta ]_{R}}$ ${\displaystyle endpos(\alpha )=endpos(\beta )}$ ${\displaystyle \alpha }$ ${\displaystyle S}$ ${\displaystyle \beta }$ ${\displaystyle \alpha =b}$ ${\displaystyle \beta =ab}$ ${\displaystyle [b]_{R}=[ab]_{R}=\{a,acaba\}}$ ${\displaystyle endpos(b)=endpos(ab)=\{2,6\}}$
• およびがの接尾辞で となる場合、 となります。上記の例では、 および の「中間」接尾辞について となります。 ${\displaystyle [\alpha ]_{R}=[\beta ]_{R}}$ ${\displaystyle \gamma }$ ${\displaystyle \beta }$ ${\displaystyle |\alpha |\leq |\gamma |\leq |\beta |}$ ${\displaystyle [\alpha ]_{R}=[\gamma ]_{R}=[\beta ]_{R}}$ ${\displaystyle [c]_{R}=[bac]_{R}=\{aba\}}$ ${\displaystyle \gamma =ac}$ ${\displaystyle [ac]_{R}=\{aba\}}$

接尾辞オートマトンの状態はどれも、その状態で認識される最長単語のネストされた接尾辞の連続した連鎖を認識する。 ^[14] ${\displaystyle q=[\alpha ]_{R}}$

文字列の「左拡張」とは、 と同じ右文脈を持つ最長の文字列である。によって認識される最長文字列の長さはで表される。これは以下の式を満たす：^[15] ${\displaystyle {\overset {\scriptstyle {\leftarrow }}{\gamma }}}$ ${\displaystyle \gamma }$ ${\displaystyle \omega }$ ${\displaystyle \gamma }$ ${\displaystyle |{\overset {\scriptstyle {\leftarrow }}{\gamma }}|}$ ${\displaystyle q=[\gamma ]_{R}}$ ${\displaystyle len(q)}$

定理—の左拡張はと表すことができます。ここで、はにおけるの出現の前に がくる最長の単語です。 ${\displaystyle \gamma }$ ${\displaystyle {\overleftarrow {\gamma }}=\beta \gamma }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$ ${\displaystyle S}$ ${\displaystyle \beta }$

状態の「サフィックス リンク」は、 によって認識されないの最大のサフィックスを含む状態へのポインタです。 ${\displaystyle link(q)}$ ${\displaystyle q=[\alpha ]_{R}}$ ${\displaystyle p}$ ${\displaystyle \alpha }$ ${\displaystyle q}$

この用語で、 は より長くより長くないの接尾辞をすべて正確に認識すると言えます。また、以下の式も成り立ちます。^[15] ${\displaystyle q=[\alpha ]_{R}}$ ${\displaystyle {\overset {\scriptstyle {\leftarrow }}{\alpha }}}$ ${\displaystyle len(link(q))}$ ${\displaystyle len(q)}$

定理-サフィックスリンクは、次のように明示的に定義できるツリーを形成します。 ${\displaystyle {\mathcal {T}}(V,E)}$

1. 木の頂点はすべての部分文字列の左拡張に対応し、 ${\displaystyle V}$ ${\displaystyle {\overleftarrow {\omega }}}$ ${\displaystyle S}$
2. 木の辺は頂点のペアを接続し、 および となります。 ${\displaystyle E}$ ${\displaystyle ({\overleftarrow {\omega }},{\overleftarrow {\alpha \omega }})}$ ${\displaystyle \alpha \in \Sigma }$ ${\displaystyle {\overleftarrow {\omega }}\neq {\overleftarrow {\alpha \omega }}}$

接尾辞木との接続

サフィックストライ、サフィックスツリー、DAWG、CDAWGの関係

「接頭辞木」（または「トライ」）とは、ルート付き有向木であり、弧は文字でマークされ、その木のどの頂点からも、同じ文字でマークされた2つの出弧は存在しない。トライの一部の頂点は最終としてマークされる。トライは、ルートから最終頂点までのパスによって定義される単語の集合を認識すると言われている。このように、接頭辞木は、ルートを初期頂点とみなす場合、特別な種類の決定性有限オートマトンである。^[16]単語の「接尾辞トライ」は、接尾辞の集合を認識する接頭辞木である。「接尾辞木」は、接尾辞トライから圧縮手順によって得られる木であり、その際、それらの間の頂点の次数が2に等しい場合、後続の辺はマージされる。^[15] ${\displaystyle v}$ ${\displaystyle S}$

定義によれば、サフィックス・オートマトン（接尾辞オートマトン）は、サフィックス・トライ（接尾辞木の最小化）によって得られる。コンパクト化されたサフィックス・オートマトン（接尾辞木）は、サフィックス・ツリー（接尾辞木の端にある各文字列がアルファベットの実体文字であると仮定した場合）の最小化とサフィックス・オートマトン（接尾辞オートマトン）のコンパクト化の両方によって得られることが示される。 ^[17]同じ文字列のサフィックス・ツリーとサフィックス・オートマトンとの間のこの関係に加えて、文字列のサフィックス・オートマトンと反転文字列のサフィックス・ツリーとの間にも関係がある。^[18] ${\displaystyle S=s_{1}s_{2}\dots s_{n}}$ ${\displaystyle S^{R}=s_{n}s_{n-1}\dots s_{1}}$

右文脈と同様に、「左文脈」 、つまり、同じ左文脈を持つ最長の文字列に対応する「右拡張」、および同値関係を導入することができる。文字列の「接頭辞」の言語に関して右拡張を考慮すると、次のようになる。^[15] ${\displaystyle [\omega ]_{L}=\{\beta \in \Sigma ^{*}:\beta \omega \in L\}}$ ${\displaystyle {\overset {\scriptstyle {\rightarrow }}{\omega ~}}}$ ${\displaystyle \omega }$ ${\displaystyle [\alpha ]_{L}=[\beta ]_{L}}$ ${\displaystyle L}$ ${\displaystyle S}$

定理-文字列の接尾辞ツリーは次のように明示的に定義できます。 ${\displaystyle S}$

• 木の頂点はすべての部分文字列の右拡張に対応し、 ${\displaystyle V}$ ${\displaystyle {\overrightarrow {\omega }}}$ ${\displaystyle S}$
• エッジは、 および となる三つ組に対応します。 ${\displaystyle E}$ ${\displaystyle ({\overrightarrow {\omega }},x\alpha ,{\overrightarrow {\omega x}})}$ ${\displaystyle x\in \Sigma }$ ${\displaystyle {\overrightarrow {\omega x}}={\overrightarrow {\omega }}x\alpha }$

ここでトリプレットとは、文字列が書かれた 辺がからにあることを意味します。 ${\displaystyle (v_{1},\omega ,v_{2})\in E}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{2}}$ ${\displaystyle \omega }$

これは文字列の接尾辞リンク木と文字列の接尾辞木が同型であることを意味する：^[18] ${\displaystyle S}$ ${\displaystyle S^{R}}$

「abbcbc」と「cbcbba」という単語の接尾辞構造
「abbcbc」という単語の接尾辞オートマトン 単語「abbcbc」の接尾辞トライ、接尾辞ツリー、CDAWG 「cbcbba」という単語の接尾辞木 （「abbcbc」という単語の接尾辞リンク木）

左拡張の場合と同様に、右拡張についても次の補題が成り立つ: ^[15]

定理—文字列の右拡張はと表すことができます。ここで、は内のすべての の出現の後に が続く最長の単語です。 ${\displaystyle \gamma }$ ${\displaystyle {\overrightarrow {\gamma }}=\gamma \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \gamma }$ ${\displaystyle S}$ ${\displaystyle \alpha }$

サイズ

長さ の文字列の接尾辞オートマトンには、最大で個の状態と最大で個の遷移があります。これらの境界は、文字列と個でそれぞれ到達します。^[13]これはより厳密には、 と のように定式化できます。ここで、 とは、それぞれオートマトンにおける遷移と状態の数です。^[14] ${\displaystyle S}$ ${\displaystyle n>1}$ ${\displaystyle 2n-1}$ ${\displaystyle 3n-4}$ ${\displaystyle abb\dots bb=ab^{n-1}}$ ${\displaystyle abb\dots bc=ab^{n-2}c}$ ${\displaystyle |\delta |\leq |Q|+n-2}$ ${\displaystyle |\delta |}$ ${\displaystyle |Q|}$

最大接尾辞オートマトン
接尾辞オートマトン ${\displaystyle ab^{n-1}}$ 接尾辞オートマトン ${\displaystyle ab^{n-2}c}$

工事

最初はオートマトンには空の単語に対応する単一の状態のみが含まれていますが、その後文字列の文字が1つずつ追加され、オートマトンが各ステップで段階的に再構築されます。^[19]

州の最新情報

文字列に新しい文字が追加された後、いくつかの同値類は変化します。接尾辞の言語に関して、の正しい文脈を とします。すると、が追加された後のからへの遷移は、補題^{[14]によって定義されます。} ${\displaystyle [\alpha ]_{R_{\omega }}}$ ${\displaystyle \alpha }$ ${\displaystyle \omega }$ ${\displaystyle [\alpha ]_{R_{\omega }}}$ ${\displaystyle [\alpha ]_{R_{\omega x}}}$ ${\displaystyle x}$ ${\displaystyle \omega }$

定理—を 上の単語とし、をこのアルファベットの文字とします。すると、との間には次の対応関係が成り立ちます。 ${\displaystyle \alpha ,\omega \in \Sigma ^{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle x\in \Sigma }$ ${\displaystyle [\alpha ]_{R_{\omega }}}$ ${\displaystyle [\alpha ]_{R_{\omega x}}}$

• ${\displaystyle [\alpha ]_{R_{\omega x}}=[\alpha ]_{R_{\omega }}x\cup \{\varepsilon \}}$が;の接尾辞である場合 ${\displaystyle \alpha }$ ${\displaystyle \omega x}$
• ${\displaystyle [\alpha ]_{R_{\omega x}}=[\alpha ]_{R_{\omega }}x}$さもないと。

現在の単語にを追加した後、の右コンテキストは、が の接尾辞である場合に限り大幅に変化する可能性があります。これは、同値関係がの改良であることを意味します。言い換えると、 の場合、 です。新しい文字を追加した後、 の最大 2 つの同値クラスが分割され、それぞれが最大 2 つの新しいクラスに分割される可能性があります。まず、空の右コンテキストに対応する同値クラスは常に 2 つの同値クラスに分割され、そのうちの 1 つはそれ自体に対応し、右コンテキストとして を持ちます。この新しい同値クラスには と、 に出現しなかったそのすべての接尾辞が正確に含まれます。これは、このような単語の右コンテキストが以前は空で、現在は空の単語のみが含まれているためです。^[14] ${\displaystyle x}$ ${\displaystyle \omega }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \omega x}$ ${\displaystyle \equiv _{R_{\omega x}}}$ ${\displaystyle \equiv _{R_{\omega }}}$ ${\displaystyle [\alpha ]_{R_{\omega x}}=[\beta ]_{R_{\omega x}}}$ ${\displaystyle [\alpha ]_{R_{\omega }}=[\beta ]_{R_{\omega }}}$ ${\displaystyle \equiv _{R_{\omega }}}$ ${\displaystyle \omega x}$ ${\displaystyle \{\varepsilon \}}$ ${\displaystyle \omega x}$ ${\displaystyle \omega }$

サフィックスオートマトンの状態とサフィックスツリーの頂点との対応関係が与えられれば、新しい文字が追加された後に分岐する可能性のある2番目の状態を見つけることが可能である。 から への遷移は、反転された文字列におけるからへの遷移に対応する。サフィックスツリーで言えば、これはのサフィックスツリーへの新しい最長サフィックスの挿入に対応する。この挿入後には最大で2つの新しい頂点が形成される可能性があり、そのうちの1つは に対応し、もう1つは分岐があった場合はその直接の祖先に対応する。サフィックスオートマトンに戻ると、これは最初の新しい状態が を認識し、2番目の状態（2番目の新しい状態がある場合）がそのサフィックスリンクであることを意味する。これは補題として次のように述べることができる：^[14] ${\displaystyle \omega }$ ${\displaystyle \omega x}$ ${\displaystyle \omega ^{R}}$ ${\displaystyle x\omega ^{R}}$ ${\displaystyle x\omega ^{R}}$ ${\displaystyle \omega ^{R}}$ ${\displaystyle x\omega ^{R}}$ ${\displaystyle \omega x}$

定理—を上の単語と文字とする。また、に出現するの最長接尾辞を とし、 とする。すると、の任意の部分文字列に対して以下が成立する。 ${\displaystyle \omega \in \Sigma ^{*}}$ ${\displaystyle x\in \Sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle \alpha }$ ${\displaystyle \omega x}$ ${\displaystyle \omega }$ ${\displaystyle \beta ={\overset {\scriptstyle {\leftarrow }}{\alpha }}}$ ${\displaystyle u,v}$ ${\displaystyle \omega }$

• かつならば;​ ${\displaystyle [u]_{R_{\omega }}=[v]_{R_{\omega }}}$ ${\displaystyle [u]_{R_{\omega }}\neq [\alpha ]_{R_{\omega }}}$ ${\displaystyle [u]_{R_{\omega x}}=[v]_{R_{\omega x}}}$
• かつならば;​ ${\displaystyle [u]_{R_{\omega }}=[\alpha ]_{R_{\omega }}}$ ${\displaystyle \vert u\vert \leq \vert \alpha \vert }$ ${\displaystyle [u]_{R_{\omega x}}=[\alpha ]_{R_{\omega x}}}$
• かつならば。​ ${\displaystyle [u]_{R_{\omega }}=[\alpha ]_{R_{\omega }}}$ ${\displaystyle \vert u\vert >\vert \alpha \vert }$ ${\displaystyle [u]_{R_{\omega x}}=[\beta ]_{R_{\omega x}}}$

これは、（例えば、がにまったく出現せず、 ）の場合、空の右コンテキストに対応する同値クラスのみが分割されることを意味します。^[14] ${\displaystyle \alpha =\beta }$ ${\displaystyle x}$ ${\displaystyle \omega }$ ${\displaystyle \alpha =\beta =\varepsilon }$

接尾辞リンクに加えて、オートマトンには最終状態を定義する必要がある。構造特性から、によって認識される単語のすべての接尾辞は、の接尾辞パス上のいずれかの頂点によって認識されることがわかる。つまり、 より大きい長さの接尾辞は に存在し、 より大きいが より大きくない接尾辞はに存在する、などである。したがって、 を認識する状態が で表される場合、すべての最終状態（つまり、 の接尾辞を認識する状態）は、シーケンス を形成する。^[19] ${\displaystyle \alpha }$ ${\displaystyle q=[\alpha ]_{R}}$ ${\displaystyle (q,link(q),link^{2}(q),\dots )}$ ${\displaystyle q}$ ${\displaystyle len(link(q))}$ ${\displaystyle q}$ ${\displaystyle len(link(link(q))}$ ${\displaystyle len(link(q))}$ ${\displaystyle link(q)}$ ${\displaystyle \omega }$ ${\displaystyle last}$ ${\displaystyle \omega }$ ${\displaystyle (last,link(last),link^{2}(last),\dots )}$

遷移と接尾辞リンクの更新

文字 がに追加されると、接尾辞オートマトンの新しい状態はと になります。 からの接尾辞リンクは に、 からに遷移します。 からの単語はではその接尾辞としてのみ出現するため、 から への遷移はまったく発生しませんが、への遷移は少なくとも の長さを持ち、文字 でマークされたの接尾辞から発生する必要があります。 状態は のサブセットによって形成されるため、 からの遷移はからの遷移と同じである必要があります。一方、 につながる遷移は未満で少なくとも の長さを持つの接尾辞から発生する必要があります。これは、このような遷移が以前に につながり、この状態の分離した部分に対応しているためです。これらの接尾辞に対応する状態は、 の接尾辞リンクパスのトラバーサルによって決定できます。^[19] ${\displaystyle x}$ ${\displaystyle \omega }$ ${\displaystyle [\omega x]_{R_{\omega x}}}$ ${\displaystyle [\alpha ]_{R_{\omega x}}}$ ${\displaystyle [\omega x]_{R_{\omega x}}}$ ${\displaystyle [\alpha ]_{R_{\omega x}}}$ ${\displaystyle [\alpha ]_{R_{\omega x}}}$ ${\displaystyle link([\alpha ]_{R_{\omega }})}$ ${\displaystyle [\omega x]_{R_{\omega x}}}$ ${\displaystyle \omega x}$ ${\displaystyle [\omega x]_{R_{\omega x}}}$ ${\displaystyle \omega }$ ${\displaystyle \alpha }$ ${\displaystyle x}$ ${\displaystyle [\alpha ]_{R_{\omega x}}}$ ${\displaystyle [\alpha ]_{R_{\omega }}}$ ${\displaystyle [\alpha ]_{R_{\omega x}}}$ ${\displaystyle [\alpha ]_{R_{\omega }}}$ ${\displaystyle [\alpha ]_{R_{\omega x}}}$ ${\displaystyle \omega }$ ${\displaystyle |\alpha |}$ ${\displaystyle len(link([\alpha ]_{R_{\omega }}))}$ ${\displaystyle [\alpha ]_{R_{\omega }}}$ ${\displaystyle [\omega ]_{R_{\omega }}}$

単語abbcbcの接尾辞オートマトンの構築
∅ → a 最初の文字が追加された後、サフィックスオートマトンに 1 つの状態のみが作成されます。 同様に、サフィックス ツリーには 1 つのリーフだけが追加されます。	a → ab b は以前に出現しなかったため、以前のすべての最終状態から新しい遷移が描画されます。 同じ理由で、サフィックス ツリーのルートに別のリーフが追加されます。
ab → abb 状態 2 では単語abとbが認識されますが、新しい接尾辞はbのみであるため、この単語は状態 4 に分離されます。 サフィックス ツリーでは、頂点 2 につながるエッジの分割に対応します。	abb → abbc 文字cは初めて出現するため、以前のすべての最終状態から遷移が描画されます。 逆文字列の接尾辞ツリーでは、ルートに別のリーフが追加されます。
abbc → abbcb 状態 4 は接尾辞である単語bのみで構成されているため、状態は分割されません。 同様に、接尾辞ツリーの頂点 4 に新しいリーフが追加されます。	abbcb → abbcbc 状態 5 は単語abbc、bbc、bc、cを認識しますが、最後の 2 つだけが新しい単語の接尾辞であるため、新しい状態 8 に分離されます。 同様に、頂点 5 につながるエッジが分割され、頂点 8 がエッジの中央に配置されます。

構築アルゴリズム

上記の理論的結果から、文字xを取り、ωの接尾辞オートマトンをの接尾辞オートマトンに再構築する次のアルゴリズムが導かれる。^[19] ${\displaystyle \omega x}$

1. 単語ωに対応する状態はlastのまま保持されます。
2. xが追加された後、 lastの前の値が変数pに格納され、last自体は に対応する新しい状態に再割り当てされます。 ${\displaystyle \omega x}$
3. ωの接尾辞に対応する状態は、最後の への遷移によって更新されます。これを行うには、 xによる遷移が既に存在する状態が現れるまで、を順に実行する必要があります。 ${\displaystyle p,link(p),link^{2}(p),\dots }$
4. 前述のループが終了すると、次の 3 つのケースが考えられます。
   1. サフィックスパス上のどの状態にもxによる遷移がなかった場合、x は以前にωに発生したことがなく、最後のサフィックスリンクはにつながるはずです。 ${\displaystyle q_{0}}$
   2. xによる遷移が見つかり、状態pから状態qに至る場合、q を分割する必要はなく、最後の q の接尾辞リンクになります。 ${\displaystyle len(p)+1=len(q)}$
   3. 遷移が見つかったが、 の場合、 qからの長さが最大である単語は、新しい「クローン」状態clに分離される必要があります。 ${\displaystyle len(q)>len(p)+1}$ ${\displaystyle len(p)+1}$
5. 前のステップがclの作成で終了した場合、そこからの遷移とその接尾辞リンクはqの遷移をコピーする必要があり、同時にclはqとlastの両方の共通接尾辞リンクとして割り当てられます。
6. 以前にqに至った遷移のうち、最大で長さが の単語に対応するものはclにリダイレクトされます。これを行うには、 pの接尾辞パスを辿り、そこからxによる遷移がqに至らない状態が見つかるまで続けます。 ${\displaystyle len(p)+1}$

全体の手順は次の擬似コードで記述される：^[19]

関数 add_letter(x) : p = last と定義します。  last = new_state()を割り当てます。 len(last) = len(p) + 1 を割り当てます。δ(p, x)が未定義の 場合: δ(p, x) = last、p = link(p)を割り当てます。 q = δ(p, x)を定義します。 q = last の場合: link(last) = q 0を割り当てます。 それ以外の場合、len(q) = len(p) + 1を割り当てます: link(last) = q を割り当てます。 それ以外の場合: cl = new_state() を定義します。 len ( cl) = len(p) + 1 を割り当てます。 δ(cl) = δ(q)、link(cl) = link(q) を割り当てます。 δ(p, x) = qの場合: δ(p, x) = cl、p = link(p)を割り当てます。                          

ここではオートマトンの 初期状態であり、はオートマトンの新しい状態を作成する関数です。、、はグローバル変数として格納されているものとします。^[19]便宜上、は と定義します。 ${\displaystyle q_{0}}$new_state()lastlenlinkδlink(q0) ${\displaystyle q_{0}}$

複雑

アルゴリズムの複雑さは、オートマトンの遷移を格納するために使用される基礎構造によって異なる場合があります。メモリ割り当てが で行われると仮定した場合、メモリオーバーヘッドを伴うで実装することも、メモリオーバーヘッドを伴うで実装することもできます。このような複雑さを得るには、償却分析の方法を使用する必要があります。 の値はサイクルの各反復で厳密に減少しますが、サイクルの最初の反復の後、次のadd_letter呼び出しで最大 1 しか増加しません。 の全体的な値はを超えることはなく、新しい文字を追加する の反復間でのみ 1 増加します。これは、全体の複雑さも最大で線形であることを示唆しています。2 番目のサイクルの線形性も同様に示されます。^[19] ${\displaystyle O(n\log |\Sigma |)}$ ${\displaystyle O(n)}$ ${\displaystyle O(n)}$ ${\displaystyle O(n|\Sigma |)}$ ${\displaystyle O(1)}$ ${\displaystyle len(p)}$ ${\displaystyle len(p)}$ ${\displaystyle n}$

一般化

サフィックスオートマトン（接尾辞オートマトン）は、他のサフィックス構造や部分文字列インデックスと密接に関連している。特定の文字列のサフィックスオートマトンが与えられれば、圧縮と再帰トラバーサルによって線形時間でサフィックスツリーを構築することができる。^[20]のサフィックスオートマトンと反転した文字列のサフィックスツリーを切り替えるために、同様の変換が両方向に可能である。^[18]これ以外にも、トライによって与えられた文字列の集合に対するオートマトンを構築するためのいくつかの一般化が開発された。^[8]圧縮サフィックスオートメーション（CDAWG）^{[7]は、スライディングウィンドウ上でオートマトンの構造を維持する。 [} 21]は、双方向にオートマトンを構築し、文字列の先頭と末尾の両方に文字を挿入できるようにする。[ ^22] ${\displaystyle S}$ ${\displaystyle S^{R}}$

短縮サフィックスオートマトン

すでに述べたように、コンパクトサフィックスオートマトンは、通常のサフィックスオートマトンのコンパクト化（非最終であり、正確に1つの出力アークを持つ状態を削除することによって）とサフィックスツリーの最小化の両方によって得られます。通常のサフィックスオートマトンと同様に、コンパクトサフィックスオートマトンの状態は明示的に定義できます。単語の双方向拡張は 、内のすべての出現の前に が、後に が続くような最長の単語です。左拡張と右拡張の観点から見ると、双方向拡張は右拡張の左拡張、または左拡張の右拡張（つまり ）を意味します。双方向拡張の観点から見ると、コンパクトオートマトンは次のように定義されます。^[15] ${\displaystyle {\overset {\scriptstyle {\longleftrightarrow }}{\gamma }}}$ ${\displaystyle \gamma }$ ${\displaystyle \omega =\beta \gamma \alpha }$ ${\displaystyle \gamma }$ ${\displaystyle S}$ ${\displaystyle \beta }$ ${\displaystyle \alpha }$ ${\textstyle {\overset {\scriptstyle \longleftrightarrow }{\gamma }}={\overset {\scriptstyle \leftarrow }{\overset {\rightarrow }{\gamma }}}={\overset {\rightarrow }{\overset {\scriptstyle \leftarrow }{\gamma }}}}$

定理—単語の圧縮接尾辞オートマトンがペアによって定義されます。ここで、 ${\displaystyle S}$ ${\displaystyle (V,E)}$

• ${\displaystyle V=\{{\overleftrightarrow {\omega }}:\omega \in \Sigma ^{*}\}}$オートマトン状態の集合です。
• ${\displaystyle E=\{({\overleftrightarrow {\omega }},x\alpha ,{\overleftrightarrow {\omega x}}):x\in \Sigma ,\alpha \in \Sigma ^{*},{\overleftrightarrow {\omega x}}={\overleftrightarrow {\omega }}x\alpha \}}$オートマトン遷移のセットです。

双方向の拡張により、コンパクト オートマトンが同じ状態であると認識する単語の集合を定義する同値関係が誘導されます。 この同値関係はによって定義される関係の推移閉包であり、関係 （サフィックス ツリーの最小化）を介して同値な接尾辞ツリーの頂点を接着することと、関係（サフィックス オートマトンをコンパクト化）を介して同値な接尾辞オートマトンの状態を接着することの両方によって、コンパクト オートマトンが得られるという事実が強調されます。^[23]単語およびが同じ右拡張を持ち、単語および が同じ左拡張を持つ場合、累積的にすべての文字列、および は同じ双方向拡張を持ちます。 同時に、およびの左拡張と右拡張のどちらも一致しない場合があります。 例として、 、およびを取り、その左拡張と右拡張が次のとおりであるものとします。、ですが、および です。とはいえ、一方向拡張の同値関係はネストされた接頭辞または接尾辞の連続的な連鎖によって形成されるのに対し、双方向拡張の同値関係はより複雑であり、確実に結論付けられることは、同じ双方向拡張を持つ文字列は同じ双方向拡張を持つ最長文字列の部分文字列であるということだけです。ただし、空でない部分文字列が共通に存在しないことさえあります。この関係の同値類の総数はを超えないため、長さ の文字列の圧縮接尾辞オートマトンには最大で の状態があります。このようなオートマトンにおける遷移の数は最大で です。^[15] ${\textstyle {\overset {\scriptstyle \longleftrightarrow }{\alpha }}={\overset {\scriptstyle \longleftrightarrow }{\beta }}}$ ${\textstyle ({\overset {\scriptstyle {\rightarrow }}{\alpha \,}}={\overset {\scriptstyle {\rightarrow }}{\beta \,}})\vee ({\overset {\scriptstyle {\leftarrow }}{\alpha }}={\overset {\scriptstyle {\leftarrow }}{\beta }})}$ ${\displaystyle {\overset {\scriptstyle {\leftarrow }}{\alpha }}={\overset {\scriptstyle {\leftarrow }}{\beta }}}$ ${\displaystyle {\overset {\scriptstyle {\rightarrow }}{\alpha \,}}={\overset {\scriptstyle {\rightarrow }}{\beta \,}}}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$ ${\displaystyle \alpha }$ ${\displaystyle \gamma }$ ${\displaystyle S=\beta =ab}$ ${\displaystyle \alpha =a}$ ${\displaystyle \gamma =b}$ ${\displaystyle {\overset {\scriptstyle {\rightarrow }}{\alpha \,}}={\overset {\scriptstyle {\rightarrow }}{\beta \,}}=ab={\overset {\scriptstyle {\leftarrow }}{\beta }}={\overset {\scriptstyle {\leftarrow }}{\gamma }}}$ ${\displaystyle {\overset {\scriptstyle {\rightarrow }}{\gamma \,}}=b}$ ${\displaystyle {\overset {\scriptstyle {\leftarrow }}{\alpha }}=a}$ ${\displaystyle n+1}$ ${\displaystyle n}$ ${\displaystyle n+1}$ ${\displaystyle 2n-2}$

複数の文字列の接尾辞オートマトン

単語の集合 を考えてみましょう。集合に含まれるすべての単語の接尾辞によって構成される言語を認識する接尾辞オートマトンを一般化して構築することが可能です。このようなオートマトンにおける状態と遷移の数に関する制約は、 と置けば単一単語オートマトンの場合と同じになります。^[23]このアルゴリズムは単一単語オートマトンの構築と似ていますが、状態の代わりに、関数add_letter が単語の集合から集合 への遷移を仮定して、単語に対応する状態を処理します。^{[24] [25]} ${\displaystyle T=\{S_{1},S_{2},\dots ,S_{k}\}}$ ${\displaystyle n=|S_{1}|+|S_{2}|+\dots +|S_{k}|}$ ${\displaystyle last}$ ${\displaystyle \omega _{i}}$ ${\displaystyle \{\omega _{1},\dots ,\omega _{i},\dots ,\omega _{k}\}}$ ${\displaystyle \{\omega _{1},\dots ,\omega _{i}x,\dots ,\omega _{k}\}}$

この考え方は、が明示的に与えられず、代わりに頂点を持つプレフィックスツリーによって与えられる場合にも一般化される。 Mohriらは、このようなオートマトンの最大数は であり、そのサイズから線形時間で構築できることを示した。同時に、このようなオートマトンにおける遷移の数は に達することがあり、たとえばアルファベット上の単語の集合では、単語の合計長は に等しく、対応する接尾辞トライの頂点の数は に等しく、対応する接尾辞オートマトンが状態と遷移から構成される。 Mohri が提案したアルゴリズムは、主に複数の文字列のオートマトンを構築するための一般的なアルゴリズムを繰り返しているが、単語を 1 つずつ増やすのではなく、幅優先探索順序でトライを走査し、走査中に新しい文字に出会うたびにその文字を追加することで、線形計算量の償却を保証する。^[26] ${\displaystyle T}$ ${\displaystyle Q}$ ${\displaystyle 2Q-2}$ ${\displaystyle O(Q|\Sigma |)}$ ${\displaystyle T=\{\sigma _{1},a\sigma _{1},a^{2}\sigma _{1},\dots ,a^{n}\sigma _{1},a^{n}\sigma _{2},\dots ,a^{n}\sigma _{k}\}}$ ${\displaystyle \Sigma =\{a,\sigma _{1},\dots ,\sigma _{k}\}}$ ${\textstyle O(n^{2}+nk)}$ ${\displaystyle O(n+k)}$ ${\displaystyle O(n+k)}$ ${\displaystyle O(nk)}$

引き戸

LZ77やRLEなどの一部の圧縮アルゴリズムでは、文字列全体ではなく、文字列の更新中にその最後の文字だけサフィックスオートマトンまたは類似の構造を格納することでメリットが得られる場合があります。これは、圧縮データは通常、表現的に大きく、メモリの使用は望ましくないためです。 1985年に、ジャネット・ブルーマーは、文字が独立して均一に分布していると仮定して、最悪の場合および平均でサイズ のスライディングウィンドウにサフィックスオートマトンを維持するアルゴリズムを考案しました。彼女はまた、複雑性は改善できないことも示しました。 が複数の単語の連結として解釈される場合、サイズ のウィンドウの状態数はの順序のジャンプで頻繁に変化し、通常のサフィックスオートマトンに対する の理論的改善さえも不可能になります。^[27] ${\displaystyle k}$ ${\displaystyle O(n)}$ ${\displaystyle k}$ ${\displaystyle O(nk)}$ ${\displaystyle O(n\log k)}$ ${\displaystyle O(nk)}$ ${\displaystyle (ab)^{m}c(ab)^{m}d}$ ${\displaystyle k=6m+2}$ ${\displaystyle k}$ ${\displaystyle m}$ ${\displaystyle O(nk)}$

サフィックスツリーについても同様であるはずです。なぜなら、サフィックスツリーの頂点は反転された文字列のサフィックスオートマトンの状態に対応するからです。しかし、この問題は、文字列全体のサフィックスに対応するすべての頂点を明示的に格納するのではなく、少なくとも2つの出力エッジを持つ頂点のみを格納することで解決できます。このタスクのためのMcCreightのサフィックスツリー構築アルゴリズムのバリエーションは、1989年にEdward FialaとDaniel Greeneによって提案されました。^[28]数年後、Jesper LarssonはUkkonenのアルゴリズムのバリエーションで同様の結果を得ました。 ^{[29] [30]}サフィックスツリーとサフィックスオートマトンの両方の特性を吸収するコンパクトサフィックスオートマトンのためのこのようなアルゴリズムの存在は、2008年にMartin SenftとTomasz Dvorakによって、アルファベットのサイズが少なくとも2の場合、不可能であることが発見されるまで、長い間未解決の問題でした。^[31]

この障害を克服する一つの方法は、ウィンドウ幅を のままで少し変化させることである。これは、2004年に稲永らが提案した近似アルゴリズムによって実現できるかもしれない。このアルゴリズムでサフィックスオートマトンが構築されるウィンドウの長さは であることは保証されないが、アルゴリズム全体の計算量が線形である限り、 から までであることが保証される。 ^[32] ${\displaystyle O(k)}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle 2k+1}$

アプリケーション

文字列の接尾辞オートマトンは以下の問題を解くのに使用できる: ^{[33] [34]} ${\displaystyle S}$

• オンラインで異なる部分文字列の数を数えると、 ${\displaystyle S}$ ${\displaystyle O(|S|)}$
• で少なくとも2回出現する最長の部分文字列を見つける。 ${\displaystyle S}$ ${\displaystyle O(|S|)}$
• との最長共通部分文字列を見つけると、 ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle O(|T|)}$
• の出現回数を数えると、 ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle O(|T|)}$
• 内ののすべての出現を検索します。 は出現回数です。 ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle O(|T|+k)}$ ${\displaystyle k}$

ここでは、の接尾辞オートマトンが構築された後に入力に与えられるものと仮定する。^[33] ${\displaystyle T}$ ${\displaystyle S}$

サフィックスオートマトンはまた、データ圧縮^[35] 、音楽検索^{[36] [37]}、ゲノム配列のマッチングにも使用されています。^[38]

参考文献

1. Crochemore & Vérin (1997)、p. 192
2. Weiner (1973)
3. プラット（1973）
4. スリセンコ（1983）
5. ブルーマー他 (1984)、109ページ
6. チェン＆セイフェラス（1985）、97ページ
7. Blumer et al. (1987)、p. 578
8. 稲永ら。 (2001)、p. 1
9. Crochemore & Hancart (1997)、3～6ページ
10. セレブリャコフら。 (2006)、50–54 ページ
11. Рубцов (2019)、89–94 ページ
12. ホップクロフト＆ウルマン（1979）、65～68頁
13. Blumer et al. (1984)、111–114ページ
14. クロシュモア＆ハンカート（1997年）、27～31ページ
15. 稲永ら。 (2005)、159–162 ページ
16. Rubinchik & Shur (2018)、1–2 ページ
17. 稲永ら。 (2005)、156–158 ページ
18. 藤重ほか(2016)、1–3 ページ
19. Crochemore & Hancart (1997)、31–36 ページ
20. Паращенко (2007)、19–22 ページ
21. ブルーマー（1987）、451ページ
22. 稲永（2003）、1ページ
23. Blumer et al. (1987)、pp. 585–588
24. ブルーマー他 (1987)、588-589頁
25. ブルーマー他 (1987)、593ページ
26. 毛利、モレノ、ワインスタイン (2009)、pp. 3558–3560
27. ブルーマー（1987年）、461–465ページ
28. フィアラとグリーン (1989)、p. 490
29. ラーソン（1996）
30. Brodnik & Jekovec (2018)、p. 1
31. ゼンフト & ドヴォルザーク (2008)、p. 109
32. 稲永ら（2004）
33. Crochemore & Hancart (1997)、36～39ページ
34. クロシュモア＆ハンカート（1997年）、39～41ページ
35. 山本ら。 (2014)、p. 675
36. Crochemoreら。 (2003)、p. 211
37. 毛利、モレノ、ワインスタイン (2009)、p. 3553
38. ファロ（2016年）、145ページ

参考文献

• Blumer, A.; Blumer, J.; Ehrenfeucht, A.; Haussler, D.; McConnell, R. (1984). 「単語のすべての部分語の集合に対する最小DFAをオンラインで線形時間で構築する」.オートマトン、言語、プログラミング. コンピュータサイエンス講義ノート. 第172巻. pp.  109– 118. doi :10.1007/3-540-13345-3_9. ISBN 978-3-540-13345-2。
• Blumer, A.; Blumer, J.; Haussler, D.; McConnell, R.; Ehrenfeucht, A. (1987). 「効率的なテキスト検索と分析のための完全転置ファイル」Journal of the ACM . 34 (3): 578– 595. doi :10.1145/28869.28873. Zbl  1433.68118.
• ブルーマー、ジャネット A. (1987). 「ウィンドウ内のDAWGはどれくらいか？ 有向非巡回ワードグラフのための移動ウィンドウアルゴリズム」.アルゴリズムジャーナル. 8 (4): 451– 469. doi :10.1016/0196-6774(87)90045-9. Zbl  0636.68109.
• アンドレイ・ブロドニク。イェコヴェツ、マテヴシュ (2018)。 「スライディングサフィックスツリー」。アルゴリズム。11 (8): 118.arXiv : 1801.07449。土井：10.3390/A11080118。Zbl  1458.68043。
• Chen, MT; Seiferas, Joel (1985). 「効率的かつエレガントなサブワードツリー構築」.単語の組み合わせアルゴリズム. pp.  97– 107. doi :10.1007/978-3-642-82456-2_7. ISBN 978-3-642-82458-6。
• クロシュモア, マキシム; ハンカート, クリストフ (1997). 「パターンマッチングのためのオートマトン」.形式言語ハンドブック. pp.  399– 462. doi :10.1007/978-3-662-07675-0_9. ISBN 978-3-642-08230-6。
• クロシュモア、マキシム、ヴェラン、ルノー (1997). 「コンパクトな有向非巡回語グラフについて」.論理とコンピュータサイエンスにおける構造. コンピュータサイエンス講義ノート. 第1261巻. pp.  192– 211. doi :10.1007/3-540-63246-8_12. ISBN 978-3-540-63246-7。
• クロシュモア、マキシム。イリオプロス、コスタス S.ナバロ、ゴンサロ。ピンゾン、ヨアン J. (2003)。 「音楽検索における (δ,γ) マッチングのためのビット並列サフィックス オートマトン アプローチ」。文字列の処理と情報の取得。コンピューターサイエンスの講義ノート。 Vol. 2857. pp.  211–223 .土井:10.1007/978-3-540-39984-1_16。ISBN 978-3-540-20177-9。
• セレブリャコフ、ウラジミール。ガロチキン、マクシム・パブロヴィッチ。フルジアン、メラン・ガビブラエヴィッチ。ゴンチャール、ドミトリー・ルスラノヴィッチ（2006）。 Теория и реализация языков программирования: Учебное пособие (PDF) (ロシア語)。モスクワ：MZプレス。ISBN 5-94073-094-9。
• ファロ、シモーネ (2016). 「ゲノム配列の完全一致のための高速アルゴリズムの評価と改良」.計算生物学のためのアルゴリズム. コンピュータサイエンス講義ノート. 第9702巻. pp.  145– 157. doi :10.1007/978-3-319-38827-4_12. ISBN 978-3-319-38826-7。
• Fiala, ER; Greene, DH (1989). 「有限ウィンドウによるデータ圧縮」Communications of the ACM . 32 (4): 490– 505. doi :10.1145/63334.63341.
• 藤重 雄太; 辻丸 由紀; 稲永 俊介; 坂内 秀夫; 武田 正之 (2016). 「整数アルファベットに対するDAWGと極小不在語の線形時間計算」.第41回国際計算機科学数学基礎シンポジウム (MFCS 2016) . ライプニッツ国際情報科学会議. ダグストゥール城 – ライプニッツ情報科学センター. pp. 38:1–38:14. doi : 10.4230/LIPICS.MFCS.2016.38 . Zbl  1398.68703.
• ホップクロフト、ジョン・エドワード、ウルマン、ジェフリー・デイヴィッド (1979). 『オートマトン理論、言語、計算入門』（第1版）. マサチューセッツ州: アディソン・ウェスレー. ISBN 978-81-7808-347-6. OL  9082218M.
• 稲永俊介 (2003). 「サフィックスツリーの双方向構築」(PDF) . Nordic Journal of Computing . 10 (1): 52– 67. CiteSeerX  10.1.1.100.8726 .
• 稲永俊介；星野宏正；篠原あゆみ;武田 正幸；有川節夫；マウリ、ジャンカルロ。パヴェシ、ジュリオ (2005)。 「コンパクトな有向非巡回ワードグラフのオンライン構築」。離散応用数学。146 (2): 156–179。土井:10.1016/J.DAM.2004.04.012。Zbl  1084.68137。
• 稲永俊介；星野宏正；篠原あゆみ;武田 正幸；有川節夫（2001）。 「トライのためのCDAWGの構築」（PDF）。プラハ弦学カンファレンス。議事録。ページ 37 ～ 48。CiteSeerX  10.1.1.24.2637。
• 稲永俊介；篠原あゆみ;武田 正幸；有川節夫（2004）。 「スライディング ウィンドウ用のコンパクトな有向非巡回ワード グラフ」。離散アルゴリズムのジャーナル。2 : 33–51。土井:10.1016/S1570-8667(03)00064-9。Zbl  1118.68755。
• Larsson, NJ (1996). 「サフィックスツリーのデータ圧縮への拡張適用」.データ圧縮会議 - DCC '96 議事録. pp.  190– 199. doi :10.1109/DCC.1996.488324. ISBN 0-8186-7358-3。
• Mohri, Mehryar; Moreno, Pedro; Weinstein, Eugene (2009). 「一般サフィックスオートマトン構築アルゴリズムと空間境界」.理論計算機科学. 410 (37): 3553– 3562. doi :10.1016/J.TCS.2009.03.034. Zbl  1194.68143.
• Паращенко、Дмитрий А。 (2007)。 Обработка строк на основе суффиксных автоматов (PDF) (ロシア語)。サンクトペテルブルク: ITMO 大学。
• プラット、ヴォーン・ロナルド (1973).ウィーナー反復検出法の改良と応用. OCLC  726598262.
• Рубцов、Александр Александрович（2019）。 Заметки и задачи о регулярных языках и конечных автоматах (PDF) (ロシア語)。モスクワ: モスクワ物理工科大学。ISBN 978-5-7417-0702-9。
• ルビンチク、ミハイル。シュール、アーセニー M. (2018)。 「EERTRE: 文字列内の回文を処理するための効率的なデータ構造」。欧州組合せ論ジャーナル。68 : 249–265.arXiv : 1506.04862 。​​土井：10.1016/J.EJC.2017.07.021。Zbl  1374.68131。
• Senft, Martin; Dvořák, Tomáš (2008). 「Sliding CDAWG Perfection」.文字列処理と情報検索. コンピュータサイエンス講義ノート. 第5280巻. pp.  109– 120. doi :10.1007/978-3-540-89097-3_12. ISBN 978-3-540-89096-6。
• Slisenko, AO (1983). 「周期性の検出とリアルタイム文字列マッチング」. Journal of Soviet Mathematics . 22 (3): 1316– 1387. doi :10.1007/BF01084395. Zbl  0509.68043.
• ワイナー、ピーター (1973). 「線形パターンマッチングアルゴリズム」.第14回スイッチング・オートマトン理論シンポジウム (SWAT 1973) . pp.  1– 11. doi :10.1109/SWAT.1973.13.
• 山本 純一; 井 智宏; 坂内 秀夫; 稲永 俊介; 武田 正之 (2014). 「より高速でコンパクトなオンラインLempel-Ziv分解」.第31回国際計算機科学理論シンポジウム (STACS 2014) . ライプニッツ国際情報科学会議. ダグストゥール城 – ライプニッツ情報科学センター. pp.  675– 686. doi : 10.4230/LIPICS.STACS.2014.675 . Zbl  1359.68341.

外部リンク

• ウィキメディア・コモンズのサフィックス・オートマトン関連メディア
• E-Maxxアルゴリズムに関する英語の接尾辞オートマトン記事

Retrieved from "https://en.wikipedia.org/w/index.php?title=Suffix_automaton&oldid=1315785893"