doi: 10.4304/jsw.6.12.2391-2398
Multi-pattern Matching with Wildcards
- 1 College of Computer Science and Technology, Jilin University, Changchun, China
- 2 Department of Computer Science, Jilin Business and Technology College, Changchun, China
- 3 Department of Computer Science & Engineering, Univ. of South Carolina, USA
Abstract
Multi-pattern matching with wildcards is to find all the occurrences of a set of patterns with wildcards in a text. This problem arises in various fields, such as computational biology and network security. But the problem is not extensively studied as the single pattern case and there is no efficient algorithm for this problem. In this paper, we present efficient algorithms based on the fast Fourier transform. Let <em>P</em> = {<em>p</em><sup>1</sup>, . . . , <em>p<sup>k</sup></em>} be a set of patterns with wildcards where the total length of patterns is |<em>P</em>|, and a text <em>t</em> of length <em>n</em> over alphabet <em>a</em><sub>1</sub>, . . . , a_x001b_. We present three algorithms for this problem where patterns are matched simultaneously. The first algorithm finds the matches of a small set of patterns in the text in <em>O</em>(<em>n</em> log |<em>P</em>| + <em>occ</em> log <em>k</em>) time where <em>occ</em> is the total number of occurrences of <em>P</em> in <em>t</em>. The words used in the algorithm are of size <em>k</em>d2 lg <em>_x001b_e</em>+<em>P<sub>k</sub></em> i=1dlg |pi|e bits. The second algorithm is based on a prime number encoding. It runs in time <em>O</em>(<em>n</em> log<em>m</em> + <em>occ </em>log<em> k</em>) where <em>m</em> is the length of the longest pattern in <em>P</em>. The algorithm uses words with kdlg(2m_x001b_2 +k2)e bits. The third one finds the occurrences of patterns in the text in time <span id="cke_bm_355S" style="display: none;"> </span><em>O</em><span id="cke_bm_355E" style="display: none;"> </span>(<em>n</em> log |<em>P</em>| log _x001b_ + <em>occ</em> log <em>k</em>) by computing the Hamming distance between patterns and the text. The algorithm uses words with <span id="cke_bm_356E" style="display: none;"> </span><em>Pk i</em>=1dlg |pi|e bits. Moreover, we demonstrate an FFT implementation based on the modular arithmetic for machines with 64-bit word. Finally, we show that these algorithms can be easily parallelized, and the parallelized algorithms are given as well.
Keywords
- Algorithm;
- Multi-pattern
- matching;
- Wildc
How to Cite
Meng Zhang, Yi Zhang, Jijun Tang, and Xiaolong Bai, "Multi-pattern Matching with Wildcards," Journal of Software, vol. 6, no. 12, pp. 2391-2398, 2011. https://doi.org/ 10.4304/jsw.6.12.2391-2398
Copyright & License
Copyright © 2011 by the authors. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited (CC BY 4.0).