Study on speed-up of searching algorithms for regular expressions with boolean operations

布尔运算正则表达式搜索算法加速研究

• 批准号: 18500010
• 负责人: YAMAMOTO Hiroaki
• 金额: $ 2万
• 依托单位: Shinshu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2006
• 资助国家: 日本
• 起止时间: 2006 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18500010/
• 关键词: extended regular expression; pattern matching alucrithm; finite automaton; string matching algorithm; regular expression

Below are results obtained by this research project.1. We developed an extended regular expression matching algorithm based on deterministic finite automata.2. We extended our extended regular expression matching algorithm to solve regular expressions with all boolean operations, and evaluated the performance experimentally.3. We developed a method to generate a compact deterministic finite automaton representation using a dual position automaton, and applied it to matching algorithms.4. We developed an efficient translation algorithm from regular expressions into nondeterministic finite automata. This algorithm can be used in matching algorithms.

本研究项目取得的成果如下： 1．我们开发了一种基于确定性有限自动机的扩展正则表达式匹配算法。 2．我们扩展了扩展的正则表达式匹配算法来解决所有布尔运算的正则表达式，并通过实验评估了性能。 3．我们开发了一种使用双位置自动机生成紧凑确定性有限自动机表示的方法，并将其应用于匹配算法。 4．我们开发了一种从正则表达式到非确定性有限自动机的高效翻译算法。该算法可用于匹配算法。

项目成果

Bit-Parallel Algorithms for Translating Regular Expressions into NFAs

将正则表达式转换为 NFA 的位并行算法

• 发表时间: 2006
• 期刊: IEICE Trans.Inf.& Syst. (accepted)
• 作者: H.Yamamoto;M.Okamoto;T.Miyazaki
• 通讯作者: T.Miyazaki

文字列上のビット並列法を利用した木パターン照合アルゴリズム

在字符串上使用位并行性的树模式匹配算法

• 发表时间: 2008
• 作者: 山本博章;竹之内大地
• 通讯作者: 竹之内大地

On an Efficient Implementation for a DFA-based Algorithms for the Extended Regular Expression Membership and Searching Problems

基于 DFA 的扩展正则表达式隶属度和搜索问题算法的有效实现

• 发表时间: 2007
• 作者: H. Yamamoto;T. Miyazaki
• 通讯作者: T. Miyazaki

拡張正規表現所属問題に対するDFAに基づいたアルゴリズム

基于 DFA 的扩展正则表达式隶属度问题算法

• 发表时间: 2006
• 期刊: 情報処理学会 研究報告 2006-AL-109
• 作者: Isomoto H.;et al.;山本博章
• 通讯作者: 山本博章

Regular Expression Matching Algorithms using Dual Position Automata

使用双位置自动机的正则表达式匹配算法

• 发表时间: 2007
• 期刊: Proc. of the International Workshop on Combinatorial Algorithms 2007
• 作者: Hisatsune J;et. al.;H. Yamamoto
• 通讯作者: H. Yamamoto