压缩和查找大量单词列表

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

2
20字节 * 200万 = 40Mb。与计算机中典型的内存量相比,这是微不足道的。如果您将它们存储在排序数组中,您将使用二分查找进行查找,并且几乎不需要任何额外的内存。 - jkff
没错,40mb并不算多。如果你担心速度问题,那么尽可能以最简单的方式将数据保存在内存中。 - ruslik
如下所述,这40MB必须随应用程序一起提供,并且我希望保持应用程序的下载大小更小。此外,那不是唯一的部分。还有另一组“单词”的较大部分,虽然不需要可搜索,但仍可压缩,因为它将在原始字符串中占用约1GB的空间。一旦我找到适合上述情况的算法,我希望也能将其用于这个更大的集合。 - Thomas Tempelmann
此外,为什么要假设我不想在内存比标准PC少得多的设备上使用它?iPhone、嵌入式设备等都可能成为其中的一部分。 - Thomas Tempelmann
1
@Thomas,我认为这些建议来自于不断地观察人们如何微观或过早地优化事物。许多人在阅读您的短语“我想高度压缩数据”时,可能会怀疑是否存在这样的情况,而没有进一步的解释。 - Dr. belisarius
显示剩余2条评论
5个回答

7
存在一种名为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

我有一种预感,这将是答案。虽然我从未专门处理过trie,但我有一个想法,这就是它的样子。不过,我想知道,为了管理树,每个节点都必须携带其所有子节点的列表。在紧凑的文件或内存形式中,这意味着,如果树的大小超过1MB,我将需要一个32位指针加上子节点名称的大小(在按单个字节组织的树中,这将是一个字节)。我想知道这是否会导致由于这种管理而导致过多的内存消耗。 - Thomas Tempelmann
@Thomas - 看看我发布的视频。它是关于一个包含DAWG(类似于Trie但更复杂)的Boggle AI使用的文件。你不需要32位来存储指针-你可以聪明一点(偏移和位域)。 - Niki Yoshiuchi

2

感谢您提供的视频指针。虽然有点冗长(我可以跳过很多基础知识),但是它很好地解释了所有设计思路。我也发现经典的DAWG不起作用-我已经在我的原始帖子中添加了解释。 - Thomas Tempelmann

1

请查看论文"如何压缩词典"。它解释了如何构建一个最小化的有限状态自动机(也称为DAWG),并实现了单词到数字和数字到单词的一一映射。这正是你所需要的。


谢谢,但我需要每个路径都有不同的结束节点。请看我的原始(改进后)帖子为什么。 - Thomas Tempelmann
在本文中,使用FSA可以为每个路径生成唯一(且密集的)编号。您可以使用此编号将相关信息外部存储,例如在数组中、数据库中或具有固定记录长度的文件中。 - hmuelner

0

你应该熟悉索引文件。


谢谢你的帮助,但我认为我对索引文件的概念非常熟悉。我大约在1982年学习过它,我想 :) - Thomas Tempelmann

0
你有试过使用哈希映射吗?问题是,在现代操作系统架构上,操作系统将使用虚拟内存将未使用的内存段交换到磁盘上。因此,将所有内容加载到哈希映射中可能实际上是有效的。
正如jkff指出的那样,你的列表只有大约40 MB,这并不算太多。

如果我必须将它包含在我的应用程序下载中,40MB 太大了。我希望它会很受欢迎 :) - Thomas Tempelmann
此外,我尽量保持磁盘上的内存占用低。哈希表在这方面没有帮助。 - Thomas Tempelmann

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接