我必须在 25 GB 的维基百科语料库中搜索一个单词。我使用了 grep 但它需要很多时间。是否有一种可以快速搜索的高效且简单的表示。另外，我想找到完全匹配的。
谢谢你。
问问题
274 次
4 回答
3
您可能希望对从单词到位置列表（字节码偏移）的映射进行索引。单词列表将按字母顺序排序。然后，您可以在这个庞大的单词列表中获得某些字母开始位置的二级索引。
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 ... | |
这是我系的自然语言教授所提倡的方式（我们在算法课程中作为实验室进行了这个练习）。
于 2010-05-15T07:33:20.823 回答
3
您是否尝试过使用索引引擎……例如，带有 Nutch 的 Lucene？Lucene 是索引引擎。Nutch 是网络爬虫。结合力量！
我忘了提... CouchDB ( http://couchdb.apache.org/ )
于 2010-05-15T07:37:04.530 回答
2
我在Boyer-Moore算法及其简化版本上取得了成功。网络上有各种语言的实现。
于 2010-05-15T07:36:21.540 回答
0
@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
这使您可以通过索引文件对语料库进行二进制搜索。如果您正在搜索上面的单词“best”，您将获取索引文件中的中间条目 79。然后您将转到语料库中的位置/字节 79 并查看那里有什么单词。它是bad。我们知道按字母顺序排列best > bad，所以位置必须在索引文件的第二半。
因此，我们在 79（第 6 位）和 15（第 12 位）之间获取中间索引，在我的示例中为 01。然后我们查看语料库中的位置/字节 88（第 9 个）以找到bear. best > bear所以我们再试一次 - 现在中间索引是 01（第 10 位）或 05（第 11 位），具体取决于您的取整方式。但显然我们会best在 1 或 2 次搜索中找到。如果我们像示例一样有 12 个单词，在最坏的情况下最多需要 4 次搜索。对于平均字长为 5 个字母和它们之间的空格的25GB 文件，这大约是 40 亿字。但是，在最坏的情况下，您只会搜索约 32 次。那时，您的程序将更多的时间花在旋转磁盘和缓冲输入上，而不是实际搜索！
此方法也适用于重复的单词。如果你想找到 word 的所有位置the，你可以二分查找the直到找到索引。然后，您将重复从索引文件中的位置减去 1，每次使用该值查看语料库。如果该位置的单词仍然是the，请继续。当您最终停止时，您在索引文件中拥有映射到the.
索引文件的创建是唯一困难的部分。您需要遍历语料库中的每个单词，建立单词及其索引的数据结构。一路上，跳过太常见或太短而无法列出的单词，如“a”、“I”、“the”、“and”、“is”等。当你完成后，你可以采用那个数据结构并将其转换为索引文件。不幸的是，对于 25GB 的文件，您的索引需要 > 32 位，因此请使用long（在 Java 中）或long long（在 C 中）来保存它。没有理由它应该是人类可读的，所以将索引写成 64 位值，而不是字符串。
我推荐的结构是自平衡二叉搜索树。每个节点都是一个字符串值（单词）和索引。然而，树只根据字符串比较节点。如果您这样做，那么按顺序遍历（左、节点、右）将为您提供准确的索引文件。
希望这可以帮助！我在几年前开发手机词典时使用的一个例子是Jim Breen 的 EDICT。由于 EUC 编码和日文字符，可能难以拾取，但意图是相同的。
于 2010-05-16T07:00:43.337 回答