LIPIcs.STACS.2014.506.pdf
- Filesize: 0.61 MB
- 12 pages
Document
Space-Efficient String Indexing for Wildcard Pattern Matching
Authors
-
Part of:
Volume:
31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2014-03-05
Cite As Get BibTex
Moshe Lewenstein, Yakov Nekrich, and Jeffrey Scott Vitter. Space-Efficient String Indexing for Wildcard Pattern Matching. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 506-517, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/LIPIcs.STACS.2014.506
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(n.log^e(n)) bits for any e>0 and reports all occ occurrences of a wildcard string in O(m+s^g.M(n)+occ) time, where M(n)=o(log(log(log(n)))), s 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+s^g+occ).log^e(n)) query time and an O(n{log(log(n))}^2)-bit index with O((m+s^g+occ).log(log(n))) query time. These are the first non-trivial data structures for this problem that need o(n.log(n)) bits of space.
Subject Classification
Keywords
- compressed data structures
- compressed indexes
- pattern matching
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads