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

機関リポジトリ Web Site

書誌事項

タイトル別名
  • ケッテイセイ ユウゲン オートマトン ニ モトズク セイキ ヒョウゲン エンジン ノ ジツゲン
  • Design Issues in Implementing a Regular Expression Search Engine Based on DFA

この論文をさがす

説明

type:論文

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

収録刊行物

詳細情報 詳細情報について

問題の指摘

ページトップへ