正则表达式的问题 - 亵渎过滤器

我正在做一个亵渎过滤器（我知道的坏主意），我试图用Java中的正则表达式。正则表达式的问题 - 亵渎过滤器

现在这里是我的正则表达式示例字符串，它将过滤2个单词，foo和bar。

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

基本上，我把它忽略的话，那么我在骂人单词的每个字母，并|每个完整的诅咒字正则表达式之间放(?>[.,;:*'^+~\\/#|]*+|.)。

它的工作，但它很慢。

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

所以，每6个诅咒词约1ms用这个。但我的过滤器将有数百（400左右）。计算这个值需要大约66ms来过滤这个长字符串。

这是我正在构建的聊天服务器，如果我有大量的用户（比如说5,000），并且有五分之一的人在1秒内聊天（1,000条聊天消息），我需要过滤一条消息1毫秒。

我是否要求太多的正则表达式？手工制作我自己专用的过滤器会更快吗？有没有方法来优化这个？

我正在预编译正则表达式。

如果你想看到这个表达式http://regexr.com?30454

更新的效果：另一件事我所能，是在动作过滤客户端的聊天信息。

更新：我认为实现这种程度的表现会不使用正则表达式黯然手工编码解决方案的唯一途径，所以我必须做一个更基本的过滤器。

来源

2012-02-23 James T

谜底。亵渎过滤器如何区分良性“关联”和亵渎“asshat” – 2012-02-23 22:53:34

http://en.wikipedia.org/wiki/Scunthorpe_problem;） – 2012-02-23 23:01:32

@Peter你只用了几秒就打败了我;-) – DNA 2012-02-23 23:02:54

更偏执地回答你的问题“是我要求的太多了正则表达式的？” - 是

我花了2年的大部分使用正则表达式在亵渎过滤工作，并最终放弃向上。在这段时间里，我尝试了所有的这些事情：

预编译
字符类（标点符号，空格等）
非捕获组（上面提到的，可以大大降低内存和提高速度）
结合类似的正则表达式（也如上所述）
修剪空白（str.trim（））
办案（str.toLowerCase（））
组合和分离的空白（转换多个相邻的空白，以一个单一的空间，反之亦然）
写我自己的自定义正则表达式引擎（强烈不推荐的，因为它是复杂的，不可扩展）

毫无效果良好，为我的黑名单让我的系统变慢了。最后，我放弃并实施了一个线性分析过滤器，该过滤器现在是CleanSpeak的核心部分，即my company's profanity filtering product。

我们发现，一旦我们停止使用正则表达式，并且每秒处理600-700条消息到每秒超过10,000条消息，我们也能够做一些出色的多线程和其他优化。

最后，我们还发现执行线性分析使得过滤器更加准确，并且允许我们解决“scunthrope问题”以及许多其他人在这里的评论中提到的问题。

你绝对可以尝试我上面提到的所有事情，看看你能否提高你的性能，但这是一个难以解决的问题，因为正则表达式并非真正为语言分析而设计。它们被设计用于文本分析，这是一个非常不同的问题。

来源

2012-02-24 20:58:39

我希望我可以给一个以上upvote，这是非常有用的信息。 – 2012-02-24 21:05:24

我似乎无法找到关于“线性分析”的任何文章，推荐任何文章？我不确定你的意思。 – 2012-02-24 21:09:42

不幸的是我不能进入它太多，因为它的一些是IP，但我可以告诉你，线性分析与单程分析或单程分析相同。这是[词法分析器]使用的东西（http://en.wikipedia.org/wiki/Lexical_analysis）。这与正则表达式不同，因为每个正则表达式都会对字符串执行一次传递。我们最初的解决方案最终以每个黑名单字进行了大约10-20次传球。用一个500字的黑名单大概有5,000-10,000个通行证。使用我们目前的解决方案，我们只执行一次传球。 – 2012-02-25 17:35:14

您可以使用任何内置的字符类，例如：

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

检测“富”与字母之间的任何非字母，而不是“食物”或“snafoo”（原文如此）

然而，这样做的弱点是“_”算作一个字的字符:-(

我认为一个更有希望的方法是使用一个简单，快速的过滤器与一些误报，然后重新测试积极对一个更严格的过滤器。除非你的用户是总的便利口，不应该有那么多详细的检查需要。

更新：我回家后想到这个，但Qtax先到那里（请参阅其他答案） - 尝试先删除所有标点符号，然后在文本上运行纯文字模式。这应该使单词模式变得更加简单和快速，特别是当你有很多单词要测试时。

最后，注意内[]你不需要逃脱正则表达式的特殊字符，所以：

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

是OK（反斜杠仍然需要转义）

来源

2012-02-23 23:11:30 DNA

我刚刚在一个基准测试中对你的正则表达式进行了测试，由于某种原因，我的速度提高了50％，但是你对快速慢速检查的建议是个好主意。 – 2012-02-23 23:37:32

有趣的是，显然'\ W'看起来更复杂。 – DNA 2012-02-23 23:40:57

@ Bubby4j你的速度可能更快，因为它会匹配包含“bar”的字符串（因此它能够更快地完成，而不需要遍历剩余的单词）？ – Aprillion 2012-02-24 00:00:46

当你有很多的话，他们组通过它们的第一个相等的字符，你应该看到添加的单词不会超过线性时间增加。

我的意思是，如果你有两个词“foobar的”和“福”使形成像foo(?:bar|k)正则表达式。

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

另一个建议可能是只删除字符串首先在各标点，然后你可以申请一个更简单的表达。

另外，如果可以的话，尝试应用在更长的字符串表达式。因为这可能比一次只做一条消息更快。也许结合几条消息进行第一次检查。

来源

2012-02-24 00:16:15 Qtax

'？：'vs'？>'有37％的好区别，很好的建议。 – 2012-02-24 00:24:57

@ Bubby4j，如果'foo'是你的名单上的一个词，你想要像'fuozo'这样的词匹配？因为这就是你当前的表达式会匹配的。这似乎不太正确。 – Qtax 2012-02-24 00:44:53

这是一个很好的观点。希望没有太多这样的词，我只是将它们添加到白名单中。我的目标是制作诸如http://www.inversoft.com/cleanspeak-capabilities/filtering/之类的东西，他们声称只需1ms即可过滤聊天消息，适用于所有那些真正有趣的可能性。 – 2012-02-24 00:48:59

，你可以尝试更换所有

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

空字符串，然后简单地检查

\b(foo|bar)\b

UPDATE：

如果您更偏执的空间f(*+)o\1o|b(*+)a\2r

或一般f([^o]?)o\1o|b([^a]?)a\2r

来源

2012-02-24 00:26:30 Aprillion

不够灵活，人们可以轻松绕过过滤器。 – 2012-02-24 00:31:00

什么基于foo的例子将不会匹配原来的匹配？请注意，原件也有很多错误的消极和积极的，例如'frovo' - 见http://regexr.com？3045m – Aprillion 2012-02-24 00:41:09

正则表达式的问题 - 亵渎过滤器

回答

相关问题