有限状態automatonの構成

概要

長い文字列を左から読むとき、読んだ全文が必要とは限らない。たとえば aba の出現を見つけたいなら、過去の全文よりも「次の文字とつながりそうな末尾」が重要になる。この情報を有限個の状態へまとめ、各文字を読んだ後の状態と、そのとき起きる事象を表にしたものが有限状態オートマトンである。

この単元では、何を同じ状態とみなせるかを決め、入力され得るすべての文字に対する遷移を作る。連続部分文字列と、文字を飛ばして選ぶ部分列では、覚える情報がどう違うかも扱う。作った状態グラフは、出現検出だけでなく、禁止語を避ける数え上げや得点の最適化にも使える。

考え方

次の一致につながるものは、過去のどこにあるか

語 aba が連続して現れるかを調べよう。xxab を読んだ時点では、末尾の ab が次の a を待っている。先頭の xx は、この一致を完成させることにも、その後の一致を始めることにも関わらない。

一方、xxa と xxab は同じ状態にできない。次が a なら、前者はまだ未完成、後者は aba の完成になるからだ。同じ続きを与えたときの振る舞いが違うものは、区別しておく必要がある。

固定した非空の語を PP、その長さを mm とする。prefix(接頭辞)は先頭からの連続部分、suffix(接尾辞)は末尾までの連続部分で、空文字列も含める。読んだ列のsuffixのうち、PP のprefixにもなっている最長の長さを状態 qq とする。P=abaP=\texttt{aba} なら状態は0、1、2、3で、それぞれ空、a、ab、aba に対応する。

最長の候補しか保存しなくてよい理由も確認する。新しい文字の追加で長さ r>0r>0 のprefixが末尾に一致するなら、その最後の一文字を除いた長さ r−1r-1 のprefixは、追加前のsuffixだった。したがって r−1≤qr-1\leq q であり、その候補は保存した最長prefixの末尾にも存在する。古い全文を読み返さなくても、保存した部分からすべての次候補を復元できる。

一致しなかったときも、ゼロへ戻るとは限らない

aba を探して aa を読んだ場合を考える。二文字目の a は期待した b ではないが、その a 自身が新しい一致の始まりになる。従って状態は1のままだ。ab に b を足して abb にすると、有効な末尾はなく状態0になる。

入力文字を a,b,c とした完全な遷移表は次になる。表の状態は「今の末尾でどこまで一致しているか」を表す。

状態 qqa を読むb を読むc を読む
0:空100
1:a120
2:ab3(出現)00
3:aba120

完成した状態3の後も読むことがある。ababa を追うと状態は 1,2,3,2,31,2,3,2,3 となり、3文字目と5文字目で二回出現する。完成後に無条件で0へ戻すと、重なった後半の出現を見逃す。表では a,b 以外の文字はすべて c と同じ遷移になるが、このような同一視も各文字の振る舞いを確認してから行う。

一般の遷移を作るには、状態に対応する PP のprefixへ一文字を足し、そのsuffixであるprefixの最長長を求めればよい。短い語なら直接比較で十分だ。長い語では、最長の候補から次に短い候補へ戻る関係をKMPのprefix functionで前計算できる。

添字を0始まりとし、π[i]\pi[i] を PP の先頭 i+1i+1 文字について、全体より短いprefixでもsuffixでもあるものの最長長とする。不一致なら q←π[q−1]q\leftarrow\pi[q-1] へ戻って比較し直す。q=0q=0 でも一致しなければ0のままにする。q=mq=m では次の文字を比較する前に π[m−1]\pi[m-1] へ戻すので、存在しない P[m]P[m] を読まない。aba の完成後なら、末尾の a に当たる長さ1を残す。

飛ばしてよい部分列では、進行は後退しない

同じ aba を、今度は部分列として含むか調べる。ac を読んだ後も、選んだ a は捨てなくてよい。次の b、その後の a を待ち続けられる。連続性が必要なときと異なり、余分な文字は単に飛ばせる。

この場合、qq は「部分列として作れた最長prefixの長さ」とする。q<mq<m で次の文字が P[q]P[q] なら一つ進め、それ以外では維持する。完成した q=mq=m は以後そのままにする。aba に対する表は次である。

状態 qqa を読むb を読むc を読む
0100
1121
2322
3333

必要な文字を最も早い位置で選んでも、以後に使える位置は狭くならない。また、一文字の追加で新たに作れるprefixは高々一文字分しか伸びないので、この更新で最長長を保てる。

これは「含むか」の判定に十分な状態である。部分列の選び方を数えるなら、同じprefixを作る複数の選択も数える必要があり、最長長だけでは足りない。状態の十分性は、何を求めるかと組にして判断する。

遷移先と、今回起きた事象を分ける

出現検出の表ができたら、それを何に使うかを決める。

  • 禁止語を避けたい。 完成する遷移を通さない。
  • 一度でも出現した列を数えたい。 一致長とは別に既出フラグを持ち、完成時に真にして以後も維持する。
  • 出現回数を数えたい。 完成のたびに一回を足し、次の一致も探し続ける。
  • 出現に得点を付けたい。 完成した語の得点の和を辺重みにする。

例えば abac の最後では aba の一致長は0へ戻るが、過去に出現した事実まで消えるわけではない。一致長、既出の事実、累積回数は、それぞれ役割が違う。

長さ LL 以下の短い語を多数扱うときは、末尾 L−1L-1 文字そのものを状態にする方法もある。一文字の追加で完成する語を、その新しい右端だけで列挙できるからだ。文字種数を σ\sigma とすると、末尾が十分長い状態は σL−1\sigma^{L-1} 通り。開始直後の短い末尾も別状態かダミー記号で表す。ABC264 Gでは長さ3以下の語への得点を、この方法で辺重みに変える。

有限の遷移表から、数え上げや最適化へ進む

長さ ii の列で状態 qq へ来た個数を dpi[q]dp_i[q] とする。空列の開始状態に1、他に0を置く。各状態から各文字を選び、合法ならその遷移先の次配列へ個数を足す。異なる文字が同じ状態へ進んでも、出来上がる列は別なので別々に加える。各列は「最後の一文字」と「それを除いた列」に一意に分けられ、過不足なく数えられる。

次の配列は各長さで0に戻し、更新中は旧配列だけを読む。最後に受理する状態の個数を足す。禁止語回避なら残る全状態、出現を要求するなら既出フラグが真の状態である。最大得点なら同じ遷移で加算の代わりに最大値を取り、到達不能を区別する。

長さが大きい場合も、まずこの一段の意味を決める。遷移が位置によらず同じなら行列遷移を累乗できる。ABC305 Gは短い禁止語の回避をこの形へつなぐ例である。長さ無制限の最大化なら、到達可能な正閉路の有無が問題になる。状態が有限でも、歩行は何度でも状態を再訪できるためだ。

複数条件を課すときは状態の組を作れるが、状態数は積で増える。ABC301 Fのような文字の種類の情報を含む問題では、一致の進行だけで十分か、対称性を使って種類の情報をまとめられるかまで検討する。既成のオートマトンへ当てはめる前に、未来の判定に必要な情報を洗い出すことが出発点になる。

成立条件と計算量

状態の正当化では、同じ状態の任意の二履歴について、次の各文字の合法性・遷移先・追加得点が一致することを確かめる。これが成り立てば一文字ずつ繰り返し、任意の続きについて同じ振る舞いになる。開始状態と最後に受理する条件も定義の一部である。

単一語の長さを mm、最終的な状態数を SS、文字種数を σ\sigma、表の構築時間を BB とする。部分列の表は各組を定数時間で決められ、O(mσ)O(m\sigma) 時間。部分文字列の表を各候補長の文字比較で作る素朴な方法は、一遷移に O(m2)O(m^2)、全体に O(m3σ)O(m^3\sigma) かかり得る。KMPの π\pi を O(m)O(m) で作り、状態の短い順に、不一致先の計算済み遷移を参照すれば、表を O(mσ)O(m\sigma) で作れる。全遷移で独立に戻り続ける方法とは区別する。

表を作った後、与えられた長さ NN の一列を読む処理は O(B+N)O(B+N)、長さ NN の全列を数えるDPは O(B+NSσ)O(B+NS\sigma) 時間。表に O(Sσ)O(S\sigma)、二層DPに O(S)O(S)、語とprefix functionに O(m)O(m) の領域を使う。入力列を保存すればさらに O(N)O(N) 必要である。個数の加算は固定の法で定数時間とする。

複数語で末尾を直接持つ方法は LL に指数的なので、最長語長と文字種数を先に確認する。長い複数語のsuffixを共有する方法はAho–Corasickで学ぶ。直積した場合は、構成後の状態数で計算量を見積もる。

長さ0の入力では初期状態のまま終わる。非空の語を避ける空列は一通り、含む空列は0通りとなる。空の語を探す問題では一致の定義が変わるため、ここでの非空語の構成をそのまま使わない。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

前提・学習成果・出典

習得対象の目安: 青色(1600–1999)。suffixや進行状況を状態に選び、全ての文字に対する遷移を構成する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 禁止・要求patternを有限状態へ圧縮する。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-finite-pattern-automaton

習得する技能

  • 未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: Aho–Corasick、automaton上のDP・行列遷移、非決定性automatonのsubset construction、Suffix Automatonで部分文字列集合を表す。

文字を一つ加えた後の未来の挙動が等しい履歴を有限状態へ同値化し、pattern suffix・部分列進行・圧縮DP rowなどから全文字の完全遷移表を構築する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

このUnitでは扱わないもの

  • 有限状態automatonの構成の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠