禁止・要求patternを有限状態へ圧縮する
概要
長い文字列を一文字ずつ読むとき、毎回その全体を覚え直す必要はない。次の文字でpattern(探したい文字の並び)が完成するかを決める情報だけを残し、一文字ごとの遷移を作る。この有限状態の仕組みをautomaton(オートマトン)と呼び、文字列の判定や数え上げへ使う。
考え方
独自の小例として、a,b,cからなる文字列でabを避けたいとする。まず、abが連続する部分文字列として現れたら禁止する場合を考える。aを読んだ後は、次のbで完成する。aaを読んだ後も、最後のaだけが次の一致の候補なので同じ状態でよい。一方、acを読んだ後は、間にcが入って連続性が切れ、続けてbを読んでもabはできない。
今度は、文字を飛ばして選べる部分列としてabが現れたら禁止するとする。acの後も、先ほどのaを選べた事実は残る。その後にbが来れば、acbの1文字目と3文字目を選んで完成する。同じ入力でも、部分文字列なら「末尾のどこから一致を続けられるか」、部分列なら「どこまで選べたか」が必要になる。
この違いを一般化すると、二つの履歴をまとめてよいのは、どんな文字列をこの先に付けても、最後に条件を満たすかが同じになるときである。条件を満たすことを受理と呼ぶ。禁止patternの回避だけなら、既に禁止を破った履歴は捨て、安全な履歴の中で次の違反に必要な情報を比べればよい。出現を要求する場合は、末尾の一致が消えても「過去に一度は現れた」という情報を忘れてはいけない。
まず最小の状態数を探すより、保持する情報から「全ての文字の次状態」と「最後の受理判定」が決まることを確かめる。有限状態automatonの構成では、このabの例を一致長と遷移表へ落とし込む。複数patternの末尾一致はAho–Corasick、同時に可能な状態を集合で保持する場合はsubset constructionへ進む。
成立条件と計算量
状態数を 、入力に使う文字の種類数を とする。各状態・各文字から次状態が一意に決まる表を作れば、一つの入力文字列は一文字 、長さ で 時間で読める。表の領域は 。表を作る時間は、一致判定の方法を含めて別に評価する。有限個の状態にできても、状態数が実用的な大きさとは限らない。
長さ の文字列を全て数えるなら、状態は「同じ続きを付けられる履歴の分類」、DP値は「その分類へ来た文字列の個数」である。到達しない状態の個数は0とし、合法な一文字遷移で個数を足す。構築済みの表に対する通常DPは 時間となる。禁止完成を捨てるか、出現履歴を加えて最後に受理状態を選ぶかを決めてから、automaton上のDP・行列遷移へ接続する。
下位単元
- 有限状態automatonの構成 — 青色
- Aho–Corasick — 黄色
- 非決定性automatonのsubset construction — 黄色
問題一覧
この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
導入対象の目安: 青色(1600–1999)。未来の受理条件が同じprefixをまとめ、有限状態へ変換する入口。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 文字列アルゴリズム。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-string-automata
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
このUnitでは扱わないもの
- 数値上限・桁・繰り上がりを状態にする桁DP、および接頭辞一致長だけを求めるKMP・Z法。