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

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

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

オートマトン理論の観点では、サフィックス オートマトンとは、与えられた文字列のサフィックスの集合を認識する最小限の部分的な決定論的有限オートマトンです。サフィックス オートマトンの状態グラフは、有向非巡回ワード グラフ (DAWG) と呼ばれ、この用語は、決定論的非巡回有限状態オートマトンにも使用されることがあります。 ${\displaystyle S=s_{1}s_{2}\dots_{n}}$

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

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

サフィックスオートマトンの概念は、1983年にデンバー大学とコロラド大学ボルダー校のアンセルム・ブルーマー、ジャネット・ブルーマー、アンジェイ・エーレンフォイヒト、デイヴィッド・ハウスラー、ロス・マッコーネルからなる科学者グループによって導入されました^。ただし、同様の概念は、サフィックスツリーと並んでピーター・ワイナー^[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}$

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

たとえば、単語とそのサブワードについては、および が成り立ちます。非公式には、はの出現に続く の終わりまでの単語によって形成され、 はそれらの出現の右側の位置によって形成されます。この例では、要素 は単語 に対応し、単語 は要素 に対応します。 ${\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 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)}$

「プレフィックス ツリー」（または「トライ」）は、ルート付き有向ツリーで、そのツリーの頂点には同じ文字でマークされた 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}$

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

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

長さの文字列の接尾辞オートマトンには、最大で個の状態と最大で 個の遷移があります。これらの境界は、文字列とそれぞれで到達されます。^[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|}$

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

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

現在の単語にを追加した後、が の接尾辞である場合に限り、の右コンテキストが大幅に変化する可能性があります。これは、同値関係 がの改良であることを意味します。言い換えると、の場合、 です。新しい文字を追加した後、 の最大 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}$

これは、（例えば、がにまったく出現せず、 ）の場合、空の右コンテキストに対応する同値クラスのみが分割されることを意味します。 ^[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 }}}$

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

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

全体の手順は次の疑似コードで記述される: ^[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}}$${\displaystyle new\_state()}$${\displaystyle last}$${\displaystyle len}$${\displaystyle link}$${\displaystyle \delta }$

アルゴリズムの複雑さは、オートマトンの遷移を格納するために使用される基礎構造によって異なる場合があります。メモリ割り当てが で行われると仮定すると、メモリ オーバーヘッドを伴うで実装することも、メモリ オーバーヘッドを伴うで実装することもできます。このような複雑さを得るには、償却分析の方法を使用する必要があります。 の値は、サイクルの各反復で厳密に減少しますが、サイクルの最初の反復の後に次の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 }}}}$

双方向拡張は、コンパクトオートマトンが同じ状態であると認識する単語の集合を定義する同値関係を誘導します。 この同値関係はによって定義される関係の推移閉包であり、関係 （サフィックスツリーの最小化）を介して同値な接尾辞ツリーの頂点を接着することと、関係 （サフィックスオートマトンをコンパクト化）を介して同値な接尾辞オートマトンの状態を接着することによってコンパクトオートマトンが得られるという事実を強調しています。^[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}$