Studies on String Pattern Matching Algorithms

本计画的目的在于发展与改良字串模式比对演算法，并将其应用于一个实际的文字资料库管理系统。本文主要研究了以下几个方面的问题，并取得了丰硕的成果：1）模式匹配技术的研究现状。包括Boyer-Moore、Knuth-Morris-Pratt和Aho-Corasick最著名的算法，我们撰写了一篇系统的调查论文，该论文将在Computer Software上发表。2）开发一种高效的模式匹配算法，作为我们分割字符代码技术的扩展。3）开发日语文本的替换算法。我们开发了一种日文文本版的模式匹配算法，可以同时替换我们以前开发的英文文本的多个字符串。4）开发了SIGMA系统作为文本数据库系统，可以处理包括日文文本和英文文本在内的所有文本。该系统利用我们在这个项目中开发的技术和算法。

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.