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