用搜索字符串。通配符

我有一個數組有這麼多的字符串，並希望搜索它的模式。這種模式可以有一些「。」通配符誰匹配（每個）1個字符（任何）。用搜索字符串。通配符

例如：

myset = {"bar", "foo", "cya", "test"} 

find(myset, "f.o") -> returns true (matches with "foo") 
find(myset, "foo.") -> returns false 
find(myset, ".e.t") -> returns true (matches with "test") 
find(myset, "cya") -> returns true (matches with "cya")

我試圖找到一種方法來快速實現這個算法，因爲myset實際上是一個非常大的陣列，但沒有我的想法具有令人滿意的複雜性（例如O(size_of(myset) * lenght(pattern))）

編輯：

myset是一個巨大的數組，在它的話並不大。我可以做一個緩慢的預處理。但我會有這麼多find()查詢，所以find()我想find()儘可能快。

來源

2011-02-02 Murilo Vasconcelos

每個模式一個或多個通配符？ – 2011-02-02 00:38:08

該集合是否修復？您可以從中創建一個模板並將模式與模板匹配。 – 2011-02-02 00:48:59

什麼語言？你可以使用現有的正則表達式庫嗎？ – 2011-02-02 00:53:53

你可以在你的設置建立的所有可能的字的語料庫的後綴樹（see this link）使用這種數據結構的複雜性將包括O（n）的一個時間成本來構建樹，其中n是所有單詞的長度總和。

一旦建立樹，查找一個字符串是否匹配應該只需要O（n），其中n是字符串的長度。處於p位置（儘可能多的p值你認爲值得-同時）的字符c的

來源

2011-02-02 01:30:00

如果集是固定的，可以預先計算的頻率，然後通過陣列搜索一次，對於每個元件檢測字符在特定的位置按照最可能早早退出的順序排列。

來源

2011-02-02 01:31:43

首先，將語料庫劃分爲每個單詞長度的集合。然後，您的查找算法可以在適當的集合上進行搜索，因爲輸入到find()總是要求匹配具有特定的長度，並且該算法可以設計爲與所有長度相同的單詞一起工作。

接下來（對於每個集合），從字符x位置的散列到匹配單詞列表創建一個散列映射。有大量散列衝突是相當不錯的。您可以使用增量和運行長度編碼來減少匹配單詞列表的大小。

要進行搜索，請爲查找輸入長度選擇合適的哈希映射，併爲每個非.字符計算該字符x位置的散列值，並將AND一起列出單詞列表，以獲得大大縮小的列表。

蠻力搜索該小得多的列表。

來源

2011-02-02 02:29:16

如果您確定集合中單詞的長度不是很大。你也許可以創造出擁有如下表：具有第一個字符幾個詞的「A」，其中有第一個字符「B」字列表，..

一覽表中有第二個字符

名單'a'，具有第二個字符'b'的單詞列表，..

等等。

當您在搜索單詞。您可以查找具有與搜索字符串的第一個字符相同的第一個字符的單詞列表。通過這個精煉的列表，查找具有與搜索字符串的第二個字符相同的第二個字符的單詞等等。你可以忽略'。'每當你遇到他們。

我知道搭建桌子可能會佔用大量的空間，但所花費的時間會顯着減少。

例如，如果你已經MYSET = {「酒吧」，「富」，「CYA」，「測試」}，你是「佛」

的時刻尋找你檢查單詞列表開始與f，你消除了其餘的設置。只是一個想法..希望它有幫助。

來源

2011-02-02 04:07:56

我有這個相同的問題，我並不完全滿意我在互聯網上找到的大多數想法/解決方案。我認爲這樣做的「正確」方法是使用Directed Acyclic Word Graph。我沒有那麼做，但是我爲Trie添加了一些額外的邏輯以獲得類似的效果。

請參閱我的isWord()實現，類似於您所需的find()接口。它的工作原理是遞歸Trie，在通配符上分支，然後將結果收集回公共集合中。（請參閱findNodes()。）

getMatchingWords()在精神上是相似的，只不過它返回的是匹配字的集合，而不是查詢是否匹配任何布爾值。

來源

2017-02-15 12:36:51 Jameson

用搜索字符串。通配符

回答

相關問題