Linear Time Succinct Indexable Dictionary Construction with Applications

Abstract

Indexable dictionaries, supporting rank and select queries, are used as building blocks for many algorithms. For a universe U = {0,..., |U|-1} and an ordered set S = {s0,..., sn-1} U, an indexable dictionary supports rank and select queries in addition to membership queries, Select(j) query is used to get the j'th ranked element, and Rank(x) is used to retrieve the rank of x among all elements in S. In this work, we give two time-linear, one-pass practical constructions of static succinct indexable dictionaries, both are deterministic in query time, but they differ by construction method and Rank(x) query time. The first supports Rank and Select queries in constant time and has expected linear construction time. The second supports Select queries in constant time, and Rank(x) queries in O(log log |U|/n) time, has worst-case linear construction time, and uses only o(n) additional bits during construction. The latter one is fully indexable dictionary supporting Rank(x) queries on arbitrary x. These indexable dictionaries can be used where construction bounds matter, as in a dynamic algorithm that uses them as a building block, we exemplify this by showing how to utilize them to improve the query time of a dynamic dictionary matching algorithm.