如何有效地檢查給定的字符串是否包含數組中的單詞

我正在構建一個應用程序，用戶在其中輸入一段文本。一旦提交，我需要檢查該文本塊是否包含來自我預先定義的單詞列表中的單詞。
單詞列表很大，大約在50K左右，所以我需要找出一種方法，我可以高效快速地完成檢查。
這裏有一些解決方案，我想過了，但他們似乎真的效率低下如何有效地檢查給定的字符串是否包含數組中的單詞

選項1： 創建的應用程序代碼的函數，僅僅通過每個預定的字，並檢查循環，如果這個詞是塊文字

如

var wordList = ['fox','dog','tree']; //in my app this list will be large 
function contains(userInput) { 
    for(i in wordList){ 
     if(userInput.indexOf(wordList[i]) > -1) 
      return true;  
    } 
    return false 
}

選項2： 文本和單詞列表的塊將被存儲在數據庫中，所以我可以做一個SQL語句，這樣

e.g

SELECT * 
FROM UserInput ui 
    INNER JOIN WordList wl ON wl.word LIKE CONCAT('%', ui.InputText, '%')

有沒有更好的方式來做到這一點？

來源

2014-11-04 MakkyNZ

如果您正在查看大於小數據集（和50k條件）的任何內容，那麼我肯定會在數據庫中執行任何數據操作。

你是對的，開放式LIKE不會是非常高性能，但它會比在數據庫外執行快幾個數量級。如果你的用戶輸入保證是一個完整的單詞，那麼你可以打破WordList中的所有內容來分隔單詞並進行完全匹配搜索。如果你不能保證從UserInput有一個完整的字，然後我會用你的選項2.

如果性能是超級重要的，那麼你也可以來看一下，全文索引

MySQL：http://dev.mysql.com/doc/refman/5.6/en/innodb-fulltext-index.html
MS SQL：http://msdn.microsoft.com/en-us/library/ms187317.aspx。

來源

2014-11-04 15:50:27

您可以在數據庫中或使用LINQ來做到這一點。

在空間上拆分用戶輸入，以便您擁有包含用戶輸入詞的數組或表值參數。然後只要對你的單詞列表進行內部連接。加入之後剩下的任何東西都是兩個地方存在的詞。性能會很好。

SELECT SomeColumn 
FROM WordList wl 
JOIN @tvp ui ON wl.SomeColumn = ui.SomeColumn

它比LIKE搜索快幾個數量級，而且比全文索引設置要簡單得多。

來源

2014-11-04 16:11:26 DVK

Aho–Corasick string matching algorithm

有在文章C＃實現鏈接。

來源

2014-11-04 16:14:36

我肯定會在應用程序方面做到這一點..但我假設列表是一個「壞詞」列表..並且它不會經常改變..如果假設是正確的..那麼代碼會是這樣的

static List<String> Chached; 
List<String> GetBadWords() 
{ 
    if(Chached==null) 
    { 
     //load words from db into static array 
     Chached.Sort();//!important step 
    } 
    return Chached 
} 

public bool IstextValid(String sText) 
{ 
    List<String> oBadWords = GetBadWords() 
    foreach(String sWord in Rexex.Split(sText,@"\W"))//split by anything not alphanumeric 
     if(oBadWords.BinarySearch(sWord)>=0)//since is sorted we can do binary search O(log n) 
      return false; 
    return true; 
}

基本上做有兩個優化，以考慮

保持列表在內存中，沒有必要不斷地嘮叨SQL
使用二進制搜索，以避免Ø （N * M）

來源

2014-11-04 16:24:59 CaldasGSM

如何有效地檢查給定的字符串是否包含數組中的單詞

回答

相關問題