设计牛津英语词典

Question

我在接受采访时被问到如何设计牛津英语词典.

我告诉他我使用的是TREE数据结构,但他回答说需要大量的内存.那么应该使用哪种其他数据结构？

Answer 1

我听过的一个数据结构在过去用于存储T9字典的移动电话中如下(嗯,这只解决了关键问题,但不是定义存储):

条目是按顺序排序的,每个条目应以从上一个条目开始的偏移开始,并从中继续.例如:

apple
4icable
7tion

会解码到苹果,适用,应用程序.但是,这可能与合并链的尝试没有什么不同,请参阅

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

维基百科揭示了有向无环字图,它与树不同,它不仅分支,而且分支可以合并,其中单词具有相同的后缀.这确实可以是一个优越的存储.

        a
       / \
  pplic   utom
       \ /
      ation