在回答关于SO的Splunk问题时，给出了以下示例文本：
msg:abc.asia-[2021-08-23T00:27:08.152+0000]"；获取/事实？factType=商业；sourceSystem=ADMIN&sourceOwner=ABC&filters=%257B%2522stringMatchFilters%2522:%255B%257B%2522key%2522BFEESCE((json_data-%253E%253E'isNotSearchable')：布尔值，%2520alse)%22522，%22522值%22522:%22522false%25222，%2522o运算符%25222:%22522EQ%2522%257D%255D，%22522multiStringMatchFilters%2522:%255B%257B%2522key%25222:%2522json_data–%253E%253E'i d’%25222、%25222值%2522:%255B%2522497011%2522%255D%257D%255D，%2522容器筛选器%2522:%255B%255D，%22522受信任的多字符串匹配筛选器%22522:%255B%255D，%2252受信任的字符串匹配筛选器%5522:%2255B%255D%257D&排序=%257B%22522排序订单%22522:%255B%257B%2522key%25222:%22522id%25222，%22522订单%22522:%22522DESC%2522%257D%255D%257D&分页=空
这个人想提取"；过滤器"；URL的一部分，如果"；factType"；是"；"商业"；
以下一体化regex将其巧妙地提取出来(假设URL总是按正确的顺序排列(即factType位于filters之前)：
factType=(?<facttype>w+).+filters=(?<filters>[^&]+)
根据regex101，它找到了670步的预期匹配
但如果我把它分解成
factType=(?<facttype>w+)
然后是
filters=(?<filters>[^&]+)
regex101报告分别用26步和16步找到的匹配
把正则表达式一分为二，使其匹配效率提高(~15倍)，怎么样？
正则表达式的主要问题是存在.+，其中.(几乎)吃任何东西，而*通常贪婪。实际上，regexp引擎分为两类：贪婪引擎和懒惰引擎。贪婪的引擎基本上消耗所有字符，只要什么都没找到就回溯，而懒惰的引擎只有在找不到下面的模式时才会消耗字符。更多的引擎是贪婪的。在默认情况下，Java是很少使用懒惰引擎的语言。幸运的是，您可以指定您想要一个带有.+?的惰性量词。这意味着引擎将尝试搜索.*的最短匹配，而不是默认情况下的最长匹配。这是人们在编写手动搜索时通常会做的事情。结果是65步，而不是670步(好10倍)。
注意，在这种情况下，量词并不总是有用的。通常最好使正则表达式更精确(即确定性)，以提高性能(通过减少非确定性自动机中错误的路径跟踪导致的可能回溯次数)。
不过，请注意，与手动搜索相比，regexp引擎通常不会得到很好的优化(只要使用高效的搜索算法)。它们非常适合使代码变得简短、灵活和可维护。对于高性能，使用本机语言的基本循环通常更好。如果使用SIMD指令对其进行矢量化(这通常不容易)，则情况尤其如此。
这里有一个正则表达式，无论这些匹配项在输入文本中的位置如何，它本质上都比.+或.+?更高效。
factType=(?<facttype>w+)(?:&(?!filters=)[^&s]*)*&filters=(?<filters>[^&]+)
- RegEx演示1
- RegEx演示2
此正则表达式可能看起来更长，但它将更高效，因为我们在匹配&之后使用负前瞻(?!filters=)来在filters查询参数之前停止匹配。
Q。什么是回溯
A。简单地说：如果匹配不完整，引擎会回溯字符串，试图找到整个匹配，直到匹配成功或失败。在上面的例子中，如果你使用.+，它匹配最长可能的匹配，直到输入结束，然后开始一次向后回溯一个位置，以找到第二个模式的整个匹配。当你使用.+?时，它只是进行懒惰的比赛，并一次向前移动一个位置以获得完整的比赛。
该建议的方法比.*、.+或.+?方法有效得多，因为它在试图找到第二模式的匹配时避免了昂贵的回溯。
RegEx详细信息：
factType=：匹配factType=(?<facttype>w+)：匹配1+字字符并在命名组facttype中捕获(?:：启动非捕获组&：匹配&(?!filters=)：当filters=在下一个位置时停止匹配[^&s]*:匹配0个或多个非空格非&字符
)*：结束非捕获组。重复此组0次或更多次&:匹配&filters=:匹配filters=(?<filters>[^&]+):在命名组filters中匹配一个或多个非空格非&字符并捕获
关于灾难性回溯的相关文章