Dictionary matching with a few gaps

DOI10.1016/J.TCS.2015.04.011MaRDI QIDQ2346375zbMATH OpenOpenAlexFDO

Authors Amihood Amir, Avivit Levy, Ely Porat, B. R. Shalom

Publication date 1 June 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.2350

zbMATH Keywords

string matchingdictionary matchinggapped patterns

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Abstract: The dictionary matching with gaps problem is to preprocess a dictionary $D$ of $d$ gapped patterns $P_1,ldots,P_d$ over alphabet $Sigma$, where each gapped pattern $P_i$ is a sequence of subpatterns separated by bounded sequences of don't cares. Then, given a query text $T$ of length $n$ over alphabet $Sigma$, the goal is to output all locations in $T$ in which a pattern $P_{i}inD$, $1leqileqd$, ends. There is a renewed current interest in the gapped matching problem stemming from cyber security. In this paper we solve the problem where all patterns in the dictionary have one gap with at least $alpha$ and at most $$ don't cares, where $alpha$ and $$ are given parameters. Specifically, we show that the dictionary matching with a single gap problem can be solved in either $O(dlogd+|D|)$ time and $O(dlo{g}^{varepsilon}d+|D|)$ space, and query time $$, where $occ$ is the number of patterns found, or preprocessing time and space: $O(d^2+|D|)$, and query time $$, where $occ$ is the number of patterns found. As far as we know, this is the best solution for this setting of the problem, where many overlaps may exist in the dictionary.

Recommendations

• Dictionary matching with uneven gaps
• Dictionary matching with one gap
• Dictionary matching with a bounded gap in pattern or in text
• A comparative study of dictionary matching with gaps: limitations, techniques and challenges
• Fast approximate matching of words against a dictionary
• Parameterized dictionary matching and recognition with one gap
• scientific article; zbMATH DE number 437564
• Improved dynamic dictionary matching
• Dictionary matching and indexing with errors and don't cares

Cites work

• A Four Russians algorithm for regular expression pattern matching
• A Space-Economical Suffix Tree Construction Algorithm
• A faster algorithm for matching a set of patterns with variable length don't cares
• Alphabet-Independent and Scaled Dictionary Matching
• Dictionary matching and indexing with errors and don't cares
• Dynamic dictionary matching
• Efficient string matching
• Faster Regular Expression Matching
• Finding Patterns with Variable Length Gaps or Don’t Cares
• Improved dynamic dictionary matching
• Matching a set of strings with variable length don't cares
• New techniques for regular expression searching
• On-line construction of suffix trees
• Orthogonal range searching on the RAM, revisited
• Regular expression matching with multi-strings and intervals
• String matching with variable length gaps
• Text Indexing and Dictionary Matching with One Error
• Truncated suffix trees and their application to data compression.

Cited in

(15)

• Mind the gap: essentially optimal algorithms for online dictionary matching with one gap
• Dictionary matching with uneven gaps
• A comparative study of dictionary matching with gaps: limitations, techniques and challenges
• Online parameterized dictionary matching with one gap
• Online recognition of dictionary with one gap
• Parameterized dictionary matching and recognition with one gap
• Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams
• Mind the gap!
• Online matching of multiple regular patterns with gaps and character classes
• Pattern masking for dictionary matching
• Dictionary matching and indexing with errors and don't cares
• Real-Time Streaming Multi-Pattern Search for Constant Alphabet
• Dictionary matching with a bounded gap in pattern or in text
• Upper and lower bounds for dynamic data structures on strings
• Dictionary matching with one gap

This page was built for publication: Dictionary matching with a few gaps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2346375)