メモ化を用いた正規表現エンジンの実装

• Item type: Trans(1)
• 公開日: 2009-01-27
• タイトル: メモ化を用いた正規表現エンジンの実装
• タイトル / 言語: en
• タイトル: Implementation of Regular Expression Engine Using Memoization
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 発表概要
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 筑波大学大学院システム情報工学研究科
• 著者所属: 筑波大学大学院システム情報工学研究科
• 著者所属: 筑波大学大学院システム情報工学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of System and Information Engineering, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): Graduate School of System and Information Engineering, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): Graduate School of System and Information Engineering, University of Tsukuba
• 著者名: 須賀功太; 前田, 敦司; 山口, 喜教
• 著者名(英): Kota, Suga; Atsushi, Maeda; Yoshinori, Yamaguti
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 正規表現は文字列処理の基本的なツールとして，言語処理系やテキスト処理アプリケーションに広く用いられている．正規表現と入力文字列とのマッチング処理の実装には，正規表現から構成した非決定性有限オートマトン（NFA）を用い，バックトラッキングを用いてNFAの動作をシミュレートするアルゴリズムや，NFAを決定性有限オートマトン（DFA）に変換してバックトラッキングなしでマッチングを行うアルゴリズムが広く用いられている．NFAとバックトラッキングを用いる実装では，マッチングに要する時間的計算量が最悪で指数関数的になるという問題があり，一方でDFAを用いる実装では，事前にDFAを構成するための空間的・時間的計算量が指数関数的になるという問題点がある．NFAとバックトラッキングを用いる実装にメモ化を組み合わせて，最悪時の時間計算量を改善する提案がなされている．この場合の空間計算量は，正規表現パターン長と入力テキストサイズの積に比例する．また，NFAをバックトラッキングなしで（幅優先で）シミュレートするアルゴリズムも知られている．本発表では，これらの手法の効率を比較し，メモ化に用いるメモリ領域を削減する手法について考察する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Regular expressions are widely used as a basic tool for programming language implementations and text processing applications. Most implementations of regular-expression matching engine fall into two categories: some implementations construct nondeterministic finite automata (NFAs) from given regular expression and simulate NFAs with backtracking simulation algorithms; others convert NFAs into DFAs and directly simulate them in non-backtracking algorithm. With implementation using NFA and backtracking, the time complexity becomes exponential in the worst case. While DFA-based implementation requires exponential space/time complexity in constructing DFAs. There are proposals for backtracking implementations to incoroprate memoization to improve worst-case time complxity. In this case, space requirement becomes regular expression size times input text size. Non-backtracking simulation algorithm of NFAs are also known. In this presentation, we compare the efficiency of these techniques. Arguments on a technique to reduce memoization space area is also presented.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 2, 号 1, p. 22-22, 発行日 2009-01-27
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会