An efficient POSIX regular expression matching via Glushkov automata with augmented transitions

通过具有增强转换的 Glushkov 自动机进行高效的 POSIX 正则表达式匹配

• 批准号: 22500019
• 负责人: OKUI Satoshi
• 金额: $ 2.58万
• 依托单位: Chubu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2010
• 资助国家: 日本
• 起止时间: 2010 至 2012
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22500019/
• 关键词: 正規表現; POSIX; パターン照合; オートマトン; ＰＯＳＩＸ; 最左最長; パターンマッチング

Regular expression matching is crucial for many applications such as text processing. Although POSIX 1003.2 standard requires (sub-) matching to follow the leftmost-longest rules, almost none of existing implementations, which rely on backtracking, are responsible to the requirement; they follow the greedy semantics, an alternative way more suited for backtracking, instead. This study has offered, based on a slight extension of Glushkov automata (aka, position automata), a new and more efficient matching algorithm that accommodates POSIX regular expression matching. We have given its rigorous correctness proof, and the exact computational cost at worst case. Our experimental implementation has shown significant improvements on efficiency in some practical cases.

正则表达匹配对于许多应用（例如文本处理）至关重要。尽管POSIX 1003.2标准需要（子）匹配才能遵循最长的规则，但几乎没有依赖回溯的现有实现对要求负责；他们遵循贪婪的语义，这是一种更适合回溯的替代方式。这项研究提供了基于Glushkov Automata（又称位置自动机）的略有扩展，这是一种新的，更有效的匹配算法，可容纳POSIX正则表达式匹配。我们已经给出了其严格的正确性证明，以及最坏情况下的确切计算成本。在某些实际情况下，我们的实验实施已显示出效率的显着提高。

项目成果

正規表現のあいまいさ除去の効率的実現

正则表达式消歧的高效实现

• 发表时间: 2011
• 期刊: 情報科学リサーチシャーナル
• 作者: 尾花将輝;花川典子;飯田元;奥居哲;尾花将輝;奥居哲
• 通讯作者: 奥居哲

高階関数に基づく視覚的プログラミング言語の構造化

基于高阶函数构建可视化编程语言

• 发表时间: 2011
• 作者: 太田健介;杉山智昭;奥居哲
• 通讯作者: 奥居哲

POSIX-Compliant Disambiguation in Regular Expression Matching (Preliminary Report)

正则表达式匹配中符合 POSIX 标准的歧义消除（初步报告）

• 发表时间: 2010
• 作者: Norihiro Yoshida;Masataka Kinoshita,and Hajimu Iida;Satoshi Okui
• 通讯作者: Satoshi Okui

視覚的プログラミング言語におけるリファクタリング手法

可视化编程语言中的重构技术

• 发表时间: 2011
• 作者: 杉山智昭;太田健介;奥居哲
• 通讯作者: 奥居哲

決定性有限オートマトンによる正規表現の貪欲な照合

正则表达式与确定性有限自动机的贪婪匹配

• 发表时间: 2013
• 期刊: 情報科学リサーチジャーナル
• 作者: ロバート・A・ハーン;エリック・D・ドメイン 著;上原隆平 訳;奥居哲，増田拓也，藤田佳宏，鈴木大郎
• 通讯作者: 奥居哲，増田拓也，藤田佳宏，鈴木大郎