Space-efficient string indexing for wildcard pattern matching

DOI10.4230/LIPICS.STACS.2014.506zbMATH Open1359.68339arXiv1401.0625OpenAlexW2964110985MaRDI QIDQ2965512FDOQ2965512

Authors: Yakov Nekrich, Moshe Lewenstein, Jeffrey Scott Vitter 

Publication date: 3 March 2017

Abstract: In this paper we describe compressed indexes that support pattern matching queries for strings with wildcards. For a constant size alphabet our data structure uses $O(nlo{g}^{varepsilon}n)$ bits for any $varepsilon>0$ and reports all $mathrmocc$ occurrences of a wildcard string in $O(m+sigm{a}^{g}cdotmu(n)+mathrmocc)$ time, where $mu(n)=o(logloglogn)$, $sigma$ is the alphabet size, $m$ is the number of alphabet symbols and $g$ is the number of wildcard symbols in the query string. We also present an $O(n)$-bit index with $O((m+sigm{a}^g+mathrmocc)lo{g}^{varepsilon}n)$ query time and an $O(n(loglogn{)}^2)$-bit index with $O((m+sigm{a}^g+mathrmocc)loglogn)$ query time. These are the first non-trivial data structures for this problem that need $o(nlogn)$ bits of space.

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

Recommendations

• Less space: indexing for queries with wildcards
• Less space: indexing for queries with wildcards
• Space Efficient Indexes for String Matching with Don’t Cares

zbMATH Keywords

pattern matchingcompressed data structurescompressed indexes

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Cited In (13)

• On the average-case complexity of pattern matching with wildcards
• Document retrieval with one wildcard
• Document retrieval with one wildcard
• Less space: indexing for queries with wildcards
• Space Efficient Indexes for String Matching with Don’t Cares
• Succincter text indexing with wildcards
• On character-based index schemes for complex wildcard search in peer-to-peer networks
• Less space: indexing for queries with wildcards
• Compressed indexes for text with wildcards
• Practical space-efficient index for structural pattern matching
• Fast string dictionary lookup with one error
• Dynamic relative compression, dynamic partial sums, and substring concatenation
• Pattern masking for dictionary matching: theory and practice

This page was built for publication: Space-efficient string indexing for wildcard pattern matching

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