Rank and select operations on a word

DOI10.1016/J.IPL.2021.106148MaRDI QIDQ2234779zbMATH OpenOpenAlexFDO

Authors Meng Zhang, Yi Zhang

Publication date 19 October 2021

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2021.106148

zbMATH Keywords

pattern matchingsuccinct data structuresword parallelism

Mathematics Subject Classification ID

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

Recommendations

• Experimental and Efficient Algorithms
• Optimal indexes for sparse bit vectors
• Lower bounds on the size of selection and rank indexes
• Adaptive succinctness
• Optimal lower bounds for rank and select indexes

Cites work

• scientific article; zbMATH DE number 3133100 (Why is no real title available?)
• scientific article; zbMATH DE number 5596834 (Why is no real title available?)
• Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching
• Fast convolutions of packed strings and pattern matching with wildcards
• Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets
• Surpassing the information theoretic bound with fusion trees
• Towards optimal packed string matching
• Trans-dichotomous algorithms without multiplication — some upper and lower bounds

Cited in

(3)

• Lower bounds on the size of selection and rank indexes
• High-order entropy compressed bit vectors with rank/select
• Experimental and Efficient Algorithms

This page was built for publication: Rank and select operations on a word

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