Research On Parallel String Matching Based On R-Contiguous Bits Rule

With the rapidly growing of information and the appearance of new application requirements in engineering, the classic string matching algorithms face great challenges. The string matching algorithms have been widely used in the fields of Internet information search, informational filtration, biology informatics, intrusion detection, distance education, electronic commerce and so on.Researches focus on exact string matching in early time, and many single and multiple string matching algorithms have been presented. However, the number of applications for string matching grows every day. It has very important theoretical value and practical meaning to research, so it is necessary to design very fast string matching algorithms.The r-continuous bits matching is a kind of evolvement of the exact string matching. The reasons of the evolvement source are as follows. The author consults lots of Immunology, AIS and Immune Algorithms about medicine field and computer field. Lots of difficult problems in computer domain have been solved by AIS very well. However, few problems have been solved by the r-continuous bits matching. Furthermore, the author discovers some excellent characteristics about the r-continuous bits matching rule. If the characteristics can be used in the string matching, we will gain satisfying result. For example, the characteristic of the immune system distribution and parallelism can be used in the string matching, and the problem of running time increasing rapidly will be solved when the data increases rapidly. Furthermore, the r-continuous bits matching rule discussed emphatically in the paper originates from the string, matching of antigen and antibody. In the human immune system, the kinds of antibody are probably 10⁶, however, people have discovered that the kinds of antigen are probably 10¹⁶. Why can our human body that be enclosed in giant virus be in a whole skin? The answer is the string matching of antigen and antibody.Based on these ideas above, the author will compose the paper.First of all, the paper simply introduces some basic knowledge about immune matching rule and presents the biological basis of the paper.Secondly, the author analyses the KMP algorithm and introduces the r-continuous bits matching rule into the string matching. Thus, we can change the value r, which can control the string matching degree, and gain the satisfying answer.Finally, the author introduces the detailed constructed procedure of the Cluster from experience. We run the parallel string matching program. The experimental results accord for the advance design. In the seventh chapter, the author puts forward some unresolved problems. For example, how to improve the communication time. Cooperating with the medical experts, we can design computer immune system that is characteristic of the biological immune system. The biological immune system can defense kinds of antigen at the same time by the parallel method. In the future, these problems will be worth studying.