在一個單詞中搜索一個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編碼和日文字符可能難以拾取，但意圖是相同的。