c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches

Code

• gitlab.com/habatakitai/ctriepp
  OfficialIn papernone★ 0

Abstract

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 locate, prefix search, and update operations on K. Under the assumption that = w / characters fit into a single machine word w, we propose a keyword dictionary that represents K in n + (k n) bits of space, supporting all operations in O(m / + ) expected time on an input string of length m in the word RAM model. This data structure is underlined with an exhaustive practical evaluation, highlighting the practical usefulness of the proposed data structure, especially for prefix searches - one of the most elementary keyword dictionary operations.

Reproductions