Development of string matching algorithms with flexible functions and its applications

功能灵活的字符串匹配算法开发及其应用

• 批准号: 15500006
• 负责人: YAMAMOTO Hiroaki
• 金额: $ 1.73万
• 依托单位: Shinshu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2003
• 资助国家: 日本
• 起止时间: 2003 至 2005
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-15500006/
• 关键词: extended regular expression; pattern matching algorithm; finite automaton; string matching algorithm; 検索アルゴリズム; 文字列検索アルゴリズム; 近似照合アルゴリズム; 近似検索アルゴリズム

Below are results obtained by this research project.1. We developed an extended regular expression matching algorithm based on finite automata.2. We developed a hybrid extended regular expression matching algorithm based on finite automata. This algorithm can make use of various automata.3. We extended the above algorithm to an extended regular expression with any boolean function.4. We made searching soft-wares for the algorithms developed and evaluated the performance experimentally.5. We developed an approximate matching algorithm for semi-extended regular expressions.6. We developed an efficient translation algorithm from regular expressions into NFAs. This algorithm can be used in matching algorithms.

本研究项目取得的成果如下： 1．开发了一种基于有限自动机的扩展正则表达式匹配算法。 2．我们开发了一种基于有限自动机的混合扩展正则表达式匹配算法。该算法可以利用各种自动机。 3．我们将上述算法扩展到具有任意布尔函数的扩展正则表达式。4．我们针对所开发的算法制作了搜索软件并进行了性能实验评估。 5．我们开发了半扩展正则表达式的近似匹配算法。 6．我们开发了一种从正则表达式到 NFA 的高效翻译算法。该算法可用于匹配算法。

项目成果

正規表現をNFAに変換するためのアルゴリズムについて

关于正则表达式转换为NFA的算法

• 发表时间: 2004
• 期刊: 第3回情報科学技術フォーラム論文集
• 作者: 山本博章;宮崎敬;岡本正行
• 通讯作者: 岡本正行

A New Translation from Semi-extended Regular Expressions into NFAs and Its Application to an Approximate Matching Problem

• DOI: 10.1007/978-3-540-24587-2_18
• 发表时间: 2003-09
• 作者: Hiroaki Yamamoto

Hiroaki Yamamoto: "A Fast Bit-Parallel Algorithm for Matching Extended Regular Expressions"Proc.of COCOON2003, Lecture Notes in Computer Science. LNCS2697. 222-231 (2003)

Hiroaki Yamamoto：“用于匹配扩展正则表达式的快速位并行算法”Proc.of COCOON2003，计算机科学讲义。

Experimental evaluation of algorithms on translating from regular expressions into NFAs

将正则表达式转换为 NFA 的算法的实验评估

• 发表时间: 2005
• 期刊: 2005 Summer LA Symposium
• 作者: D.Takenouchi;H.Yamamoto
• 通讯作者: H.Yamamoto

Bit-Parallel Translation into Small NFAs and Fast Matching Algorithm for Regular Expressions

小型 NFA 的位并行翻译和正则表达式的快速匹配算法

• 发表时间: 2005
• 期刊: Proc. of 2005 Korea-Japan Joint Workshop on Algorithms and Computation (WAAC2005)
• 作者: H.Yamamoto;M.Okamoto;T.Miyazaki
• 通讯作者: T.Miyazaki