我有一个庞大的多字节序列列表(称为单词),需要存储在文件中,并且需要快速查找。庞大意味着:大约有200万个这样的单词,每个单词长度为10-20字节。
此外,每个单词都应该有一个与之关联的标记值,以便我可以使用它来引用更多的(外部)数据 (因此,拼写检查器的词典在这里不适用,因为它只提供了命中测试)。
如果这只是在内存中,并且如果内存很充足,我可以简单地将所有单词存储在哈希映射(也称为字典、键值对)中,或者在排序列表中进行二进制搜索。
然而,我想高度压缩数据,并且也不想将数据读入内存而是在文件中进行搜索。
由于单词大多基于英语,因此某些单词中的特定“音节”出现的可能性更高——这可能对有效算法有所帮助。
有人能够指导我一个高效的技术或算法吗?
甚至还有代码示例吗?
更新:
我发现DAWG或类似的东西通过将路径路由到常见后缀的方式对我行不通,因为那样我就不能为每个完整单词路径附上独立的值了。如果我要检测常见后缀,我必须将它们放入自己的字典(查找表)中,以便trie节点可以引用它们,但节点将保留自己的结束节点以存储该路径的标记值。
事实上,这可能是正确的方法:
不是仅为单个字符构建树节点,而是尝试找到经常使用的字符序列,并为其创建节点。这样,单个节点可以覆盖多个字符,可能会导致更好的压缩。
现在,如果这是可行的,我如何实际找到所有短语中经常使用的子序列?由于大约有200万个短语,每个短语通常由1-3个单词组成,所以运行所有可能子字符串的所有排列将很困难...
此外,每个单词都应该有一个与之关联的标记值,以便我可以使用它来引用更多的(外部)数据 (因此,拼写检查器的词典在这里不适用,因为它只提供了命中测试)。
如果这只是在内存中,并且如果内存很充足,我可以简单地将所有单词存储在哈希映射(也称为字典、键值对)中,或者在排序列表中进行二进制搜索。
然而,我想高度压缩数据,并且也不想将数据读入内存而是在文件中进行搜索。
由于单词大多基于英语,因此某些单词中的特定“音节”出现的可能性更高——这可能对有效算法有所帮助。
有人能够指导我一个高效的技术或算法吗?
甚至还有代码示例吗?
更新:
我发现DAWG或类似的东西通过将路径路由到常见后缀的方式对我行不通,因为那样我就不能为每个完整单词路径附上独立的值了。如果我要检测常见后缀,我必须将它们放入自己的字典(查找表)中,以便trie节点可以引用它们,但节点将保留自己的结束节点以存储该路径的标记值。
事实上,这可能是正确的方法:
不是仅为单个字符构建树节点,而是尝试找到经常使用的字符序列,并为其创建节点。这样,单个节点可以覆盖多个字符,可能会导致更好的压缩。
现在,如果这是可行的,我如何实际找到所有短语中经常使用的子序列?由于大约有200万个短语,每个短语通常由1-3个单词组成,所以运行所有可能子字符串的所有排列将很困难...