Regex性能问题.亵渎过滤器

Question

我正在做一个污秽过滤器(我知道这是个坏主意)，我正试图用Java中的regex来实现它。

现在这里是我的regex示例字符串，这将过滤2个单词，foo和bar。

(?i)f(?>[.,;:*`'^+~\\/#|]*+|.)o(?>[.,;:*`'^+~\\/#|]*+|.)o|b(?>[.,;:*`'^+~\\/#|]*+|.)a(?>[.,;:*`'^+~\\/#|]*+|.)r

基本上，我有一个忽略的情况，然后我将(?>[.,;:*'^+~\\/#|]*+|.)放在诅咒词的每个字母之间，|放在每个完整的诅咒词regex之间。

起作用了，但有点慢。

如果我在过滤器中有6个单词，它将在939,548纳秒内过滤一个相当长的字符串(500个字符)。当我有12次的时候，几乎是双打。

因此，大约每6个诅咒词1ms与这个。但我的过滤器将有数百(400左右)个。算上这个，过滤这个长字符串需要大约66毫秒。

这是我正在构建的聊天服务器，如果我有很多用户(例如，5,000人)和1/5的用户在1秒内聊天(1,000条聊天消息)，我需要在大约1ms内过滤一条消息。

我问得太多了吗？手工制作我自己的专用过滤器会更快吗？有什么方法来优化这个吗？

我正在预编正版。

如果您想要看到这个正则表达式http://regexr.com?30454的效果

更新:我可以做的另一件事是让聊天消息在actionscript中过滤客户端。

更新:我认为实现这种性能的唯一方法是手工编码的解决方案，而不是悲伤地使用regexp，所以我必须做一个更基本的过滤器。

Answer 1

回答你的问题“我问得太多了吗？”-是的

在两年的大部分时间里，我使用正则表达式在一个亵渎的过滤器上工作，最后我放弃了。在这段时间里，我尝试了所有这些：

• 预编译
• 字符类(标点符号、空格等)
• 非捕获组(以上所述，可以大大减少内存和提高速度)。
• 合并类似的regexp(上文也提到)
• 修整空格(str.trim())
• 案件处理(str.toLowerCase())
• 填充和解压空格(将多个相邻空格转换为单个空格，反之亦然)
• 编写我自己的自定义regexp引擎(高度不推荐，因为它很复杂且不可伸缩)

没有什么是好的，随着我的黑名单的增长，我的系统放慢了速度。最后，我放弃并实现了一个线性分析滤波器，它现在是CleanSpeak，我公司的污秽过滤产品的核心部分。

我们发现，当我们停止使用regexp并从每秒处理600-700条消息到每秒处理10,000+消息时，我们还能够进行一些很好的多线程和其他优化。

最后，我们还发现，进行线性分析使滤波器更加精确，使我们能够解决"scunthrope问题“，还有许多人在这里的评论中提到了这一点。

您肯定可以尝试以上提到的所有内容，看看是否可以提高性能，但这是一个很难解决的问题，因为regexp并不是真正为语言分析设计的。它们是为文本分析而设计的，这是一个完全不同的问题。

Answer 2

您能使用任何内置的字符类吗？

 \bf\W?o\W?o\W?\b

在字母之间用任何非字母检测"foo“，而不是”食品“或"snafoo”(原文如此)。

但是，它的缺点是"_“是一个单词字符:-(

我认为一个更有前途的方法是使用一个简单的，快速的过滤器与一些假阳性，然后重新测试阳性与一个更严格的过滤器。除非你的用户完全是厕所，否则不应该有那么多详细的检查。

Update：我回家后想到了这一点，但Qtax首先到了那里(见其他答案)--先尝试删除所有标点符号，然后在文本上运行简单的单词模式。这将使单词模式变得更简单、更快，特别是当您有很多单词需要测试时。

最后，请注意，在[]中不需要转义regex特殊字符，因此：

[.,;:*`'^+~\\/#|]

是好的(反斜杠仍然需要转义)

Answer 3

当你有很多单词的时候，按照它们的第一个相等的字符来分组，你应该会看到增加单词的线性时间的增加。

我的意思是，如果你有两个词"foobar“和"fook”，就会形成一个类似于foo(?:bar|k)的正则表达式。

使用非回溯组代替不捕获可能会提高性能。即将(?:...)替换为(?>...)。

另一个建议是先删除字符串中的所有标点符号，然后应用一个更简单的表达式。

此外，如果可以，请尝试将表达式应用于较长的字符串。因为这样做可能比一次只做一条消息更快。也许合并几条消息来进行第一次检查。