我有一个巨大的多字节序列列表(我们称它们为单词)，我需要将它们存储在一个文件中并且我需要能够快速查找。巨大意味着:大约有 200 万个，每个长度为 10-20 个字节。
此外，每个单词都应该有一个与之关联的标签值，这样我就可以使用它来为每个项目引用更多(外部)数据(因此，拼写检查器的字典在这里不起作用仅提供 HitTest )。
如果这只是在内存中，并且内存充足，我可以简单地将所有单词存储在散列映射(又名字典，又名键值对)中，或存储在用于二进制搜索的排序列表中。
但是，我想对数据进行高度压缩，并且还希望不必将数据读入内存，而是在文件中搜索。
由于单词主要基于英语，因此单词中的某些“sillables”很可能比其他单词出现得更频繁 - 这可能有助于高效算法。
有人可以为我指出有效的技术或算法吗？
甚至代码示例？
更新
我认为 DAWG 或任何类似的以这种方式将路径路由到公共(public)后缀的方法对我来说不起作用，因为那样我就无法用单独的值标记每个完整的单词路径。如果我要检测公共(public)后缀，我必须将它们放入它们自己的字典(查找表)中，以便 trie 节点可以引用它们，但该节点将保留其自己的结束节点以存储该路径的标记值。
事实上，这可能是要走的路:
我可以尝试查找常用的字符序列，而不是只为单个字符构建树节点，并为它们创建一个节点。这样，单个节点可以覆盖多个字符，可能会导致更好的压缩。
现在，如果这可行，我如何才能真正找到我所有短语中经常使用的子序列？ 大约有 200 万个短语通常由 1-3 个单词组成，很难运行所有可能子字符串的所有排列...
最佳答案
存在一种称为 trie 的数据结构。我相信这种数据结构非常适合您的要求。基本上，trie 是一棵树，其中每个节点都是一个字母，每个节点都有子节点。在基于字母的 trie 中，每个节点将有 26 个 child 。
根据您使用的语言，在创建时将其存储为可变长度列表可能更容易或更好。
这个结构给出了: a) 快速搜索。跟随一个长度为 n 的单词，您可以在树中的 n 个链接中找到该字符串。 b) 压缩。存储常用前缀。
示例:单词 BANANA 和 BANAL 都将具有相等的 B、A、N、A 节点，然后最后一个 (A) 节点将具有 2 个子节点，L 和 N。您的节点还可以存储有关该单词的其他信息。
(http://en.wikipedia.org/wiki/Trie)
安德鲁 JS
关于algorithm - 大量单词的压缩和查找，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4218065/