代码之家 › 专栏 › 技术社区 › Boolean

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

wikipedia data-structures algorithm

2

Boolean · 技术社区 · 16 年前

我必须在一个25GB的维基百科语料库中搜索一个单词。我用过grep,但要花很多时间。是否有一个高效且简单的表示法可以快速搜索。另外,我想找到完全匹配的。

非常感谢。

4 回复 | 直到 16 年前

1

3

aioobe 16 年前

您可能需要对从单词到位置列表(字节码偏移)的映射进行索引。单词列表将按字母顺序排列。然后你就可以有一个二级索引,在这个大的单词列表中,某些字母从哪里开始。

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   ...           |                            |

这是我所在系的自然语言教授提倡的方法(我们在一个算法课程的实验室里做了这个练习)。

2

3

gvaish 16 年前

你试过使用索引引擎吗。。。喂,卢森和努奇?Lucene是索引引擎。Nutch是网络爬虫。结合力量!

我忘了提。。。库奇达( http://couchdb.apache.org/ )

3

2

Michael Barker 16 年前

我在这方面很成功 Boyer-Moore 算法及其应用 simplified version . 网络上有各种语言的实现。

4

0

Phil 16 年前

@aloobe的答案是使用一个索引文件将单词映射到位置。我只是想解释一下,尽管我认为OP想要的答案可能只是博伊尔·摩尔。

索引文件如下所示(简化为使用人类可读的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 bad . 我们是按字母顺序知道的 best > bad ,因此位置必须在索引文件的后半部分。

bear . best > bear 所以我们再试一次-现在中间的索引是01(第10个)或05(第11个),这取决于你如何取整。但很明显我们会发现 best 在1或2次以上的搜索中。如果我们有12个像这个例子一样的单词,在最坏的情况下最多需要4次搜索。为了一个

这种方法也适用于重复的单词。如果你想找到单词的所有位置 the ,您将在 这个 直到你找到索引。那么你要从这个位置减去1 索引文件 重复地,每次使用该值查看语料库。如果那个地方的字还在 这个 这个 .

索引文件的创建是唯一困难的部分。你需要浏览语料库中的每个单词,建立单词及其索引的数据结构。在此过程中,跳过那些太常见或太短而无法列出的单词,如“a”、“I”、“the”、“and”、“is”等。完成后,可以将该数据结构转换为索引文件。对于25GB的文件,您的索引必须是>不幸的是,32位,所以使用 long long long (C)拿着它。没有理由让它对您来说是可读的,所以将索引写成64位值,而不是字符串。

我建议的结构是 self-balancing binary search tree . 每个节点都是一个字符串值(单词)和索引。但是,树仅基于字符串比较节点。如果这样做,那么按顺序遍历(左、节点、右)将准确地给出索引文件。

Jim Breen's EDICT