多态自动机在字符串搜索及统计时的应用

Application of multiplicity automata to text search and statistics

多态自动机较之有穷自动机有更强的计算功能和对算法的描述功能,所以在计算理论和学习理论中有相当地位.本文首先简要地介绍了多态自动机,然后利用多态自动机的计算功能给出了一种搜索算法,此算法可以完成字符串的搜索和统计功能.文章对此算法的复杂度进行了分析,该算法的复杂度是多项式的,并且对此算法添加一些辅助部分也可以完成搜索网络资源的功能.此算法在计算机上也很容易实现.

Compared with deterministic automata,multiplicity automata has stronger functions of computing and description of algorithm. Consequently it has an important place on computation and learning theory. Firstly, In this paper, the multiplicity automata is briefly introduced, then a new searching algorithm, which has functions of searching and counting any strings, is given by using computing function of multiplicity automata. The algorithm has polynomial complexity. And given some other supplementary, It also has the function of searching sources on Internet with some other supplementary installations. The other advantage of the algorithm is its easiness to implement on computer.