高效地搜索正則表達式集合

如果我有一些未知數量的正則表達式（零個或多個，希望少於幾千個），搜索與給定字符串匹配的正則表達式的有效方法是什麼？高效地搜索正則表達式集合

我應該使用什麼類型的容器，算法和/或數據結構？如果我想找到唯一匹配的正則表達式，而不是所有正則表達式匹配，這是不同的嗎？那些不同於只想知道有多少匹配？

讓我換一種方式，讓我們假設我有一個用戶輸入任意字符串，我有一些正則表達式容器。我可以按照我選擇的任何方式設計容器，並以我選擇的任何方式進行搜索。如果我想要一個與該集合的用戶輸入相匹配的所有正則表達式的列表，我該怎麼做？如果我只想知道有多少匹配存在，該怎麼辦？如果我只是想確保比賽的獨特性呢？

來源

2016-07-14 Sqeaky

將它們組合成一個表達式，根據需要「捕捉」原始表達式。 – greybeard

這些（數學上講）的正則表達式，還是他們隨機設置的圖靈完全匹配函數，按照大多數正則表達式庫？他們是確切的還是子串匹配？ – rici

@rici PCRE/ECMAScript正則表達式和完全匹配。但我很好奇所有變化的答案。 – Sqeaky

如果在嘗試將字符串與它們進行匹配之前，可以對正則表達式執行一些預計算，那麼可以將它們的聯合轉換爲可以同時匹配所有字符串的DFA。

請參見：https://en.wikipedia.org/wiki/Deterministic_finite_automaton

這種方法經常用於解析器和編譯器的詞法分析（分詞）。無論您投入多少正則表達式或它們有多複雜，DFA的好處在於它的速度（快速）是相同的。

這並不容易，但有工具。如果您使用的是Java，那麼我有一個可以使用的開源項目：http://mtimmerm.github.io/dfalex/。要回答你的其他問題，如果你願意，你可以從中得到所有匹配正則表達式的集合。

如果你感興趣的是如何做自己的過程一般包括把你的正則表達式到NFA（https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton）使用湯普森的建設（https://en.wikipedia.org/wiki/Thompson%27s_construction），然後用子集構造轉換NFA到DFA的（ https://en.wikipedia.org/wiki/Powerset_construction），然後通常用Hopcroft算法最小化DFA（https://en.wikipedia.org/wiki/DFA_minimization）

有很多優化和技巧的空間。

祝你好運！

P.S.我應該注意一些事情：1）通常不能使用具有反向引用的正則表達式來使用DFA。 2）DFA在理論上可能呈指數級增長。這幾乎不會偶然發生，但如果您的正則表達式是由潛在的惡意人員輸入的，那麼您將不得不對此做出一些處理。

來源

2016-07-15 00:21:39

這很好，我不知道DFA最小化是一件事情。至於我的潛在惡意用戶，他們大多會傷害自己。 – Sqeaky

甲PHP例如：

<?php 
$regex_array = array(
    "/regex_1/" => 0, 
    "/regex_2/" => 0, 
    "/regex_3/" => 0 // and so on and so forth 
); 

$strings_array = array(
    "input_string_1", 
    "input_string_2", 
    "input_string_3" // and so on and so forth 
); 

foreach ($regex_array as $key => $value) 
    foreach ($strings_array as $current_string) 
    if (preg_match($key, $current_string)) 
     $regex_array[$key]++; 
?>

Here的的運行過程中出現的代碼。

來源

2016-07-14 17:05:57 horcrux

我幾年沒有碰過PHP，但是這不僅僅是一種線性搜索嗎？ – Sqeaky

我不會將自己的答案標記爲答案，除非沒有人在幾天內擊敗它。

到目前爲止，我已經不值一文唯一的想法就是把正則表達式分成兩堆集裝箱內的一個加時。

在一堆中，每個正則表達式都帶有一些通配符，字符類或其他任何使它偏離常規字符串的東西。我會稱之爲RegexPile。

進入另一堆去的所有正則表達式是字符串或trivially可轉換爲字符串。因爲字符串很容易匹配，並且算法很好理解，所以我可以說這個堆將被排序，並且將被排序，並且在二進制搜索中查找字符串是微不足道的。我會稱之爲SortedStringArray。

天真，我可以線性搜索RegexPile和SortedStringArray做一個二進制搜索。這至少可以讓我跳過一些比較，在時間或空間方面花費很少，但也沒有太多真正的優化。

它在計算上是類似的，但是如果我做這樣的事情，我想我會爲每個正則表達式（或每個小組的正則表達式）在RegexPile中啓動一個線程。我的想法是，任何給定的正則表達式可能會帶來無限的數量，因爲正則表達式可以做到這一點。然後，如果任何線程花費太長時間，我可能會因超時而失敗並提前終止所有線程。我也認爲大多數人會在第一個字符上失敗，這意味着大多數這些線程在第一個字符被選中後會消失。隨着現在大多數系統提供的便宜寫時複製線程，此線程產卵應該足夠便宜，許多線程在我完成產卵之前將關閉，只有相似的線程在任何時候都會徘徊。然後我在另一個線程中執行二進制代碼SortedStringArray。

來源

2016-07-14 17:20:38 Sqeaky

高效地搜索正則表達式集合

回答

相關問題