Portal de Periódicos da CAPES

Online Dictionary Matching with Variable-Length Gaps

2011; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-642-20662-7_7

1611-3349

Tuukka Haapasalo, Panu Silvasti, Seppo Sippu, Eljas Soisalon-Soininen,

Web Data Mining and Analysis

The string-matching problem with wildcards is considered in the context of online matching of multiple patterns. Our patterns are strings of characters in the input alphabet and of variable-length gaps, where the width of a gap may vary between two integer bounds or from an integer lower bound to infinity. Our algorithm is based on locating "keywords" of the patterns in the input text, that is, maximal substrings of the patterns that contain only input characters. Matches of prefixes of patterns are collected from the keyword matches, and when a prefix constituting a complete pattern is found, a match is reported. In collecting these partial matches we avoid locating those keyword occurrences that cannot participate in any prefix of a pattern found thus far. Our experiments show that our algorithm scales up well, when the number of patterns increases.