all*_*aws 6 java data-structures
对于这种情况,还有比Trie更好的东西吗?
我正在使用Java,所以我的第一次尝试就是使用Set <String>.但是,我的目标是移动设备并且内存不足.由于许多英语单词共享共同的前缀,trie似乎是一个体面的赌注,以节省一些记忆 - 任何人都知道一些其他好的选择?
编辑 - 更多信息 - 数据结构将用于两个操作
谢谢你的好建议
我看到一个用于最小化拼写字典空间的结构是将每个单词编码为:
所以单词列表
HERE would encode as THIS
sanctimonious 0,sanctimonious
sanction 6,on
sanguine 3,guine
trivial 0,trivial
Run Code Online (Sandbox Code Playgroud)
你在那里直接保存7个字节(19%),我怀疑由于相邻单词的(公共前缀)之间的最小距离,对于20,000字的字典保存是相似的.
为了加速查找,内存中有一个26条目表,它保存了以a,b,c,...,z开头的单词的起始偏移量.这些偏移处的字总是以0作为第一个字节,因为它们没有与前一个字相同的字母.
这似乎是一种特里但没有指针,如果树中的每个字符都有一个与之关联的4字节指针,这肯定会占用太多空间.
请注意,这是来自我的CP/M日,那里的记忆比现在更加稀缺.
归档时间: |
|
查看次数: |
3963 次 |
最近记录: |