中部大学附属三浦記念図書館
ログイン
  • 目録検索 目録検索 ▼
  • 利用者サービス 利用者サービス ▼
    • 利用状況の確認
    • ブックマーク
    • お気に入り検索
    • レビュー履歴
    • タグ履歴
    • ILL複写依頼
    • ILL貸借依頼
    • 購入依頼

中部大学附属三浦記念図書館

イメージ

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

増田, 拓也; 奥居, 哲, 2016.03. -- (情報科学リサーチジャーナル ; Vol. 23 (2016.3)). w. <XC16000151>
登録タグ：
登録されているタグはありません
便利機能：
レビューを見る 詳細情報を見る
書誌URL：
イメージ

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

増田, 拓也; 奥居, 哲, 2016.03. -- (情報科学リサーチジャーナル ; Vol. 23 (2016.3)). w. <XC16000151>
登録タグ：
登録されているタグはありません
便利機能：
レビューを見る 詳細情報を見る
書誌URL：

ページリンク
決定性有限オートマトンに基づく正規表現エンジンの実現 (pdf)

書誌詳細

タイトル 決定性有限オートマトンに基づく正規表現エンジンの実現
タイトル(その他) ケッテイセイ ユウゲン オートマトン ニ モトズク セイキ ヒョウゲン エンジン ノ ジツゲン
タイトル(その他) Design Issues in Implementing a Regular Expression Search Engine Based on DFA
作成者 増田, 拓也
マスダ, タクヤ
Masuda, Takuya
作成者 奥居, 哲
オクイ, サトシ
Okui, Satoshi
公開者 中部大学情報科学研究所
本文リンク 決定性有限オートマトンに基づく正規表現エンジンの実現 (pdf)
書誌構造リンク 情報科学リサーチジャーナル <XB16000006> Vol. 23 (2016.3)
ISSN 13402935
雑誌名 情報科学リサーチジャーナル
巻次等 23
開始終了ページ 3-16
発行日 2016.03
内容記述 決定性有限オートマトン(DFA)に基づく正規表現ライブラリのC++による試験実装を踏まえ,実装上の選択が時間的・空間的な効率にどのような影響を及ぼすかを検討した.DFAの構築と照合に要するリソースの多くは,DFAの基となる非決定性有限オートマトン(NFA)の状態数と文字の種類の二つによって限定される.このことに着目し,NFAの状態数に依存するリソースを可能な限り事前に確保する工夫を凝らしたところ,ε閉包に関する処理の時間的・空間的なコストが低減された.また,データ構造を選択する場合,特にC++が提供するコンテナ(STL)を利用する場合には,一般的に効率がよいとされているハッシュ表や木構造のものは極力避け,動的配列を採用した.リソースのサイズが比較的小さい場合,あるいは固定長である場合には,キャッシュヒットの効率がよい動的配列が有効であることが分かった.一方で,上述の工夫は,(ε閉包に関する処理を除いた)DFAの状態数に依存する処理に対しては効果がなく,さらなる改良には,メモリープールやアロケータを導入する必要があることがプロファイリング結果から明らかになった.
登録日 2016.06.14
資源タイプ 論文
資料種別(NIIタイプ) 紀要論文
フォーマット PDFファイル
著者版フラグ publisher
機関名 中部大学
コレクションコード E02_023_003
このページのTOPへ
このページのTOPへ

  • 関連情報

    関連資料

    他の検索サイトで探す

    この書誌のQRコード