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

Question

有什么比 Trie 更好的了？对于这种情况？

• 存储约 10 万个英语单词的列表
• 需要使用最少的内存
• 查找需要合理，但不必快如闪电

我正在使用 Java，所以我的第一次尝试是只使用 Set 。但是，我的目标是移动设备并且内存已经不足。由于许多英语单词共享共同的前缀，因此 trie 似乎是节省一些内存的不错的选择——有人知道其他一些好的选择吗？

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

• 回答:列表中有某个单词 XYZ 吗？
• 生成 XYZ 周围有一个字母不同的词的邻域

谢谢你的好建议

Answer 1

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

• 与上一个相同的字符数(一个字节)；和
• 新的结局。

所以单词列表

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

您在那里直接节省了 7 个字节 (19%)，我怀疑仅由于相邻单词(的公共(public)前缀)之间的最小距离，对于 20,000 个单词的字典，节省会类似。

例如，我在一个排序的字典上运行了一个测试程序，并将旧存储空间计算为单词长度加一(用于终止符)，新存储空间为常用长度、不常用后缀长度和一个终结者。这是该测试程序的最后一部分，显示您可以超过 50%:

zwiebacks   -> zygote      common=        old=1044662 new=469762 55.0%
zygote      -> zygotes     common=zygote  old=1044670 new=469765 55.0%
zygotes     -> zygotic     common=zygot   old=1044678 new=469769 55.0%
zygotic     -> zymase      common=zy      old=1044685 new=469775 55.0%
zymase      -> zymogenic   common=zym     old=1044695 new=469783 55.0%
zymogenic   -> zymology    common=zymo    old=1044704 new=469789 55.0%
zymology    -> zymolysis   common=zymol   old=1044714 new=469795 55.0%
zymolysis   -> zymoplastic common=zymo    old=1044726 new=469804 55.0%
zymoplastic -> zymoscope   common=zymo    old=1044736 new=469811 55.0%
zymoscope   -> zymurgy     common=zym     old=1044744 new=469817 55.0%
zymurgy     -> zyzzyva     common=zy      old=1044752 new=469824 55.0%
zyzzyva     -> zyzzyvas    common=zyzzyva old=1044761 new=469827 55.0%

为了加快查找速度，内存中有一个包含 26 个条目的表，其中包含以 a、b、c、...、z 开头的单词的起始偏移量。这些偏移处的单词始终以 0 作为第一个字节，因为它们与前一个单词没有共同的字母。

这似乎是一种 trie 但没有指针，如果树中的每个字符都有一个与之关联的 4 字节指针，这肯定会占用大量空间。

请注意，这是我在 CP/M 时代的内存比现在稀缺得多。