设计牛津英语词典

Question

在一次面试中，我被问到如何设计“牛津英语词典”。

我告诉他我将使用树形数据结构，但他回答说这将占用大量内存。那么应该使用哪种其他数据结构呢？

Answer 1

我听说过去在手机中用来存储T9字典的一种数据结构如下(好吧，这只解决了关键问题，但没有解决定义存储)：

条目是排序的，每个条目都应该从前一个条目的偏移量开始，也就是从前一个条目继续的位置。例如：

apple
4icable
7tion

将解码为苹果，适用，应用。但是，这可能与使用合并链进行尝试没有太大区别，请参见

appl -> e 
     -> ica -> ble
            -> tion

维基百科发现了Directed acyclic word graph，它与树的不同之处在于，它不仅可以分支，而且可以合并分支，其中的单词具有相同的后缀。这确实可能是一个更好的存储。

        a
       / \
  pplic   utom
       \ /
      ation

Answer 2

它不会占用太多内存。你的回答很好。也许是在1995年。算你走运吧。

Answer 3

正如其他人所提到的，如果没有足够的屋顶来放置设计良好的trie，那么很可能也没有空间来容纳任何其他类型的索引。由于这是一个面试问题，听起来他似乎是想引导你使用经典的核心外数据结构，比如B-tree。

或者，一个好的回答可能是询问更多的信息，比如“你想在这个数据结构上做什么类型的操作，你需要什么样的性能？”如果你只是想要一个拼写检查，那么Bloom filter可能是最有效的“数据结构”……