如何搜索文本文件中的多個字符串

Question

我正在處理文本文件。我想用Java實現一個搜索算法。我有一個我需要搜索的文本文件。

如果我想找到一個單詞，我可以通過將所有文本放入hashmap並存儲每個單詞的出現來完成。但是，如果我想搜索兩個字符串（或可能更多），是否有任何算法？我應該把這兩個字符串散列在一起嗎？

你搜索一個全字或任何字符串：

Answer 1

這取決於文本文件的大小。通常有幾種情況下，你應該考慮：

1. 地塊的查詢在很短的文件（網頁，文章長度等的文本）的。正常語言的文本分配。一個簡單的O（n^2）算法很好。對於長度爲n的查詢，只需要一個長度爲n的窗口並將其滑過。比較並移動窗口，直到找到匹配項。這個算法並不關心單詞，所以你只是將整個搜索視爲一個大字符串（包括空格）。這可能是大多數瀏覽器所做的。 KMP或Boyer Moore不值得付出努力，因爲O（n^2）的情況非常罕見。

2. 很多的查詢在一個大文件上。預處理您的文檔並進行預處理。常見的存儲選項是後綴樹和反轉列表。如果您有多個文檔，您可以通過連接它們並單獨存儲文檔的末尾來構建一個文檔。這是收集幾乎不變的文檔數據庫的方法。

3. 如果您有多個文件，且您的冗餘度高且您的館藏經常更改，請使用KMP或Boyer Moore。例如，如果您想在DNA數據中找到某些序列，並且您經常會從實驗中獲得新的序列以找到新的DNA，那麼天真算法的O（n^2）部分將會浪費您的時間。

可能很多更多的可能性需要不同的算法和數據結構，所以你應該找出哪一個最適合你的情況。

Answer 2

一些細節暗示的方法之前，需要？

你打算在同一個不變的文件中搜索許多不同的單詞嗎？

您是否知道要一次搜索所有文字？

對於字符串有許多有效的（線性）搜索算法。如果可能的話，我會建議使用一個已經爲你寫的。

http://en.wikipedia.org/wiki/String_searching_algorithm

一個簡單的想法是使用滑動窗口哈希與窗口大小相同的搜索字符串。然後在一次傳遞中，您可以快速檢查以查看窗口哈希與搜索字符串的哈希值匹配的位置。如果匹配，請仔細檢查，看看是否有真正的匹配。