紀要論文 決定性有限オートマトンに基づく正規表現エンジンの実現

増田, 拓也||マスダ, タクヤ||Masuda, Takuya  ,  奥居, 哲||オクイ, サトシ||Okui, Satoshi

23pp.3 - 16 , 2016-03 , 中部大学情報科学研究所
ISSN:13402935
内容記述
決定性有限オートマトン(DFA)に基づく正規表現ライブラリのC++による試験実装を踏まえ,実装上の選択が時間的・空間的な効率にどのような影響を及ぼすかを検討した.DFAの構築と照合に要するリソースの多くは,DFAの基となる非決定性有限オートマトン(NFA)の状態数と文字の種類の二つによって限定される.このことに着目し,NFAの状態数に依存するリソースを可能な限り事前に確保する工夫を凝らしたところ,ε閉包に関する処理の時間的・空間的なコストが低減された.また,データ構造を選択する場合,特にC++が提供するコンテナ(STL)を利用する場合には,一般的に効率がよいとされているハッシュ表や木構造のものは極力避け,動的配列を採用した.リソースのサイズが比較的小さい場合,あるいは固定長である場合には,キャッシュヒットの効率がよい動的配列が有効であることが分かった.一方で,上述の工夫は,(ε閉包に関する処理を除いた)DFAの状態数に依存する処理に対しては効果がなく,さらなる改良には,メモリープールやアロケータを導入する必要があることがプロファイリング結果から明らかになった.
本文を読む

http://opac.bliss.chubu.ac.jp/e-Lib/bdyview.do?bodyid=XC16000151&elmid=Body&lfname=link/E02_023_003.pdf

このアイテムのアクセス数:  回

その他の情報