Abstract
In his 1987 paper entitled Generalized String Matching Abrahamson introduced the concept of pattern matching with character classes and provided the first efficient algorithm to solve this problem. The best known solution to date is due to Linhart and Shamir (2009).
Another broad yet comparatively less intensively studied class of string matching problems is numerical string searching, such as for instance “lessthan” or L1norm string searching. The best known solutions for problems in this class are based on FFT convolution after some suitable reencoding.
The present paper introduces modulated string searching as a unified framework for string matching problems where the numerical conditions can be combined with some Boolean/numerical decision conditions on the character classes. One example problem in this class is the locally boundedL1norm matching problem with parameters b and τ: here the pattern “matches” a text of same length if their L1distance is at most b and if furthermore there is no position where the text element and pattern element differ by more than the local bound τ. A more general setup is that where the pattern positions contain character classes and/or each position has its own private local bound. While the first variant can clearly be handled by adaptation of the classic FFT method, the second one is far too complicated for this treatment. The algorithm we propose in this paper can solve all such problems efficiently.
The proposed framework contains two nested procedures. The first one, based on Karatsubaʼs fast multiplication algorithm, solves pattern matching with character classes within time O(nm0.585), where n and m are the text and pattern length respectively (under some reasonable conventions). This is slightly better than the complexity of Abrahamsonʼs algorithm for generalized string matching but worse than algorithms based on FFT. The second procedure, which works as a plugin within the first one and is tailored to the specific problem variant at hand, solves the numerical and/or Boolean matching problem with high efficiency. Some of the previously known constructions can be adapted to match or outperform several (but not all) problem variations handled by the construction proposed here. The latter aims to be a general tool that provides a unified solution for all problems of this kind.
Another broad yet comparatively less intensively studied class of string matching problems is numerical string searching, such as for instance “lessthan” or L1norm string searching. The best known solutions for problems in this class are based on FFT convolution after some suitable reencoding.
The present paper introduces modulated string searching as a unified framework for string matching problems where the numerical conditions can be combined with some Boolean/numerical decision conditions on the character classes. One example problem in this class is the locally boundedL1norm matching problem with parameters b and τ: here the pattern “matches” a text of same length if their L1distance is at most b and if furthermore there is no position where the text element and pattern element differ by more than the local bound τ. A more general setup is that where the pattern positions contain character classes and/or each position has its own private local bound. While the first variant can clearly be handled by adaptation of the classic FFT method, the second one is far too complicated for this treatment. The algorithm we propose in this paper can solve all such problems efficiently.
The proposed framework contains two nested procedures. The first one, based on Karatsubaʼs fast multiplication algorithm, solves pattern matching with character classes within time O(nm0.585), where n and m are the text and pattern length respectively (under some reasonable conventions). This is slightly better than the complexity of Abrahamsonʼs algorithm for generalized string matching but worse than algorithms based on FFT. The second procedure, which works as a plugin within the first one and is tailored to the specific problem variant at hand, solves the numerical and/or Boolean matching problem with high efficiency. Some of the previously known constructions can be adapted to match or outperform several (but not all) problem variations handled by the construction proposed here. The latter aims to be a general tool that provides a unified solution for all problems of this kind.
Original language  English 

Pages (fromto)  2339 
Number of pages  17 
Journal  Theoretical Computer Science 
Volume  525 
Early online date  14 Oct 2013 
DOIs  
Publication status  Published  2014 
Keywords
 Pattern matching with character classes
 Karatsuba's fast multiplication algorithm
 Locally bounded L1norm string matching on character classes
 Truncated L1norm string matching on character classes
Profiles

Johannes Siemons
 School of Mathematics  Emeritus Reader, Visitor
 Algebra and Combinatorics  Member
Person: Honorary, Other related  academic, Research Group Member