Dictionary matching with a few gaps

DOI10.1016/J.TCS.2015.04.011zbMATH Open1319.68106arXiv1408.2350OpenAlexW1978055030MaRDI QIDQ2346375FDOQ2346375

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)

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.

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

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

zbMATH Keywords

string matchingdictionary matchinggapped patterns

Mathematics Subject Classification ID

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

Cites Work

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

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)