如何識別文本中的一組關鍵詞

我有一大組關鍵詞。給定一個文本，我希望能夠只識別那些出現在關鍵字列表中的單詞，並忽略所有其他單詞。解決這個問題的最好方法是什麼？如何識別文本中的一組關鍵詞

2011-05-20 kc3

Aho-Corasick algorithm是用於識別較大源串中一組模式字符串的快速算法。由於它運行時間爲O（m + n + z），其中n是您嘗試匹配的所有模式字符串的總大小，因此它由多個搜索實用程序以及許多防病毒程序使用，m是要搜索的字符串，z是匹配的總數。此外，如果您事先知道要搜索的字符串，則可以離線執行O（n）工作，並將搜索時間縮短爲O（m + z）。

來源

2011-05-20 16:07:41 templatetypedef

字符串和單詞之間有區別。該算法的一個關鍵思想是，當你不能匹配'foo'時，它知道你可能會匹配'oof'。但是，如果你想匹配整個單詞，那不是真的。 – btilly 2011-05-20 16:55:58

這是一個好點。你可以在字符串之前和之後存儲空格（例如，「HELLO」存儲爲「HELLO」，或者也可以使用句點和點作爲邊界） – templatetypedef 2011-05-20 22:28:07

實際上是愚蠢的錯誤當你不能匹配foo ''你可能會匹配'''，但不* *'oof'。反正只是略過算法的複雜性並且只使用一個trie。 – btilly 2011-05-20 22:34:09

把你的關鍵字放入一個數據結構，以便於查找。例如，一個哈希表或二叉樹。如果你是核心人物，你可以從你的關鍵字創建一個完美的散列。
使用DFA將輸入分解爲「單詞」。這可以使用正則表達式庫或簡單的狀態機來完成。
查找每個「單詞」以查看它是否是您的關鍵字之一。

來源

2011-05-20 16:13:22

將您的文字存儲在trie中。

走你的文字。每當你開始一個單詞時，開始走路。如果你在單詞結尾的單詞結尾，這是你感興趣的單詞，否則它不是。

圍繞單詞的定義，你會有輕微的複雜化。特別是非單詞字符通常以單詞結尾，但也有例外，如don't。

請注意，某些正則表達式引擎（Perl的任何最新版本的Perl）都足夠智能，可以自動構建一個樹並嘗試與其匹配。因此，你很有可能只用管道將你的單詞連接起來，然後將它放在正則表達式引擎中，並獲得良好的性能。

如果這不起作用，您可以構造一個正則表達式來編碼一個trie。例如，給定列表foo,bar,baz,blat正則表達式/\b(foo|b(?:a(?:r|z)|lat))\b/應該匹配那些詞並且僅匹配那些詞。它可能不會像手動C那樣高效（例如在Perl的引擎中，你會遇到對慢性能複雜正則表達式的檢查，並且它可能會做一些愚蠢的回溯操作，它不需要做）但將很多放在一起工作較少。

來源

2011-05-20 17:10:57 btilly

如果我的關鍵詞列表是10000左右。方法仍然有效嗎？ – kc3 2011-05-20 17:52:30

@ kc3：是的，建立一個trie的努力大致與你所有單詞中的字母總數成正比，一旦建立，匹配的時間大致與文本的大小成比例。大概是因爲你存儲可以引入各種因素的trie的一些實現細節。 – btilly 2011-05-20 18:19:25

如何識別文本中的一組關鍵詞

回答

相關問題