Studies on String Pattern Matching Algorithms

本项目旨在开发和改进字符串模式匹配算法，并将其应用到一个实用的文本数据库管理系统中。1)对模式匹配技术的研究现状进行了综述。包括Boyer-Moore、Knuth-Morris-Pratt和Aho-Corasick的最著名的算法，我们撰写了一篇系统的综述论文，并将在计算机软件上发表。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.