Studies on String Pattern Matching Algorithms

字符串模式匹配算法的研究

• 批准号: 60460227
• 负责人: ARIKAWA Setsuo
• 金额: $ 2.62万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (B)
• 财政年份: 1985
• 资助国家: 日本
• 起止时间: 1985 至 1986
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-60460227/
• 关键词: Pattern matching; text processing; sequential search; Japanese texts; information retrieval; 情報検索; サーチ技法; データベースシステム

This project has aimed at developing and improving string pattern matching algorithms, and then applying the results to a practical text database management system. We have concentrated on the following subjects and got fruitful results:1) Surveying the states of art in pattern matching techniques. Including the most famous algorithms by Boyer-Moore, Knuth-Morris-Pratt and Aho-Corasick, we have written a systematic survey paper which will be published from Computer Software.2) Developing an efficient pattern matching algorithm as an extension of our technique of dividing character codes.3) Developing a replacing algorithm for Japanese texts. We have developed a Japanese text version of pattern matching algorithm for replacing several character string at time which we developed before for English texts.4) Imploving the SIGMA system for text database system so as to deal with every texts including Japanese texts and English texts as well. The system makes use of the techniques and algorithms we have developed in this project.

本项目旨在开发和改进字符串模式匹配算法，然后将结果应用于实际的文本数据库管理系统。我们主要在以下几个方面进行了研究，并取得了丰硕的成果：1)考察了模式匹配技术的研究现状。包括Boyer-Moore， Knuth-Morris-Pratt和Aho-Corasick最著名的算法，我们写了一篇系统的调查论文，将发表在《计算机软件》上。2)开发一种有效的模式匹配算法，作为我们分割字符代码技术的扩展。3)开发日语文本替换算法。我们开发了一种日语文本版本的模式匹配算法，用于替换以前为英语文本开发的几个字符串。4)内建文本数据库系统的SIGMA系统，以处理所有文本，包括日语文本和英语文本。该系统利用了我们在这个项目中开发的技术和算法。

项目成果

有川節夫,他: 九州大学大型計算機センター計算機科学研究報告. 4. (1987)

Setsuo Arikawa 等：九州大学大型计算机中心计算机科学研究报告 4。（1987）。

有川節夫,篠原武: コンピュータソフトウェア. 4. (1987)

Setsuo Arikawa，Takeshi Shinohara：计算机软件 4. (1987)。

Yoshihiro Mizoguchi, Hiroshi Ohtsuka and Yasuo Kawahara: "A Symbolic Calculus of Regular Expressions" Bulletin of Informatics and Cybernetics. 22. 94-103 (1987)

Yoshihiro Mizoguchi、Hiroshi Ohtsuka 和 Yasuo Kawahara：“正则表达式的符号演算”信息学和控制论通报。

Proc.4th International Conference on Logic Programming.(1987)

Proc.第四届国际逻辑编程会议（1987）

Takeshi Shinohara and Setsuo Arikawa: "Pattern Matching Machines for Japanese Texts" Research Report, Research Institute of Fundamental Information Sciene Kyushu University. 110. 1-19 (1987)

Takeshi Shinohara 和 Setsuo Arikawa：“日语文本的模式匹配机”研究报告，九州大学基础信息科学研究所。