1. 首頁
  2. 問答
  3. 在（非常大的）文本中計算（大量）字符串

在（非常大的）文本中計算（大量）字符串

2011-06-15 85 views
0

我已經看到了Stackoverflow中「有效搜索文件中的字符串」問題的幾個變體，但不像我的情況。在（非常大的）文本中計算（大量）字符串

  • 我有一個文本文件，其中包含一個相對較大的數字（> 300K）的字符串。絕大多數這些字符串是多個詞（例如，「普萊西訴弗格森」，「約翰史密斯」等）。

  • 從那裏，我需要搜索非常大的一組文本文件（一組總共大於10GB的合法文檔）並計算這些字符串的實例。

因爲搜索字符串的數量，有多個單詞的字符串和搜索目標的大小，很多「標準」的解決方案似乎倒在路邊。

有些事情簡化問題一點點 -

  • 我不需要複雜的符號化/詞幹/等（如我所關心的唯一實例是「普萊西訴弗格森。」，不需要擔心「普萊西」，「普萊西等」）

  • 會有一些重複（例如，多個人名爲「約翰史密斯」），但是，這不是一個非常這個數據集有統計學意義的問題，所以......如果多個John Smith被合併成一個單一的計數，那麼現在就可以。

  • 我只需要計算這些特定的實例;我並不需要返回搜索結果

  • 在1個文件10個實例數相同，每10個文件

快速/骯髒的方式來解決這個問題有什麼建議1個實例？

我已經調查了NLTK，Lucene &其他人，但他們似乎是矯枉過正的問題，我試圖解決。我應該把它吸入並將所有內容導入到數據庫中？ bruteforce grep它300K次？ ;）

我的首選開發工具是Python。

要搜索的文檔主要是法律文檔這樣的 - http://www.lawnix.com/cases/plessy-ferguson.html

預期的成果是對的情況下是如何經常跨越這些文檔中引用tallys - 「普萊西v弗格森：15」

來源

2011-06-15 vijay

+0

你能否解釋多一點什麼輸入你想用它做什麼？像之前/之後的例子總是很好！真的有助於提供一個很好的答案... – 2011-06-15 17:20:54

回答

2

解決這個問題的簡單方法是用你的查詢構建一個trie（只是一個前綴樹，裏面有一個單一字符的節點列表），當你通過你的10gb文件進行搜索時，你會以文本的形式遞歸地遍歷樹火柴。

通過這種方式，您可以在選擇大文件中的每個字符位置時儘早選擇的選項，同時仍在搜索整個解決方案空間。

時間表現會非常好（與其他很多更復雜的解決方案一樣好），並且只需要足夠的空間來存儲樹（比整個字符串數少很多）和一個小緩衝區進入大文件。肯定比grecking一個db好多了300k ...

來源

2011-06-15 17:19:17 Blindy

+0

謝謝盲目！當我處理潛在的多字字符串（「John Smith」）時，任何有關填充&&樹搜索的策略建議？將「John Smith」添加到搜索結果中相對直接，但是當我搜索10GB時，似乎我可能不得不多次測試每個單詞。例如，在片段「給約翰史密斯」中，我不得不搜索「給予」，「給約翰」和「約翰史密斯」的線索 – vijay 2011-06-15 20:20:08

+0

是的，但是對於要搜索的文件中的每個字符，您已經在以指數形式修剪您的數據。就像如果你的「光標」在「John」上，你已經修剪了除樹上的「t」以外的每個起始字母，所以「John Smith」永遠不會匹配。這使得對於一個給定的字符匹配O（m），所以O（nm）總數（基本上是二次的，但是與整個文檔相比，搜索字符串的最大長度是微不足道的）。 – Blindy 2011-06-15 20:25:06

+0

至於多字字符串，我會添加它們，並在它們上運行我的正常搜索算法。我唯一要做的後處理步驟是如果我的查詢字符串有一個空格，如果我到達那裏，我「輸入」輸入中的所有空格。不過仍然是線性搜索。 – Blindy 2011-06-15 20:26:47

0

你有幾個約束你必須處理，這使得這是一個複雜的問題。

  1. 硬盤IO
  2. 內存空間
  3. 處理時間

我建議寫一個多線程/多進程Python應用程序。子進程的庫是無痛的。讓每個進程讀取一個文件，並按照Blindy建議的解析樹。完成後，它會將結果返回給父項，並將其寫入文件。

這將耗盡儘可能多的資源，因爲您可以投入它，同時允許擴展。如果你將它粘在一個beowulf集羣上，它會透明地爲你共享你的cpus中的進程。

唯一的問題是硬盤IO。在不同的硬盤上將它分成塊，並且在每個過程完成時，啓動一個新過程並加載一個文件。如果你在linux上，所有的文件可以共存在同一個文件系統名字空間中，你的程序不會知道它們的區別。

來源

2011-06-15 17:29:15

0

醜陋的蠻力解決方案將無法正常工作。

時間一個grep通過您的文檔並推斷出300k greps花費的時間（並且如果您有很多可用的機器，可能嘗試並行化），這是否可行？我的猜測是300k的搜索將不可行。例如，對大約50Mb的文件進行一次搜索花費了我大約5秒，因此對於10Gb，你會期望〜1000s，然後重複30萬次，這意味着用一臺計算機就可以在大約10年內完成搜索。你可以並行化以獲得一些改進（在一臺計算機上受到磁盤io的限制），但仍然會非常有限。我假設你希望在幾個小時內完成任務，而不是幾個月，所以這不太可能是一個解決方案。

所以你需要以某種方式索引文件。 Lucene（通過pythonsolr）或Xapian應該適合你的目的。索引文件，然後搜索索引文件。

來源

2011-06-15 17:44:32

-1

我不知道這種想法是愚蠢至極還是不行，請讓我知道...

鴻溝的文件搜索到合理的字號10/100/1000 ......和每個「塊」使用可用於SW的索引SW。這裏我正在考慮ctagsgnu global或者ptx實用程序或使用此SO post中描述的技術。

使用這種技術，您「僅」需要搜索目標字符串的索引文件。

來源

2011-06-15 18:21:07

+1

也許是一個評論，而不僅僅是一個downvote？我說這是一個愚蠢的想法... – 2011-06-15 18:52:40

相關問題

 相關問題