給定一組龐大的街道名稱，測試文本是否包含該街道名稱的最有效方法是什麼？

Question

我有一個有趣的問題，我需要幫助。我目前的工作對我的節目的特徵和偶然到這個問題

1. 我有一個巨大的存儲在數據庫中印尼（> 10萬行）街道名稱的列表， 每個街道名稱可能有不止1字。例如：「Sudirman」，「Gatot Subroto」或「Jalan Asia Afrika」都是合法的街道名稱

2. 在數據庫中有一堆文本（> 1百萬行），我將其分成了句子。現在，我需要做的功能（確切功能）是測試句子中是否有街道名稱或不是，所以只是一個真/假測試

   我試圖通過做這些來解決它步驟：

a。將街道名稱放入鑰匙，價值哈希值

b。將每個句子拆分成單詞

c。測試是否的話是在散

這是快，但不會多話

另一種替代方案，我認爲的工作是做下列步驟操作：

一個。將每個句子拆分爲單詞

b。使用LIKE語句查詢數據庫（例如，SELECT #### FROM street_table WHERE name like'％word％'）

c。如果查詢返回了一行，這意味着該句子包含街道名稱

現在，這個解決方案將是一個非常密集的IO。

所以我的問題是「什麼是最有效的方法來做這個測試」？不管編程語言如何。我主要在Python中做這個，但只要我能理解概念，任何語言都可以。

============編輯1 ============ =====

這是週期性的嗎？

是的，我會以1分鐘的間隔調用此功能/功能。每次調用將100列文本至少和測試他們對街道名稱數據庫

Answer 1

一個簡單的解決方案是創建一個字典/多地圖的第一個字的街道名稱=>全街名（S）。當你迭代句子中的每個單詞時，你會查找潛在的街道名稱，並檢查是否有匹配（通過查看下一個單詞）。

該算法應該相當容易實現，並且應該表現得相當好。

Answer 2

所以，你有一個文件，並希望SEACH如果它包含您的任何街道名稱的列表？

Turbo Boyer-Moore是一個很好的起點。

Here is more information on turbo boyer moore

但是，我堅信，你將不得不做一些關於你的街道名稱列表的組織。應該有一些桶訪問它，即您可以輕鬆地對街道名稱進行篩選：

下面的例子： 街道名稱：亞太區街道

您可以通過訪問列表： A（獲得所有與一開始的起點） AS（獲得了所有的AS開始的起點）

等等...

我相信你應該有很多桶爲中，至少有26個（第一個字母）* 26 （第二個字母）

more information about bucketing

Answer 3

使用nlp，您可以確定句子中的專有名詞。請參閱下面的鏈接。

http://nlp.stanford.edu/software/lex-parser.shtml

斯坦福解析器處於其計算精確。一旦你有專有名詞，你可以決定採取的方法。

Answer 4

Aho-Corasick算法可能非常有用。其中一個優點是它的運行時間與您要搜索的字詞數量無關（只是您要搜索的文字的長度）。如果您的街道名稱列表不經常更改，它將特別有用。

http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm