在RegEx中,如何找到包含不超过3个唯一字符的行？

Question

我循环浏览一个大文本文件,我正在查找包含不超过3个不同字符的行(但是,这些字符可以无限重复).我假设最好的方法是做某种正则表达式.

所有帮助表示赞赏.

(我正在用PHP编写脚本,如果有帮助的话)

Answer 1

儿童正则表达式优化有趣的时间锻炼!以gnarf的正则表达式为出发点:

^(.)\1*(.)?(?:\1*\2*)*(.)?(?:\1*\2*\3*)*$

我注意到这里有嵌套和顺序*,这可能导致大量的回溯.例如,在'abcaaax'中,它会尝试匹配最后一串'a'作为长度为3的单个\ 1*,长度为2的\ 1*后跟一个\ 1,一个\ 1后跟一个2长度1*,或三个单匹配\ 1s.当你有更长的字符串时,这个问题会变得更糟,特别是当由于正则表达式而没有什么能阻止\ 1与\ 2相同的字符.

^(.)\1*(.)?(?:\1|\2)*(.)?(?:\1|\2|\3)*$

这是原始版本的两倍,在Python的PCRE匹配器上进行测试.(这比在PHP中设置更快,抱歉.)

这仍然存在一个问题,即(.)?无法匹配,然后继续进行剩下的比赛.\1|\2即使没有匹配的\ 2,仍会匹配\ 1,导致潜在的回溯试图在它们无法导致匹配时引入先前的\1|\2和\1|\2|\3子句.这可以通过?在整个尾随子句中移动可选项来解决:

^(.)\1*(?:(.)(?:\1|\2)*(?:(.)(?:\1|\2|\3)*)?)?$

这又快了两倍.

仍然存在一个潜在的问题,即\ 1,\ 2和\ 3中的任何一个都可以是相同的字符,当表达式不匹配时可能导致更多的回溯.这将通过使用否定前瞻与前一个字符不匹配来阻止它:

^(.)\1*(?:(?!\1)(.)(?:\1|\2)*(?:(?!\1|\2)(.)(?:\1|\2|\3)*)?)?$

然而,在我的随机测试数据的Python中,我没有注意到这一点的显着加速.根据测试数据,您的里程可能因PHP而异,但已经足够好了.占有匹配(*+)可能有帮助,如果这在这里可用.

没有正则表达式比易于阅读的Python替代方案表现更好:

len(set(s))<=3

PHP中的类似方法可能与count_chars有关:

strlen(count_chars($s, 3))<=3

我没有测试速度,但我非常希望这比正则表达式快,除了读取更好,更好.

所以基本上我只是浪费时间摆弄正则表达式.不要浪费你的时间,在使用正则表达式之前首先寻找简单的字符串方法!

Answer 2

有可能被投票,我会建议正则表达式不是为了处理这种情况.

您可以匹配一个字符或一组字符,但是您无法记住已经找到一组字符以排除那些进一步匹配的字符.

我建议您保留一个字符集,在开始新行之前重置它,然后在越过该行时添加元素.只要集合中的元素数超过3,就会删除当前行并继续下一行.