This paper proposed a storing approach for trie structures, called coordinate hash trie. The basic idea is using a global hash table with a special hash function to store all edges of a trie. For a trie with $n$ nodes and an alphabet with size $m$, the execution time of finding, inserting and deleting a child node, is $O(1)$ for the average case, $O(m)$ for the worst case. The space used by this approach is $O(n)$, unrelated to $m$. The constant of space consumption is predictable, with no need for reallocation or resizing. In addition, this approach is very easy to implement.


翻译:本文提出了一种 Trie 结构的存储方法,称为坐标哈希 Trie。基本思想是使用全局哈希表和特殊的哈希函数来存储 Trie 的所有边。对于一个有 $n$ 个节点和字母表大小为 $m$ 的 Trie,平均情况下查找、插入和删除子节点的执行时间为 $O(1)$,最坏情况下为 $O(m)$。该方法使用的空间复杂度为 $O(n)$,与 $m$ 无关。空间消耗的常数可预测,不需要重新分配或重新调整大小。此外,该方法非常容易实现。

0
下载
关闭预览

相关内容

【硬核书】稀疏多项式优化:理论与实践,220页pdf
专知会员服务
67+阅读 · 2022年9月30日
专知会员服务
76+阅读 · 2021年3月16日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
一文带你浏览Graph Transformers
PaperWeekly
1+阅读 · 2022年7月8日
图表示学习Graph Embedding综述
AINLP
33+阅读 · 2020年5月17日
【图神经网络入门】GAT图注意力网络
深度学习自然语言处理
28+阅读 · 2020年5月16日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
论文浅尝 | 一种嵌入效率极高的 node embedding 方式
开放知识图谱
13+阅读 · 2019年5月12日
TensorFlow 2.0新特性之Ragged Tensor
深度学习每日摘要
18+阅读 · 2019年4月5日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】用Tensorflow理解LSTM
机器学习研究会
36+阅读 · 2017年9月11日
国家自然科学基金
0+阅读 · 2017年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
1+阅读 · 2023年5月15日
Arxiv
0+阅读 · 2023年5月14日
Arxiv
54+阅读 · 2022年1月1日
VIP会员
相关VIP内容
【硬核书】稀疏多项式优化:理论与实践,220页pdf
专知会员服务
67+阅读 · 2022年9月30日
专知会员服务
76+阅读 · 2021年3月16日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
一文带你浏览Graph Transformers
PaperWeekly
1+阅读 · 2022年7月8日
图表示学习Graph Embedding综述
AINLP
33+阅读 · 2020年5月17日
【图神经网络入门】GAT图注意力网络
深度学习自然语言处理
28+阅读 · 2020年5月16日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
论文浅尝 | 一种嵌入效率极高的 node embedding 方式
开放知识图谱
13+阅读 · 2019年5月12日
TensorFlow 2.0新特性之Ragged Tensor
深度学习每日摘要
18+阅读 · 2019年4月5日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】用Tensorflow理解LSTM
机器学习研究会
36+阅读 · 2017年9月11日
相关基金
国家自然科学基金
0+阅读 · 2017年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员