ダブル配列による有限状態機械の記憶アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
有限状態機械(finite state machine)のふるまいは非常にシンプルであり,コンパイラの語い解析,文献検索,スペリング検査,テキスト編集などの単語のマッチングとか,順序回路,パーサの有限制御部など数多くのモデルとして応用されている.有限状態機械をインプリメントする場合,状態遷移に関する情報(goto関数と呼ぶ)を時間的かつ空間的に如何に効率的よく記憶検索するかが重要な課題となってくる.青江らは,パターンマッチングマシンのgoto関数をダブル配列(double-array)により実現することを提案した.ダブル配列の遷移アクセス時間は,O(1)となるので,非常に高速である.しかし,青江らの議論した状態遷移表はパターンマッチングマシンのものに限定されていたので,一般の有限状態機械の遷移表には適応できなかった.従って,本稿の目的は,ダブル配列法の適用可能な範囲を一般の有限状態機械の状態遷移表に拡張することにある.
- 一般社団法人情報処理学会の論文
- 1992-09-28
著者
関連論文
- 各個人のプロファイルを用いたメイル文書のフィルタリング手法
- 分野連想語の出現位置に基づく話題分野の特定手法
- 転置ファイルによる大規模 n-gram データの検索システム
- 転置ファイルによる大規模 n-gram データの検索システム
- グラフ構造に対する効率的記憶検索法
- 文書レイアウトにおける自動図表配置手法
- ストリングパターンマッチングマシンの動的構成法
- ストリングパターンマッチングマシンにおける検索キー追加方法
- LRパーサを用いた文字列置換アルゴリズム
- HTML形式の表構造に対する一索引化手法
- 定型表現を利用した効率的な形態素解析の実現
- 二つのトライを用いた辞書検索アルゴリズム
- 二つのトライを用いた自然言語辞書検索技法
- 知識表現モデルMERMにおける心理現象の一表現法
- ダブル配列による有限状態機械の記憶アルゴリズム
- 分類知識表現を用いたキー検索アルゴリズムの決定法
- 拡張ハッシングにおけるディレクトリの圧縮アルゴリズム