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

StackOverflow https://stackoverflow.com/questions/1418966

题

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

感谢所有帮助。

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

有帮助吗？

解决方案

也许这会奏效：

preg_match("/^(.)\\1*(.)?(?:\\1*\\2*)*(.)?(?:\\1*\\2*\\3*)*$/", $string, $matches);
// aaaaa:Pass
// abababcaaabac:Pass
// aaadsdsdads:Pass
// aasasasassa:Pass
// aasdasdsadfasf:Fail

阐释：

/
 ^                 #start of string
 (.)               #match any character in group 1
 \\1*              #match whatever group 1 was 0 or more times
 (.)?              #match any character in group 2 (optional)
 (?:\\1*\\2*)*     #match group 1 or 2, 0 or more times, 0 or more times 
                   #(non-capture group)
 (.)?              #match any character in group 3 (optional)
 (?:\\1*\\2*\\3*)* #match group 1, 2 or 3, 0 or more times, 0 or more times
                   #(non-capture group)
 $                 #end of string
/

添加好处， $ matches [1]，[2]，[3] 将包含您想要的三个字符。正则表达式查找第一个字符，然后将其存储并匹配，直到找到除该字符之外的其他内容，将其作为第二个字符捕获，尽可能多地匹配这些字符中的任意一个，捕获第三个字符，以及匹配所有三个，直到匹配失败或字符串结束并且测试通过。

修改

由于解析引擎和回溯的工作方式，这个正则表达式会快得多，请阅读bobince的解释答案：

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

其他提示

正则表达式为孩子们优化乐趣时间练习！以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中设置更快，抱歉。）

这仍然有一个问题，（。）？什么都不匹配，然后继续进行其余的匹配。即使没有\ 2匹配， \ 1 | \ 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

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

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

冒着被投票的风险，我会建议正则表达式不是为了处理这种情况。

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

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

对我来说 - 作为一个具有足够公正的正则表达知识的程序员，这听起来不像只能使用Regexp解决的问题。

更有可能需要构建hashMap /数组数据结构键：字符值：计算并迭代大文本文件，重建每行的映射。在每个新字符处检查已经遇到的字符数是否为2，如果是，则跳过当前行。

但如果一个疯狂的正则表达式黑客会提出解决方案，我很想知道。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top