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

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

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

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

谢谢你的好建议

你在做什么？如果是拼写检查，你可以使用布隆filter – 请参阅此代码kata 。

我在拼写字典中最小化空间时看到的一种结构是将每个单词编码为：

所以单词列表

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日，那里的记忆比现在更加稀缺。

Patricia trie可能更合适：

我的（模糊）记忆告诉我在一些早期的全文搜索引擎中使用了…

保罗。

您仍然需要使用Trie维护树结构。编码字母或N字母的霍夫曼（对于“ing”，“un”，“ing”等常见forms）可以利用字典中的出现频率并将条目压缩为位。

完全疯狂的想法……（也就是说非常错误）

如何将单词存储为所有可能的字母组合的树？

然后每个“单词”只花费一个char和两个指针（一个指向char，一个指向终结符。）这样，它们共有的字母越多，每个单词的成本就越少。

  . . / / rps-. /\\ a \s-. / t-. c \ s-.

汽车鲤鱼鲤鱼汽车推车

因此，对于9个字符和14个指针，我们得到6个“单词”，总共25个字母。

搜索会很快（指针查找而不是字符比较），你可以做一些词干优化来节省更多的空间……？

编辑：看起来我重新发明了轮子。 😉

与保罗的post有关：

在你的情况下你不能考虑Trie的任何理由？如果它只是一个实现问题，这里是Patricia trie插入和C搜索（来自NIST）的紧密实现：

Patricia插入C语言

Patricia在C中搜索