比O（n）glob匹配器好嗎？

問題：給定一個globs的列表，我需要從列表中找到（並返回）一個給定字符串匹配或確定無匹配的glob。排除安裝時間，性能必須優於線性搜索所有水珠的：比O（n）glob匹配器好嗎？

foreach glob in list: 
    if glob.matches(string): 
    return glob 
return None

問題：是否有任何可用的庫（C++首選）這個？

編輯：多一點思考後，我在想我可以說，這是可以做到。考慮到globs或多或少具有不同語法的正則表達式，使用glob語法的lex的運行時版本將適合賬單。

鑑於問題可以簡單地歸結爲一個已知問題，我只對實施的解決方案感興趣。

來源

2011-03-25 BCS

它甚至有可能？鑑於26個水珠（'* A *'，'* B *'，'* C *'...'* Z *'）是有可能不檢查所有26個水珠（因此爲O（n）） – xanatos 2011-03-25 15:04:40

薩那託斯：考慮到這一點，你應該期望在一場比賽之前只需要檢查少量球。或者你可以將它壓縮到正則表達式'。* [A-Z]。*'並運行它。 – BCS 2011-03-25 15:08:27

Glob是正則表達式的子集（關於表達力，而不是確切的語法）。因此Globs可以轉換爲確定性有限自動機（DFA），並且可以組合形成單個DFA，以識別單個DFA的聯合。 DAs具有O（n）的複雜度，其中n是字符串的長度。自動機的構造數量僅影響建立時間（即創建自動機），而不影響運行時間。

來源

2011-03-25 15:06:33 Oswald

我不包括設置時間。 – BCS 2011-03-25 15:09:28

我剛剛注意到，改變了我的答案。 – Oswald 2011-03-25 15:15:00

我不認爲有可能有比線性時間更好的球體數量。爲了證明一個字符串與任何一個字符串都不匹配，你必須檢查每一個匹配，否則你永遠不會知道你是否跳過匹配。

編輯：在一般情況下，這是不可能使用globs。正如在評論中指出的那樣，可以組合一些球體的組合（首先猜測一個體系可能是有用的，其中每個節點指示要匹配的下一個字母以及您仍需要檢查的球體），導致工作量較少搜索。

在一般情況下，也可以將一組球體轉換爲相應的正則表達式。

表現這種匹配真的是這樣一個問題，你需要改進它？你有沒有考慮過一個更基本的算法重寫可能會更好？

來源

2011-03-25 15:09:51

假設您無法將某些匹配工作與某些設置工作結合使用：例如如果'/富/酒吧/ *'不匹配，5位，'/富/巴茲/ *'不必進行檢查，如果第二位，失敗後'/鹹菜/ *'可以跳過。 – BCS 2011-03-25 15:16:05

從技術上講，您可以嘗試創建一個「不匹配」的「否定」表達式。它可以是簡單的，但我不知道......我一直在尋找兩個非simplifiable和不negatable表情......雖然水珠的結合顯然是爲O（n），也許是負水珠的交集是少一點。 – xanatos 2011-03-25 15:22:34

可能只是在某些特定情況下。如果你能以某種方式預測某些球體不符合你的絃線。

來源

2011-03-25 15:10:20 cprogrammer

將你的球體轉換成正則表達式（一系列簡單的字符串操作可以實現這一點 - *成爲.*等）。將它們組合成一個正則表達式，使用|並將結果分配給每個glob的不同捕獲組，以便您可以確定匹配時匹配哪個glob。依靠您最喜歡的正則表達式將正則表達式編譯爲DFA，該DFA有希望更好地處理，而不是組成部分的線性步驟，但在最常見的情況下，速度不會更快。

來源

2011-03-25 15:15:28 moonshadow

Wha？如果給定足夠的免費啓動時間，任何正則表達式都可以在'lenght（input）'時間內匹配，所以在多於一個glob的情況下，它應該更快。我錯過了什麼？ – BCS 2011-03-25 15:20:42

你如何找到哪個捕獲組被填充小於'O（n）'？ – BCS 2011-03-25 15:25:20

@BCS：任何特定的正則表達式（這是真正的「正規軍」;有的Perl的「正則表達式」語法不符合條件）可以在O匹配（長度（輸入））的時間，是的。但是，當正則表達式的長度也是一個相關變量時，您需要一個不同的計算複雜度模型。 – aschepler 2011-03-25 15:27:25

我想看看你的申請是否適合shift-reduce parser如bison。他們使用查找表，這是一個痛苦的設置或更改並使用更多的內存，但速度非常快。從技術上講，它不是身體可能比O（N）最壞的情況下，但根據您的水珠，你的字符串，你的分詞做的更好，使用這樣的技術可以讓你的平均情況比這更好，因爲它消除了不匹配匹配的模式，而不必每次都檢查每個模式。

來源

2011-03-25 15:31:43

查看本文的回答：http://stackoverflow.com/問題/ 5434209 /好於上水珠匹配器/ 5434304＃5434304 – BCS 2011-03-26 16:09:10

比O（n）glob匹配器好嗎？

回答

相關問題