文献

J-GLOBAL ID：202002226050360993   整理番号：20A0054003

大きな正規表現に対する系列二分決定グラフを用いた効率よい照合手法

著者 (4件)： 瀧澤涼介 (北大 大学院情報科学院) ,  喜田拓也 (北大 大学院情報科学院) ,  有村博紀 (北大 大学院情報科学院) ,  瀧川一学 (理研)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 119  号： 249(COMP2019 18-28)(Web)  ページ： 1-10 (WEB ONLY)  発行年： 2019年10月18日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本発表では,状態数の大きな正規表現に対する効率よいテキスト照合手法を与える.提案手法では,与えられた正規表現と等価な非決定性有限オートマトンの文字ごとの遷移関係を系列BDDで圧縮表現し,系列BDDの演算を用いて遷移計算を効率よく実現する.さらに,正規表現から系列BDDを直接構築する手法を与える.実際のパターンとデータを用いた計算機実験において,提案手法を既存手法と比較した結果,前処理時間と実行時間の両方で提案手法は比較手法に対して高速であった.(著者抄録)

シソーラス用語： *正規表現 ,  非決定性オートマトン ,  *二分決定グラフ ,  比較 ,  *マッチング ,  アルゴリズム ,  移動 ,  実験
準シソーラス用語： BDD【グラフ】 ,  照合 ,  状態遷移 ,  評価実験 ,  文字列照合

分類 (2件)： オートマトン理論  (JB04000O) ,  計算理論  (JB02000A)

引用文献 (12件)：

• Nagayama, shinobu. Synthesis Lectures on Digital Circuits and Systems, Vol. 45, pp. 63-68, 01 2014.
• Ricardo Baeza-Yates and Gaston H. Gonnet. A new approach to text searching. CACM, Vol. 35, No. 10, pp. 74-82, October 1992.
• Lars Brenna, Alan Demers, Johannes Gehrke, Mingsheng Hong, Joel Ossher, Biswanath Panda, Mirek Riedewald, Mohit Thatte, and Walker White. Cayuga: a high-performance event processing engine. In SIGMOD Conference, pp. 1100-1102, 2007.
• Shuhei Denzumi, Ryo Yoshinaka, Hiroki Arimura, and Shin ichi Minato. Sequence binary decision diagram: Minimization, relationship to acyclic automata, and complexities of boolean set operations. Discrete Applied Mathematics, Vol. 212, pp. 61-80, 2016.
• Jeffrey E. F. Friedl 著, 田村勝訳. 詳説正規表現. O’reilly, 2005.

タイトルに関連する用語 (5件)： 正規表現 ,  系列 ,  二分決定グラフ ,  照合 ,  手法