c-trie++: A dynamic trie tailored for fast prefix searches
c-trie++: A dynamic trie tailored for fast prefix searches
复制标题
c-trie：专为快速前缀搜索而定制的动态特里树
DOI：
10.1016/j.ic.2021.104794
复制
发表时间：
2021
影响因子：
1
通讯作者：
Masayuki Takeda
中科院分区：
文献类型：
--
作者：
Kazuya Tsuruta;Dominik Koeppl;Shunsuke Kanda;Yuto Nakashima;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
给定一个动态集合K，K个字符串的总长度为n，其字符从大小为σ的字母表中提取，关键字字典是建立在K上的数据结构，它提供对K的查找，前缀搜索和更新操作。在假设α= w/lg <$σ字符适合于w位的单个机器字的情况下，我们提出了一个关键字字典，其在nlg <$σ+ Θ（klg <$n）或|不|lg <$σ+ Θ（k w）位空间，其中|不|是表示K的trie的节点数。它支持在O（m/α+ lg <$α）期望时间内对字RAM模型中长度为m的输入字符串进行所有操作。我们的实施评估突出了建议的数据结构的实际用途，特别是前缀搜索最重要的关键字字典操作之一。
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.