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

Question

我正在遍历一个大文本文件，我正在寻找包含不超过 3 个不同字符的行(但是，这些字符可以无限重复)。我假设最好的方法是使用某种正则表达式。

感谢所有帮助。

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

Answer 1

正则表达式优化 child 趣味练习!以 gnarf 的正则表达式为起点:

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

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

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

这是在 Python 的 PCRE 匹配器上测试的原始速度的两倍多。 (这比用 PHP 设置要快，抱歉。)

这仍然有一个问题，(.)? 不能匹配任何内容，然后继续进行剩余的匹配。 \1|\2 仍然匹配\1 即使没有\2 匹配，导致潜在的回溯尝试引入 \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

我还没有测试过速度，但我非常希望它比正则表达式更快，而且更易读。

所以基本上我完全是在浪费时间摆弄正则表达式。不要浪费你的时间，在求助于正则表达式之前先寻找简单的字符串方法!