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

Question

在这种情况下，有比Trie更好的选择吗？

• 存储约100k个英语单词列表
• 需要使用最少的内存
• 查询需要合理，但不必非常快

我正在使用Java，所以我的第一次尝试是只使用Set<String>。然而，我针对的是移动设备，内存已经很低了。由于许多英语单词共享公共前缀，使用Trie似乎是节省一些内存的不错选择 - 有没有其他好的选择？

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

• 回答：列表中是否包含某个单词XYZ？
• 生成周围与XYZ相差一个字母的单词邻域

感谢好的建议

- allclaws

---

你是假设没有网络连接吗？ - Milhous

@Milhous，现在我很想知道你认为有网络连接的情况下可能会提出什么建议... - paxdiablo

Answer 1

我看到的一种减少拼写字典空间的结构是将每个单词编码为：

• 与上一个单词相同的字符数（一个字节）；和
• 新的结尾。

因此，单词列表变为：

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

您在这里直接节省了7个字节（19%），我怀疑对于一个包含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操作系统时的经历，那时候的内存比现在更加稀缺。

- Pax

---

+1 - 感谢分享聪明的算法。顺便说一句，那时候，我的记忆可靠性弥补了稀缺的不足.... :-) - Adam Liss

Answer 2

一个 Patricia 树可能更合适：

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

我的模糊记忆告诉我，它们在一些早期的全文搜索引擎中被使用过...

保罗。

- Paul W Homer

Answer 3

你在做什么？如果是拼写检查，可以使用布隆过滤器 - 参见这个代码练习。

- mikes

---

我也想建议使用布隆过滤器，但考虑到他的目标，我认为布隆过滤器不适用。布隆过滤器不能明确回答一个单词是否在列表中，并且它也不允许生成邻域。 - mipadi

布隆过滤器如果列表中没有这个单词，就会明确回答“否定”。是的，邻域要求是后来添加的 :) - Mike Scott

Answer 4

你仍然需要使用 Trie 来维护树结构本身。 Huffman 编码 字母或 N 个字母（对于常见的形式，如“tion”、“un”、“ing”）可以利用字典中的出现频率并将条目压缩为位。

- eed3si9n

Answer 5

非常疯狂的想法...（即很可能是错误的）

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

然后每个“单词”只需要一个字符和两个指针（一个指向字符，一个指向终止符），这样它们共享的字母越多，每个单词的成本就越低。

      . .
     / /
    r-p-s-.
   /\\
  a  \s-.
 /    t-.
c      \
        s-.

车 鲤鱼 鲤鱼们 汽车 手推车 购物车

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

搜索将很快（使用指针查找而不是字符比较），您可以进行一些词干优化以节省更多空间...？

编辑：看起来我重新发明了轮子。;-)

- Chris Nava

Answer 6

关于Paul的帖子：

你考虑过为什么不能在你的情况下使用Trie吗？如果只是一个实现问题，这里有一个紧凑的Patricia trie插入和搜索C代码实现（来自NIST）：

C语言中的Patricia插入

C语言中的Patricia搜索

- Rich