c-trie++: A dynamic trie tailored for fast prefix searches
Kazuya Tsuruta, Dominik Köppl, S Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda · Information and Computation · 2021
Given a dynamic set K of k strings of total length n whose characters are drawn from an alphabet of size σ , a keyword dictionary is a data structure built on K that provides lookup, prefix search, and update operations on K . Under the assumption that α = w / lg σ characters fit into a single machine word of w bits, we propose a keyword dictionary that represents K in either n lg σ + Θ ( k lg n ) or | T | lg σ + Θ ( k w ) bits of space, where | T | is the number of nodes of a trie representing K . It supports all operations in O ( m / α + lg α ) expected time on an input string of length m in the word RAM model. An evaluation of our implementation highlights the practical usefulness of the proposed data structure, especially for prefix searches — one of the most essential keyword dictionary operations.