用于存储单词列表的节省空间的数据结构？

Question

对于这种情况,还有比Trie更好的东西吗？

• 存储~100k英文单词列表
• 需要使用最少的内存
• 查找需要合理,但不必快速闪电

我正在使用Java,所以我的第一次尝试就是使用Set <String>.但是,我的目标是移动设备并且内存不足.由于许多英语单词共享共同的前缀,trie似乎是一个体面的赌注,以节省一些记忆 - 任何人都知道一些其他好的选择？

编辑 - 更多信息 - 数据结构将用于两个操作

• 回答:列表中是否有XYZ字样？
• 生成XYZ周围的单词邻域,其中一个字母不同

谢谢你的好建议

Answer 1

我看到一个用于最小化拼写字典空间的结构是将每个单词编码为:

• 与最后一个共同的字符数(一个字节); 和
• 新的结局.

所以单词列表

HERE            would encode as    THIS
sanctimonious                      0,sanctimonious
sanction                           6,on
sanguine                           3,guine
trivial                            0,trivial

你在那里直接保存7个字节(19%),我怀疑由于相邻单词的(公共前缀)之间的最小距离,对于20,000字的字典保存是相似的.

为了加速查找,内存中有一个26条目表,它保存了以a,b,c,...,z开头的单词的起始偏移量.这些偏移处的字总是以0作为第一个字节,因为它们没有与前一个字相同的字母.

这似乎是一种特里但没有指针,如果树中的每个字符都有一个与之关联的4字节指针,这肯定会占用太多空间.

请注意,这是来自我的CP/M日,那里的记忆比现在更加稀缺.

Answer 2

Patricia trie可能更合适:

http://en.wikipedia.org/wiki/Patricia_tree

我的(模糊)记忆告诉我在一些早期的全文搜索引擎中使用了...

保罗.

Answer 3

你在干什么？如果是拼写检查，您可以使用布隆过滤器 - 请参阅此代码 kata。