針對大數據集存儲和匹配名稱的高效方法

Question

對於防止數據丟失的工具，我需要查找不同類型的數據，例如駕駛證號碼，社會安全號碼，姓名等。這是基於模式的，因此可以使用與正則表達式匹配的模式來查找，名稱恰好是一個非常寬泛的類別。幾乎可以有任何一組字符可以形成一個名字。然而，爲了使它成爲一個有意義的查詢，我想我應該只查找它們對照定義的名稱字典。這就是我的想法。

提供名稱字典作爲配置項目。對於每個用例而言，這看起來更明智，名稱可能因不同的地理區域而異。我正在尋找在Java中執行此操作的最佳實踐。基本上這些是問題 -

1. 什麼是良好的數據結構來存儲名稱。 Set是第一個選項，是否有更好的選擇，如內存數據庫。
2. 我應該如何着手在大型數據集中搜索這些名稱。這些數據集非常大，我只能夠逐行讀取它們。
3. 還有其他的選擇嗎？

Answer 1

看看concurrent-trees和CQEngine項目。

Answer 2

您可以使用全文索引或在線搜索。

我更喜歡全文索引，例如，與Lucene。您將必須定義索引器如何在文本中找到令牌（通過定義令牌模式和不關心模式）。

• 已知模式（例如，許可證編號）應在索引時註釋其類型。查詢註釋類型的索引（例如許可證編號）將返回所有包含的許可證編號。
• 靈活模式（如名稱）應作爲標記索引。然後，您可以遍歷合法名稱集合並使用它查詢索引。
• 這種方法並不是最靈活的，但是對數據文件集的更改（只需將新文件放入索引）或一組名稱（僅查詢索引中的新名稱） 。
• 在這種方法中它是不是真的你如何存儲集名稱

的另一種方法是搜索多個字符串（名稱）的表現有關。請注意，對於多個字符串有特殊的搜索算法，並且大多數算法都有一個首選的參數範圍（模式大小，字母大小，要搜索的模式數量）。您可以在StringBench處獲得一些展示。

• 此方法允許您更靈活的字符串模式。
• 但是，修改名稱集並不健壯（然後必須重複完整的搜索）。
• 多串通常會接受一組字符串來搜索的，但他們會在此設置一個特定於算法的方式（使用最多的一個線索）

編輯：

的高效搜索可以使用基於DFA的自動機完成多種模式/字符串。

我第一次想在文本中有效地搜索我選擇dk.brics.automaton。它的自動機非常高效，但它針對不匹配進行了優化（搜索以天真的方式完成）。

我轉移到了我自己的實現rexlex。它基於DFA，但比金磚四國稍慢。搜索算法並不像brics那樣天真，但增加了一些開銷。

你會找到一個link to a benchmark比較兩個。該基準可視化基於DFA的正則表達式的問題 - 如果正則表達式很大，編譯這種DFA的時間可能會非常昂貴。

我目前看好stringandchars實現多串/模式的搜索的。它專注於搜索性能，但我不知道它與上述解決方案相比如何。在上面的解決方案中，在文本中搜索多個正則表達式模式的最常見情況將更加高效。