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

all*_*aws 6 java data-structures

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

  • 存储~100k英文单词列表
  • 需要使用最少的内存
  • 查找需要合理,但不必快速闪电

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

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

  • 回答:列表中是否有XYZ字样?
  • 生成XYZ周围的单词邻域,其中一个字母不同

谢谢你的好建议

pax*_*blo 8

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

  • 与最后一个共同的字符数(一个字节); 和
  • 新的结局.

所以单词列表

HERE            would encode as    THIS
sanctimonious                      0,sanctimonious
sanction                           6,on
sanguine                           3,guine
trivial                            0,trivial
Run Code Online (Sandbox Code Playgroud)

你在那里直接保存7个字节(19%),我怀疑由于相邻单词的(公共前缀)之间的最小距离,对于20,000字的字典保存是相似的.

为了加速查找,内存中有一个26条目表,它保存了以a,b,c,...,z开头的单词的起始偏移量.这些偏移处的字总是以0作为第一个字节,因为它们没有与前一个字相同的字母.

这似乎是一种特里但没有指针,如果树中的每个字符都有一个与之关联的4字节指针,这肯定会占用太多空间.

请注意,这是来自我的CP/M日,那里的记忆比现在更加稀缺.


Pau*_*mer 6

Patricia trie可能更合适:

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

我的(模糊)记忆告诉我在一些早期的全文搜索引擎中使用了...

保罗.


Mik*_*ott 3

你在干什么?如果是拼写检查,您可以使用布隆过滤器 - 请参阅此代码 kata