java中的高效字符串匹配

我有一串句子（推文）和超過1000萬個名字。我想確定一個句子（tweet）是否包含提及1000萬個名字中的一個。我可以爲所有可能的模式編譯正則表達式，但我真的很想知道是否有一個有效的算法來做到這一點。java中的高效字符串匹配

謝謝，

2012-09-22 DotNet

你是什麼意思：1000萬個正則表達式，還是一個正則表達式，所有千萬個名字一起變成了一個交替？無論哪種方式，聽起來都比應該允許的人更有趣。 ;）但嚴重的是，這不是一個正則表達式的工作。 –

2012-09-22 16:21:49 ruakh

謝謝，看着它。 – DotNet

您可以嘗試使用Bloom filter。 Demo here。

2012-09-22 16:26:30 mindas

謝謝。這很有趣。 Bloom fliter可能會有所幫助。我現在會嘗試。 – DotNet

我不認爲你需要模式匹配，如果你只是尋求一個簡單的字符串（名稱）的發生。如果你實際上是在瞄準嘰嘰喳喳的名字 - 當他們在推文中提到時，他們是不是以@符號作爲前綴的？如果是這樣，首先尋找@符號並從那裏繼續。

要檢查@之後的字符串是否是您的1,000萬字符串中的一個，則ruakh提出的前綴樹絕對是一個好主意。

2012-09-22 16:31:15 Ridcully

謝謝。它們並不總是以@作爲前綴。有些品牌不是。 – DotNet

你可以從相反的方向去解決它。隨着句子的進入，將其分成令牌併爲每個令牌構建RegEx模式，如^ 令牌 \ s *。比較每一個與你的1000萬個名字中的每一個，假設每個名字在線。

2012-09-22 16:31:24 milam

謝謝，但這涉及到分句，以檢測給予數百萬句子相當昂貴的名詞。我希望我能正確理解你的建議。 – DotNet

回答