針對大量可比對象測試現有字符串的最佳方法

假設您有一個定義值的首字母縮略詞列表（例如AB1，DE2，CC3），並且您需要檢查字符串值（例如「Happy： DE2 | 234「）來查看在字符串中是否找到首字母縮略詞。對於首字母縮略詞的簡短列表，我通常會創建一個使用分隔符（例如（AB1 | DE2 | CC3））的簡單RegEx，然後查找匹配項。針對大量可比對象測試現有字符串的最佳方法

但是，如果有超過30個首字母縮略詞匹配，我該如何解決這個問題？使用相同的技術（醜陋）還是有更高效和更優雅的方法來完成此任務會有意義嗎？

請記住示例首字母縮略詞列表和示例字符串不是我正在使用的實際數據格式，而只是表達我的挑戰的一種方式。

順便說一句，我讀了SO related question，但並不認爲它適用於我想要完成的事情。

編輯：我忘了，包括我需要捕捉匹配的值，因此使用正則表達式的選擇...

來源

2009-01-31 Dscoduc

就個人而言，我不認爲30是一個正則表達式特別大，所以我不會太快排除它。你可以用一行代碼創建正則表達式：

var acronyms = new[] { "AB", "BC", "CD", "ZZAB" }; 
var regex = new Regex(string.Join("|", acronyms), RegexOptions.Compiled); 
for (var match = regex.Match("ZZZABCDZZZ"); match.Success; match = match.NextMatch()) 
    Console.WriteLine(match.Value); 
// returns AB and CD

所以代碼是相對優雅和可維護的。如果你知道一些測試的首字母縮寫詞數量的上限，誰知道已經在正則表達式引擎中建立了什麼樣的優化。您將可以免費從未來的正則表達式引擎優化中受益。除非您有理由相信性能會成爲問題，否則請簡單。

另一方面，正則表達式可能有其他限制，例如默認情況下，如果您有AB，BC和CD的縮寫詞，那麼它只會返回其中的兩個作爲「ABCD」中的匹配項。所以它擅長告訴你這是一個縮寫，但你需要小心捕捉多個比賽。

當性能成爲我的問題（> 10,000項）時，我把'首字母縮寫詞'放在HashSet中，然後搜索文本的每個子字符串（從最小首字母縮寫詞長度到最大首字母縮寫詞長度）。這對我來說確實很好，因爲源文本非常短。我之前沒有聽說過它，但是首先看一下你提到的問題中提到的Aho-Corasick算法，它似乎是解決這個問題的更好的通用解決方案。

來源

2009-01-31 05:39:41 codybartfast

如果縮寫的（在上面的例子一樣）有固定的大小，你可以計算哈希所有這些（可以在每個應用程序生命中完成一次），然後將這些字符串拆分爲這些重疊的部分，併爲它們計算哈希值。然後，你只需要從一個數組搜索另一個數組的值。

你可能可以創建一個後綴/前綴樹或類似的縮寫詞和搜索使用這些信息，維基百科有很多算法可以做到這一點。

您也可以爲每個首字母縮略詞創建一個確定性自動機，但它與以前的方法非常相似。

來源

2009-01-31 04:37:11 vava

不幸的是，首字母縮略詞沒有固定的大小，所以我不認爲散列會有幫助...但有趣的想法，謝謝！ – Dscoduc 2009-01-31 04:43:35

爲什麼不簡單地拆分字符串並比較返回的列表？在這種情況下，使用REGEX似乎是不必要的開銷。我知道你的格式可能會有所不同，但它似乎你可以：

拆分基於「稱號分離器」，你的情況冒號的字符串：
拍攝效果的下半年中，首字母縮寫字符串，並根據首字母縮寫詞分隔符分割它，在這種情況下爲管道|
最後，迭代首字母縮寫詞的新分割的列表，並與嵌套比較每到你的候選名單for循環

編輯：如果你只需要知道，如果一個特定的縮寫或設置縮略詞存在於一個字符串中，請使用.Search（）方法而不是.Match（）。

來源

2009-01-31 04:42:08 Soviut

我沒有想過嵌套循環。我給出的示例字符串和首字母縮寫詞是;亞洲多種不同格式的首字母縮略詞存儲...因此，分割字符串不會像使用正則表達式那樣高效... – Dscoduc 2009-01-31 04:45:47

對不起，我的意思是我會搜索的字符串有很多不同的格式，所以我不能可靠地分割字符串值... – Dscoduc 2009-01-31 04:47:34

正則表達式的方法看起來很高效和優雅。當然，在構建表達式時不得不注意非轉義字符，或者由於複雜性或大小限制而無法對其進行編譯。

做到這一點的另一種方法是構造一個trie data structure來表示所有的縮略詞（這可能有點重複正則表達式匹配器正在做什麼）。當你遍歷字符串中的每個字符時，你會創建一個指向該樹根的新指針，並將現有指針提前到適當的子元素（如果有的話）。當任何指針到達葉子時你會得到一個匹配。

來源

2009-01-31 05:26:49

唉！我只是瞥了一下trie數據結構鏈接，現在我的大腦受到了傷害......儘管如此，我應該仔細觀察它，看看它是否可行......感謝您的建議！ – Dscoduc 2009-01-31 05:32:58

是的，這可能是不值得的，因爲正則表達式真的很簡單。 – 2009-01-31 05:35:17

這是我想出來的。如果您能提供任何建設性的批評，我將不勝感激。

首先，創建一個保存我的每一個縮寫的枚舉：

enum acronym 
{ AB1,DE2,CC3 }

接下來，我創建了枚舉的字符串數組：

string[] acronyms = Enum.GetNames(typeof(acronym));

最後我遍歷字符串數組和[執行的regex.match方法：

foreach (string a in acronyms) 
{ 
    Match aMatch = Regex.Match(input, a.ToString(), RegexOptions.None); 
    if (aMatch.Success) 
    { 
     ...<do something>... 
     break; 
    } 
}

看到有什麼不對嗎？

來源

2009-01-31 05:30:29 Dscoduc

針對大量可比對象測試現有字符串的最佳方法

回答

相關問題