最佳字符串搜索算法各地

Question

我在哪裏我比較大的數據的代碼，比如網頁的針對一個文件中的一些單詞的來源。什麼是最好的算法使用？

可以有2種情況：

1. 如果我有大量的單詞來比較的來源，在這種情況下，對於一個普通的字符串搜索算法，它會採取一個字，與數據進行比較，取下一個數據並與數據進行比較等等，直到全部完成。

2. 我只有一對夫婦的文件和普通字符串搜索將是確定的話，但仍需要降低儘可能的時間。

什麼算法最好？我瞭解Boyer-Moore和Rabin-Karp搜索算法。 儘管Boyer-Moore搜索似乎很快，但我還想要其他算法的名稱及其比較。

Answer 1

在這兩種情況下，我想你可能想建立一個帕特里夏·特里（也叫基數樹）。最重要的是，查找時間是O（k），其中k是特里字符串中的最大長度。

Answer 2

注意，博耶 - 穆爾是搜索文本中的文本（幾個的話）。

如果你想要的是確定一些個人的話，那麼它來要容易得多：

• 把每查找字典中的結構字（不管它是什麼）
• 查找每個單詞的字典中的文字

這最着名的意思是你把文本看作是一個流，並且不需要一次把所有內容都保存在內存中（這對於一個文件遊標的典型例子來說非常有用）。

至於字典的結構，我會推薦一個簡單的哈希表。與樹結構相比，它的工作方式非常有記憶力。