接尾辞オートマトン
接尾辞オートマトン（せつびじオートマトン、英: suffix automaton）や有向非巡回文字列グラフ（ゆうこうひじゅんかいもじれつグラフ、英: directed acyclic word graph）とは、接尾辞を効率的に表現するデータ構造。接尾辞木や接尾辞配列と同様に、suffix という文字列に対して構築した場合、suffix, uffix, ffix, fix, ix, x が含まれている事、それ以外が含まれていない事が分かる[1]。文字列の集合 U の接尾辞オートマトンは、Q を U を表現するトライ木のノードすると、最大 2Q - 2 個の状態がある[2]。
接尾辞オートマトンは有限オートマトンの一種である。圧縮接尾辞木と解釈できる。
関連項目
参照
- ^ Navarro, Gonzalo (2001). “A guided tour to approximate string matching”. ACM Computing Surveys 33 (1): 31–88. doi:10.1145/375360.375365. http://repositorio.uchile.cl/bitstream/handle/2250/126168/Navarro_Gonzalo_Guided_tour.pdf.
- ^ Mohri, Mehryar; Moreno, Pedro; Weinstein, Eugene (September 2009). “General suffix automaton construction algorithm and space bounds”. Theoretical Computer Science 410 (37): 3553–3562. doi:10.1016/j.tcs.2009.03.034.
| |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| その他 | |||||||||||||||||
| 配列構造(英) | |||||||||||||||||
| リンク構造(英) | |||||||||||||||||
| 検索構造(英) |
| ||||||||||||||||
| 木構造 |
| ||||||||||||||||
| グラフ構造 | |||||||||||||||||
| 抽象データ型 | |||||||||||||||||
| |||||||||||||||||
- 表示
- 編集
