ste*_*121 29 python regex regex-lookarounds
TL; DR
re.search("(.)(?!.*\1)", text).group()与文本中包含的第一个非重复字符不匹配(它总是在第一个非重复字符处或之前返回一个字符,如果没有非重复字符,则返回字符串结尾之前.我的理解是如果没有匹配,.search()应该返回None.我只是想了解为什么这个正则表达式没有按照预期使用Python re模块工作,而不是任何其他解决问题的方法
完整的背景
问题描述来自https://www.codeeval.com/open_challenges/12/.我已经使用非正则表达式方法解决了这个问题,但重新访问它以扩展我对Python re模块的理解.我认为可行的正则表达式(命名与未命名的反向引用)是:
(?P<letter>.)(?!.*(?P=letter))和(.)(?!.*\1)(在python2和python3中的结果相同)
我的整个程序看起来像这样
import re
import sys
with open(sys.argv[1], 'r') as test_cases:
for test in test_cases:
print(re.search("(?P<letter>.)(?!.*(?P=letter))",
test.strip()
).group()
)
和一些输入/输出对是:
rain | r
teetthing | e
cardiff | c
kangaroo | k
god | g
newtown | e
taxation | x
refurbished | f
substantially | u
根据我在https://docs.python.org/2/library/re.html上所读到的内容:
(.)创建一个匹配任何字符的命名组,并允许以后反向引用它\1.(?!...)是一个负向前瞻,它将匹配限制在...不匹配的情况下..*\1表示任何数字(包括零)字符,后跟(.)前面匹配的任何字符re.search(pattern, string) 只返回正则表达式模式产生匹配的第一个位置(如果找不到匹配则返回None).group()相当于.group(0)返回整个匹配我认为这些部分应该能够解决所述的问题,并且它确实像大多数输入一样工作,但是失败了teething.在它上面抛出类似的问题表明它似乎忽略了重复的字符,如果它们是连续的:
tooth | o # fails on consecutive repeated characters
aardvark | d # but does ok if it sees them later
aah | a # verified last one didn't work just because it was at start
heh | e # but it works for this one
hehe | h # What? It thinks h matches (lookahead maybe doesn't find "heh"?)
heho | e # but it definitely finds "heh" and stops "h" from matching here
hahah | a # so now it won't match h but will match a
hahxyz | a # but it realizes there are 2 h characters here...
hahxyza | h # ... Ok time for StackOverflow
我知道lookbehind和负向lookbehind限制为3个字符最大固定长度字符串,并且即使它们评估为固定长度字符串也不能包含反向引用,但我没有看到文档指定对负向前瞻的任何限制.
Seb*_*ske 15
好吧,让我们tooth举个例子 - 这是正则表达式引擎的作用(为了更好地理解,大量简化)
t然后开始,然后向前看字符串 - 并且没有前瞻,因为还有另一个t.
tooth
^ °
接下来o,在字符串中向前看 - 然后失败,因为还有另一个o.
tooth
^°
接下来拿第二个o,向前看字符串 - 没有其他o礼物 - 匹配它,返回它,完成工作.
tooth
^
因此,你的正则表达式与第一个未重复的字符不匹配,但是第一个正则表达式没有与字符串末尾重复进一步重复.
Luc*_*ski 14
塞巴斯蒂安的答案已经很好地解释了为什么你目前的尝试不起作用.
由于你对 revo感兴趣的.NET风格解决方案,解决方案变得微不足道:
(?<letter>.)(?!.*?\k<letter>)(?<!\k<letter>.+?)
这是有效的,因为.NET支持可变长度的lookbehinds.您也可以使用Python获得该结果(见下文).
所以(?<letter>.)我们检查每封信:
(?!.*?\k<letter>) (?<!\k<letter>.+?)+).Python 正则表达式模块还支持可变长度的lookbehinds,因此上面的正则表达式将使用一个小的语法更改:你需要替换\k为\g(这非常不幸,因为这个模块\g是一个组反向引用,而PCRE则是一个递归).
正则表达式是:
(?<letter>.)(?!.*?\g<letter>)(?<!\g<letter>.+?)
这是一个例子:
$ python
Python 2.7.10 (default, Jun 1 2015, 18:05:38)
[GCC 4.9.2] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import regex
>>> regex.search(r'(?<letter>.)(?!.*?\g<letter>)(?<!\g<letter>.+?)', 'tooth')
<regex.Match object; span=(4, 5), match='h'>
好吧,现在事情开始变得肮脏:因为PCRE不支持可变长度的lookbehinds,我们需要以某种方式记住输入中是否已经遇到给定的字母.
不幸的是,正则表达式引擎不提供随机存取内存支持.我们在通用内存方面可以得到的最好的是一个堆栈 - 但这还不足以达到此目的,因为堆栈只允许我们访问其最顶层的元素.
如果我们接受将自己限制在给定的字母表中,我们可以滥用捕获组来存储标记.让我们在三个字母的有限字母表中看到这个abc:
# Anchor the pattern
\A
# For each letter, test to see if it's duplicated in the input string
(?(?=[^a]*+a[^a]*a)(?<da>))
(?(?=[^b]*+b[^b]*b)(?<db>))
(?(?=[^c]*+c[^c]*c)(?<dc>))
# Skip any duplicated letter and throw it away
[a-c]*?\K
# Check if the next letter is a duplicate
(?:
(?(da)(*FAIL)|a)
| (?(db)(*FAIL)|b)
| (?(dc)(*FAIL)|c)
)
这是如何工作的:
\A锚确保我们只处理输入字符串一次X我们字母表中的每个字母,我们将设置一个重复标记dX:
(?(cond)then|else)那里使用条件模式:
(?=[^X]*+X[^X]*X)如果输入字符串包含X两次字母,则条件为true .(?<dX>)是一个空的捕获组,它将与空字符串匹配.dX组将不匹配[a-c]*?\KdX标志的字母.为此,我们将做一个条件分支:(?(dX)(*FAIL)|X)
dX匹配(意味着这X是一个重复的字符),我们(*FAIL),强制引擎回溯并尝试不同的字母.dX是不匹配的,我们尽力配合X.此时,如果成功,我们知道这X是第一个非重复的字母.该模式的最后一部分也可以替换为:
(?:
a (*THEN) (?(da)(*FAIL))
| b (*THEN) (?(db)(*FAIL))
| c (*THEN) (?(dc)(*FAIL))
)
哪个稍微优化一下.它匹配当前信第一和唯一然后检查它是否是一个副本.
小写字母的完整模式a-z如下所示:
# Anchor the pattern
\A
# For each letter, test to see if it's duplicated in the input string
(?(?=[^a]*+a[^a]*a)(?<da>))
(?(?=[^b]*+b[^b]*b)(?<db>))
(?(?=[^c]*+c[^c]*c)(?<dc>))
(?(?=[^d]*+d[^d]*d)(?<dd>))
(?(?=[^e]*+e[^e]*e)(?<de>))
(?(?=[^f]*+f[^f]*f)(?<df>))
(?(?=[^g]*+g[^g]*g)(?<dg>))
(?(?=[^h]*+h[^h]*h)(?<dh>))
(?(?=[^i]*+i[^i]*i)(?<di>))
(?(?=[^j]*+j[^j]*j)(?<dj>))
(?(?=[^k]*+k[^k]*k)(?<dk>))
(?(?=[^l]*+l[^l]*l)(?<dl>))
(?(?=[^m]*+m[^m]*m)(?<dm>))
(?(?=[^n]*+n[^n]*n)(?<dn>))
(?(?=[^o]*+o[^o]*o)(?<do>))
(?(?=[^p]*+p[^p]*p)(?<dp>))
(?(?=[^q]*+q[^q]*q)(?<dq>))
(?(?=[^r]*+r[^r]*r)(?<dr>))
(?(?=[^s]*+s[^s]*s)(?<ds>))
(?(?=[^t]*+t[^t]*t)(?<dt>))
(?(?=[^u]*+u[^u]*u)(?<du>))
(?(?=[^v]*+v[^v]*v)(?<dv>))
(?(?=[^w]*+w[^w]*w)(?<dw>))
(?(?=[^x]*+x[^x]*x)(?<dx>))
(?(?=[^y]*+y[^y]*y)(?<dy>))
(?(?=[^z]*+z[^z]*z)(?<dz>))
# Skip any duplicated letter and throw it away
[a-z]*?\K
# Check if the next letter is a duplicate
(?:
a (*THEN) (?(da)(*FAIL))
| b (*THEN) (?(db)(*FAIL))
| c (*THEN) (?(dc)(*FAIL))
| d (*THEN) (?(dd)(*FAIL))
| e (*THEN) (?(de)(*FAIL))
| f (*THEN) (?(df)(*FAIL))
| g (*THEN) (?(dg)(*FAIL))
| h (*THEN) (?(dh)(*FAIL))
| i (*THEN) (?(di)(*FAIL))
| j (*THEN) (?(dj)(*FAIL))
| k (*THEN) (?(dk)(*FAIL))
| l (*THEN) (?(dl)(*FAIL))
| m (*THEN) (?(dm)(*FAIL))
| n (*THEN) (?(dn)(*FAIL))
| o (*THEN) (?(do)(*FAIL))
| p (*THEN) (?(dp)(*FAIL))
| q (*THEN) (?(dq)(*FAIL))
| r (*THEN) (?(dr)(*FAIL))
| s (*THEN) (?(ds)(*FAIL))
| t (*THEN) (?(dt)(*FAIL))
| u (*THEN) (?(du)(*FAIL))
| v (*THEN) (?(dv)(*FAIL))
| w (*THEN) (?(dw)(*FAIL))
| x (*THEN) (?(dx)(*FAIL))
| y (*THEN) (?(dy)(*FAIL))
| z (*THEN) (?(dz)(*FAIL))
)
如果您需要更大的字母表,可以扩展此模式,但显然这不是通用解决方案.它主要是教育兴趣,不应该用于任何严肃的应用程序.
对于其他风格,您可以尝试调整模式以使用更简单的等效替换PCRE功能:
\A 变 ^X (*THEN) (?(dX)(*FAIL)) 可以替换为 (?(dX)(?!)|X)\K并替换最后一个非capturnig组(?:... )使用像(?<letter>... 这样的命名组),并将其内容视为结果.唯一需要但有点不寻常的构造是条件组(?(cond)then|else).
小智 5
正则表达式对于任务来说不是最佳的,即使您使用re的替代实现也不限制固定长度字符串的后观(例如Matthew Barnett的正则表达式).
最简单的方法是计算字母的出现次数并打印频率等于1的第一个字母:
import sys
from collections import Counter, OrderedDict
# Counter that remembers that remembers the order entries were added
class OrderedCounter(Counter, OrderedDict):
pass
# Calling next() once only gives the first entry
first=next
with open(sys.argv[1], 'r') as test_cases:
for test in test_cases:
lettfreq = OrderedCounter(test)
print(first((l for l in lettfreq if lettfreq[l] == 1)))