Development of string matching algorithms with flexible functions and its applications

以下是本研究项目取得的成果。提出了一种基于有限自动机的扩展正则表达式匹配算法。提出了一种基于有限自动机的混合扩展正则表达式匹配算法。该算法可以利用各种自动机。我们将上述算法扩展到具有任意布尔函数的扩展正则表达式。为算法开发了搜索软件，并对算法性能进行了实验评估。提出了一种半扩展正则表达式的近似匹配算法。我们开发了一种从正则表达式到非正则表达式的高效转换算法。该算法可用于匹配算法中。

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.