有沒有辦法找到最強的正則表達式

Question

我想知道是否存在一種方法從給定的匹配正則表達式列表中找到最匹配的正則表達式。

假設給出以下正則表達式。

"apple.*" 
"ap.*" 
"app.*" 

而當我們搜索匹配字符串"apples"超出上述表達式。正確的答案應該是。 "apple.*"。這裏所有三個正則表達式在我們對他們評估單詞「apple」時都是有效的。但最強烈匹配的正則表達式是"apple.*"，因爲兩個字符串幾乎完全相同。

如果有人能夠爲此提出一種方法，那將會很棒。我期待在C++中實現這一點

Answer 1

似乎顯而易見的方法是從檢查哪些正則表達式匹配所選字符串開始。顯然，任何不匹配的東西在那個時候都會被淘汰。

然後取那些匹配並計算它們包含的文字（非通配符）字符的數量。文字數量最多的文字勝出。在這樣的情況下，這可能（會）變得棘手：(short|muchmuchlonger)

假設這針對的目標相匹配，這是目前尚不清楚是否short或muchmuchlonger在比賽中使用，而這種差距可能決定該模式是否是「最強「的比賽。

如果是平局，你可以（例如）看像[abcd]這樣的套。在這種情況下，您可能會將較小的設置爲像[abc]這樣的比較大的集合，如[A-Z]。然而，後者表明，計數集大小的代碼需要知道正則表達式的語法（否則，這兩個看起來像三個字符）。

最後，您要查找的是模式中的字符拒絕字符的程度。像.*這樣的東西不會拒絕任何東西，所以它不會增加正則表達式的強度（或沒有）。一個簡單的文字如a或9拒絕所有，但一個可能性，所以它增加了很大的力量。對於一組，被拒絕的字符數量與接受的字符數量成反比。

然後我們得到諸如[:alpha:]或[:alnum:]之類的東西。再次，這些基本上只是集合，所以你必須根據它們接受/拒絕的字符數量來評估它們。

要做到這一點，您可能希望將每個「正片」作爲子表達式標記，因此您會得到sub_match個對象，告訴您每個對象的實際匹配程度。然後你會乘以正則表達式的一部分將被拒絕的字符的百分比來獲得每個字符的強度。把這些放在一起，你會得到一個整體的「強度」分數。