logo
iLiswave
home language
markメニュー
mark 総合案内
mark コンテンツ一覧
  
mark バックナンバー
  
mark 関連情報
mark利用者サービス
     ブックマーク
     検索履歴
     レビュー履歴


JAIRO/学術機関リポジトリポータル
CiNii/NII論文情報ナビゲータ
中部大学附属三浦記念図書館
中部大学
mark書誌詳細 print back bookmark history help
mark 論文情報  <XC16000151> Detail Navigation Guide

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


mark
ブックマーク(BM)機能
追加ボタンを押すとブックマークを追加します
add bookmark  
Navigation Guide
mark
マイフォルダ機能
書誌情報をマイフォルダへ登録できます。
登録ボタンを押すと現在表示している書誌をマイフォルダへ登録します。
add  
Navigation Guide
mark
ファイルに保存
現在、表示している情報をファイルに保存します。
ファイルのエンコードを選択し、保存ボタンを押してください。
エンコード :

download  
Navigation Guide

Copyright (C) 中部大学附属三浦記念図書館 2013 All Right Reserved.