在一个单词中搜索一个25 GB的语料库

Question

我必须为一个单词搜索25 GB的维基百科语料库。我使用了grep，但它花费了很多时间。是否有快速搜索的高效且简单的表示形式？另外，我想找到完全匹配。

谢谢。

Answer 1

您可能想要做一个从单词到位置列表（字节码偏移）的映射索引。单词列表将按字母顺序排序。然后你可以有一个二级索引，在这个大的单词列表中某些字母开头。

Lazy hash   | Word index    | Corpus 
aaa starts at X | aaa      | lorem ipsum dolor 
aab starts at Y | ...      | sit amet ..... 
aac ...   | and 486, 549, 684, ... | ... 
... ...   |       | 
zzz ...   |       | 

这是我部门的自然语言教授所倡导的方式（我们在算法课程中做了这个练习，作为实验）。

Answer 2

我已经成功使用了Boyer-Moore算法及其simplified version。有各种各样的语言在网络上浮动的实现。

Answer 3

你有没有尝试过使用索引引擎...说，与Nutch的Lucene？ Lucene是索引引擎。 Nutch是网络爬虫。结合力量！

我忘了提... CouchDB的（http://couchdb.apache.org/）

Answer 4

@aloobe不得不使用映射的话位置的索引文件的答案。我只想对此进行阐述，但我认为OP正在寻找的答案可能只是Boyer-Moore。

索引文件看起来像这样（简化使用人类可读的2位数字）：

53 17 89 03 
77 79 29 39 
88 01 05 15 
... 

上面的每个条目是一个字节一个单词或字母的偏移，你已经被视为重要，足以指数。在实践中，你不会使用字母索引，因为你的索引文件比你的语料库大！

诀窍是，如果你在与地点的位置来替代的话，你的索引文件将是语料库的字母顺序排序的版本：

and and are as 
ate bad bat bay 
bear best bin binge 

这使你做Binary Search上该语料通过索引文件。如果您正在搜索上面的单词“best”，那么您将抓住索引文件中的中间条目79，然后您将位于语料库中的位置/字节79并查看该单词是否存在。它是bad。我们知道按字母顺序best > bad，所以位置必须在索引文件的后半部分。

所以我们抓住79（6th）和15（12th）之间的中间索引，在我的例子中是01。然后我们查看语料库中的位置/字节88（第9）以找到bear。 best > bear所以我们再试一次 - 中间指数现在是01（10）或05（11），这取决于你如何轮回。但很显然，我们会在1到2次搜索中找到best。如果我们有12个单词，最糟糕的情况下最多需要4次搜索。对于一个平均字长为5个字母和空格的文件25GB文件，这是〜40亿字。但是，在最坏的情况下，您只能搜索〜32次。在这一点上，你的程序的更多时间花在旋转磁盘和缓冲输入上，而不是实际搜索！

此方法也适用于重复单词。如果您想查找单词the的所有位置，则可以在the上进行二进制搜索，直至找到索引。然后你会重复从索引文件中的位置减去1，每次使用该值查看语料库。如果该位置的单词仍然是the，请继续。当您最终停止时，索引文件中的最早索引映射到the。

创建索引文件是唯一困难的部分。您需要查看语料库中的每个单词，建立单词及其索引的数据结构。一路上，跳过那些过于常见或短名单的词，如“a”，“I”，“the”，“and”，“is”等。完成后，您可以采用该数据结构并将其转换为索引文件。对于25GB文件，不幸的是，您的索引需要大于32位，因此请使用long（Java）或long long（C）来保存它。没有理由它应该是人类可读的，因此将索引写为64位值，而不是字符串。

我建议的结构是self-balancing binary search tree。每个节点都是一个字符串值（单词）和索引。但是，树仅根据字符串比较节点。如果你这样做，然后按顺序遍历（左，节点，右）将给你完全的索引文件。

希望这会有所帮助！我多年前开发手机词典的一个例子是Jim Breen's EDICT。由于EUC编码和日文字符可能难以拾取，但意图是相同的。