Counting Colours in Compressed Strings

DOI10.1007/978-3-642-21458-5_18MaRDI QIDQ3011854zbMATH OpenOpenAlexFDO

Authors Travis Gagie, Juha Kärkkäinen

Publication date 29 June 2011

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: Suppose we are asked to preprocess a string (s [1..n]) such that later, given a substring's endpoints, we can quickly count how many distinct characters it contains. In this paper we give a data structure for this problem that takes (n H_0 (s) + Oh{n} + oh{n H_0 (s)}) bits, where (H_0 (s)) is the 0th-order empirical entropy of $s$, and answers queries in $Ohlo{g}^{1+epsilon}n$ time for any constant (epsilon > 0). We also show how our data structure can be made partially dynamic.

Recommendations

• Compressed counting
• Counting certain binary strings
• Pattern discovery in colored strings
• Pattern discovery in colored strings
• Counting distinct strings
• On the descriptive complexity of color coding
• Counting suffix arrays and strings

Cites work

• Approximate colored range and point enclosure queries
• Combinatorial Pattern Matching
• Compressed representations of sequences and full-text indexes
• Efficient Colored Orthogonal Range Counting
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 2119724 (Why is no real title available?)
• Rank and select revisited and extended
• Rank/select on dynamic compressed sequences and applications
• Succinct data structures for flexible text retrieval systems

Cited in

(7)

• Data structures for categorical path counting queries
• Wavelet trees for all
• Array range queries
• Dynamic range majority data structures
• Colored range queries and document retrieval
• Succinct color searching in one dimension
• Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions

Describes a project that uses

Uses Software

• PATRICIA

This page was built for publication: Counting Colours in Compressed Strings

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