正则表达式匹配第一个非重复字符
Regular Expression Matching First Non-Repeated Character
TL;DR
re.search("(.)(?!.*)", text).group() 与文本中包含的第一个非重复字符不匹配（它始终 return 是第一个非重复字符处或之前的字符，或字符串末尾之前的字符如果没有非重复字符。我的理解是 re.search() 应该 return None 如果没有匹配）。
我只想了解为什么这个正则表达式不能按预期使用 Python re 模块工作，而不是用任何其他解决问题的方法
全背景
问题描述来自https://www.codeeval.com/open_challenges/12/。我已经使用非正则表达式方法解决了这个问题，但重新访问它以扩展我对 Python 的 re 模块的理解。
我认为可行的正则表达式（命名与未命名反向引用）是：
(?P<letter>.)(?!.*(?P=letter)) 和 (.)(?!.*)（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()
)
和一些 input/output 对是：
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 阅读的内容：
(.) 创建一个匹配任何字符的命名组，并允许以后将其反向引用为 </code>。 </li>
<li><code>(?!...) 是一种否定前瞻，它将匹配限制在 ... 不匹配的情况下。.* 表示任意数量（包括零）的字符后跟之前 (.) 匹配的任何字符re.search(pattern, string) returns 只是正则表达式模式产生匹配的第一个位置（如果找不到匹配，则 return None）.group() 等同于 .group(0)，return 是整个匹配项
我认为这些部分一起应该可以解决所述问题，并且它确实像我认为的那样对大多数输入起作用，但在 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 Whosebug
我知道 lookbehind 和 negative lookbehind 限制为最多 3 个字符的固定长度字符串，并且不能包含反向引用，即使它们的计算结果为固定长度的字符串，但我没有看到文档指定对负向的任何限制向前看。
好吧，让我们以您的 tooth 为例 - 这是正则表达式引擎的作用（为了更好地理解，进行了很多简化）
从 t 开始，然后在字符串中向前看 - 并且向前看失败，因为还有另一个 t.
tooth
^ °
接下来取 o，向前看字符串 - 失败，因为还有另一个 o.
tooth
^°
接下来取第二个 o，向前看字符串 - 没有其他 o 存在 - 匹配它，return 它，工作完成。
tooth
^
因此您的正则表达式不匹配第一个未重复的字符，而是第一个在字符串末尾没有进一步重复的字符。
你的正则表达式不起作用的原因是它不会匹配后面相同字符的字符，但没有什么可以阻止它匹配字符后面不是同一个字符，即使前面是同一个字符。
即使您使用不限制固定长度字符串（例如 Matthew Barnett 的正则表达式）的 re 替代实现，正则表达式也不是该任务的最佳选择。
最简单的方法是计算字母的出现次数并打印出现频率等于 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)))
已经很好地解释了为什么您当前的尝试不起作用。
.NET
由于您 revo 对 .NET 风格的解决方法感兴趣，因此解决方案变得微不足道：
(?<letter>.)(?!.*?\k<letter>)(?<!\k<letter>.+?)
之所以有效，是因为 .NET 支持 可变长度回顾。您还可以使用 Python 获得该结果（见下文）。
所以对于每个字母 (?<letter>.) 我们检查：
- 如果在输入中进一步重复
(?!.*?\k<letter>)
- 如果之前已经遇到过
(?<!\k<letter>.+?)
（我们必须在向后时跳过我们正在测试的字母，因此 +）。
Python
Python regex module 也支持可变长度的回顾，所以上面的正则表达式在语法上有一个小的变化：你需要用 \g 替换 \k （这很不幸，因为这个模块 \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
好吧，现在事情开始变糟了：因为 PCRE 不支持变长回顾，我们需要以某种方式记住输入中是否已经遇到给定的字母与否。
遗憾的是，正则表达式引擎不提供随机存取内存支持。就通用内存而言，我们可以获得的最好的是 stack - 但这还不够，因为堆栈只允许我们访问其最顶层的元素。
如果我们接受限制自己使用给定的字母表，我们可以滥用捕获组来存储标志。让我们在三个字母 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 两次则为真。
- 如果条件为真，then 子句为
(?<dX>)，这是一个将匹配空字符串的空捕获组。
- 如果条件为假，
dX组将不会被匹配
- 接下来，我们懒洋洋地跳过字母表中的有效字母：
[a-c]*?
- 我们在最后一场比赛中将他们淘汰出局
\K
- 现在，我们正在尝试匹配一个 字母，其
dX 标志是未 设置。为此，我们将执行一个条件分支：(?(dX)(*FAIL)|X)
- 如果
dX 匹配（意味着 X 是重复的字符），我们 (*FAIL)，强制引擎回溯并尝试不同的字母。
- 如果
dX 不 匹配，我们尝试匹配 X。此时，如果成功，我们就知道 X 是第一个不重复的字母。
模式的最后一部分也可以替换为：
(?:
a (*THEN) (?(da)(*FAIL))
| b (*THEN) (?(db)(*FAIL))
| c (*THEN) (?(dc)(*FAIL))
)
在某种程度上优化得更好。它匹配当前字母 first 并且只有 then 检查它是否重复。
小写字母 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))
)
这里是 demo on regex101，完成了单元测试。
如果您需要更大的字母表，您可以扩展此模式，但显然这不是通用解决方案。它主要用于教育目的，不应用于任何严肃的应用。
对于其他风格，您可以尝试调整模式以用更简单的等效项替换 PCRE 功能：
\A 变为 ^X (*THEN) (?(dX)(*FAIL))可以换成(?(dX)(?!)|X)- 您可以丢弃
\K 并用 (?<letter>...[=49 这样的命名组替换最后一个非捕获组 (?:...) =] 并将其内容视为结果。
唯一需要但有点不寻常的构造是条件组 (?(cond)then|else)。
TL;DR
re.search("(.)(?!.*)", text).group() 与文本中包含的第一个非重复字符不匹配（它始终 return 是第一个非重复字符处或之前的字符，或字符串末尾之前的字符如果没有非重复字符。我的理解是 re.search() 应该 return None 如果没有匹配）。
我只想了解为什么这个正则表达式不能按预期使用 Python re 模块工作，而不是用任何其他解决问题的方法
全背景
问题描述来自https://www.codeeval.com/open_challenges/12/。我已经使用非正则表达式方法解决了这个问题，但重新访问它以扩展我对 Python 的 re 模块的理解。
我认为可行的正则表达式（命名与未命名反向引用）是：
(?P<letter>.)(?!.*(?P=letter)) 和 (.)(?!.*)（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()
)
和一些 input/output 对是：
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 阅读的内容：
(.)创建一个匹配任何字符的命名组，并允许以后将其反向引用为</code>。 </li> <li><code>(?!...)是一种否定前瞻，它将匹配限制在...不匹配的情况下。.*表示任意数量（包括零）的字符后跟之前(.)匹配的任何字符re.search(pattern, string)returns 只是正则表达式模式产生匹配的第一个位置（如果找不到匹配，则 return None）.group()等同于.group(0)，return 是整个匹配项
我认为这些部分一起应该可以解决所述问题，并且它确实像我认为的那样对大多数输入起作用，但在 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 Whosebug
我知道 lookbehind 和 negative lookbehind 限制为最多 3 个字符的固定长度字符串，并且不能包含反向引用，即使它们的计算结果为固定长度的字符串，但我没有看到文档指定对负向的任何限制向前看。
好吧，让我们以您的 tooth 为例 - 这是正则表达式引擎的作用（为了更好地理解，进行了很多简化）
从 t 开始，然后在字符串中向前看 - 并且向前看失败，因为还有另一个 t.
tooth
^ °
接下来取 o，向前看字符串 - 失败，因为还有另一个 o.
tooth
^°
接下来取第二个 o，向前看字符串 - 没有其他 o 存在 - 匹配它，return 它，工作完成。
tooth
^
因此您的正则表达式不匹配第一个未重复的字符，而是第一个在字符串末尾没有进一步重复的字符。
你的正则表达式不起作用的原因是它不会匹配后面相同字符的字符，但没有什么可以阻止它匹配字符后面不是同一个字符，即使前面是同一个字符。
即使您使用不限制固定长度字符串（例如 Matthew Barnett 的正则表达式）的 re 替代实现，正则表达式也不是该任务的最佳选择。
最简单的方法是计算字母的出现次数并打印出现频率等于 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)))
.NET
由于您 revo 对 .NET 风格的解决方法感兴趣，因此解决方案变得微不足道：
(?<letter>.)(?!.*?\k<letter>)(?<!\k<letter>.+?)
之所以有效，是因为 .NET 支持 可变长度回顾。您还可以使用 Python 获得该结果（见下文）。
所以对于每个字母 (?<letter>.) 我们检查：
- 如果在输入中进一步重复
(?!.*?\k<letter>) - 如果之前已经遇到过
(?<!\k<letter>.+?)
（我们必须在向后时跳过我们正在测试的字母，因此+）。
Python
Python regex module 也支持可变长度的回顾，所以上面的正则表达式在语法上有一个小的变化：你需要用 \g 替换 \k （这很不幸，因为这个模块 \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
好吧，现在事情开始变糟了：因为 PCRE 不支持变长回顾，我们需要以某种方式记住输入中是否已经遇到给定的字母与否。
遗憾的是，正则表达式引擎不提供随机存取内存支持。就通用内存而言，我们可以获得的最好的是 stack - 但这还不够，因为堆栈只允许我们访问其最顶层的元素。
如果我们接受限制自己使用给定的字母表，我们可以滥用捕获组来存储标志。让我们在三个字母 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两次则为真。 - 如果条件为真，then 子句为
(?<dX>)，这是一个将匹配空字符串的空捕获组。 - 如果条件为假，
dX组将不会被匹配
- 条件是
- 接下来，我们懒洋洋地跳过字母表中的有效字母：
[a-c]*? - 我们在最后一场比赛中将他们淘汰出局
\K - 现在，我们正在尝试匹配一个 字母，其
dX标志是未 设置。为此，我们将执行一个条件分支：(?(dX)(*FAIL)|X)- 如果
dX匹配（意味着X是重复的字符），我们(*FAIL)，强制引擎回溯并尝试不同的字母。 - 如果
dX不 匹配，我们尝试匹配X。此时，如果成功，我们就知道X是第一个不重复的字母。
- 如果
- 这里使用了条件模式
模式的最后一部分也可以替换为：
(?:
a (*THEN) (?(da)(*FAIL))
| b (*THEN) (?(db)(*FAIL))
| c (*THEN) (?(dc)(*FAIL))
)
在某种程度上优化得更好。它匹配当前字母 first 并且只有 then 检查它是否重复。
小写字母 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))
)
这里是 demo on regex101，完成了单元测试。
如果您需要更大的字母表，您可以扩展此模式，但显然这不是通用解决方案。它主要用于教育目的，不应用于任何严肃的应用。
对于其他风格，您可以尝试调整模式以用更简单的等效项替换 PCRE 功能：
\A变为^X (*THEN) (?(dX)(*FAIL))可以换成(?(dX)(?!)|X)- 您可以丢弃
\K并用(?<letter>...[=49 这样的命名组替换最后一个非捕获组(?:...)=] 并将其内容视为结果。
唯一需要但有点不寻常的构造是条件组 (?(cond)then|else)。