Pattern Matching With Wildcard Constraints Based On Bit Parallel Technology

Pattern matching is a fundamental and important issue in computer science. It has been widely used in many fields, such as information retrieval, data stream mining, network intrusion detection, and biological computing, along with the rapid development of information technology. In recent years, pattern matching with wildcard constraints as a new area has increasingly attracted attention. Although adding wildcard constraints in the traditional patterns makes the problem more complicated, the patterns are more flexible. Pattern matching with wildcards has not only a theoretical research value, but also a great application potential in many areas, such as bioinformatics, where many of the protein patterns contain wildcard constraints.There have been several research efforts on pattern matching with wildcards, but some problems in this area are still open, e.g., the specification of wildcard constraints in patterns, the expression of the matching results, time efficiency and so on. This dissertation aims at these problems mentioned above, and our contributions are as follows:(1)Based on existing work on the definition about patterns that include global length constraints and local wildcard constrains, weprove that under the One-Off condition the pattern matching with wildcard constraints is an NP-hard problem.(2)A new algorithm BPBM based on bit parallel technology is proposed. This algorithm is based on a backward scanning, which uses two nondeterministic automatons (NFA) to simulate the process of scanning text. The bit parallel technology is used to solve two problems: the active states of NFA are too many and renewing active state collection is too slow when reading new characters one at each time. Theoretical analysis and experimental results show that the BPBM algorithm is more competitive to solve the same or similar problems than other related algorithms.(3)A web system is designed to provide some related algorithms from our research, anda platform for future in-depth studies.