gpt4 book ai didi

javascript - Node.js dom-parser tagRegExp 正则表达式匹配挂起 : Catastrophic backtracking?

转载 作者:行者123 更新时间:2023-11-30 19:50:23 24 4
gpt4 key购买 nike

我正在使用 node.js dom-parser,它(不理想地)使用正则表达式将标签从 DOM 中拉出。

您可以在以下位置找到 dom-parser: https://github.com/ershov-konst/dom-parser

有时,某些网页的 HTML(例如 https://www.ecosia.org/)会导致 node.js 应用程序挂起。我已经使用普通匹配脚本进行了测试,发现 tagRegExp 导致脚本挂起(可能是因为灾难性的回溯?)

我实际上是用它来查找链接 rel="canonical"和 href="xyz"(如果有的话,ecosia 没有规范)。

标签正则表达式:

/(<\/?[a-z][a-z0-9]*(?::[a-z][a-z0-9]*)?\s*(?:\s+[a-z0-9-_]+=(?:(?:'[\s\S]*?')|(?:"[\s\S]*?")))*\s*\/?>)|([^<]|<(?![a-z\/]))*/gi

纯JS测试脚本:

<script type="text/javascript">
var text = '... html source ...';
var text_esc = text
text_esc = text_esc.replace(/\</g, "&lt;");
text_esc = text_esc.replace(/\>/g, "&gt;");
var regex = /(<\/?[a-z][a-z0-9]*(?::[a-z][a-z0-9]*)?\s*(?:\s+[a-z0-9-_]+=(?:(?:'[\s\S]*?')|(?:"[\s\S]*?")))*\s*\/?>)|([^<]|<(?![a-z\/]))*/gi;
var found = text.match(regex);
var found_len = found.length;

document.write("Text: " + text_esc + "<br /><br />" + "Regex pattern: " + regex + "<br /><br />");

document.write("Matches: " + found_len + "<br /><br />");

for (var i=0;i<found_len;i++)
{
found[i] = found[i].replace(/\</g, "&lt;");
found[i] = found[i].replace(/\>/g, "&gt;");

document.write("[" + i + "]: " + found[i] + "<br /><br />");
}
</script>

欢迎提出任何想法。提前致谢。

最佳答案

问题是由 [\s\S]*? 引起的模式和低效 (x|[^x])*喜欢图案。

你可以使用

/(<\/?[a-z][a-z0-9]*(?::[a-z][a-z0-9]*)?\s*(?:\s+[a-z0-9-_]+=(?:'[^']*'|"[^"]*"))*\s*\/?>)|[^<]*(?:<(?![a-z\/])[^<]*)*/gi

'[\s\S]*?'变成了'[^']*'其中 [^']*是一个贪婪量化的否定字符类,匹配除 ' 以外的任何字符和 "[\s\S]*?"以同样的方式处理。否定字符类优于 .*?懒惰的对应物,因为它一次性匹配除指定字符之外的所有字符,并且正则表达式引擎不必尝试此模式之后的所有后续子模式,然后在每次失败时扩展。

([^<]|<(?![a-z\/]))*可以是unrolled作为[^<]*(?:<(?![a-z\/])[^<]*)* ,它将匹配相同的文本但速度更快(与之前相同,带有贪婪量词的否定字符类模式更快地通过文本)。

请注意,我还删除了几个冗余的非捕获组。

关于javascript - Node.js dom-parser tagRegExp 正则表达式匹配挂起 : Catastrophic backtracking?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54543223/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com