Регулярное выражение, совпадающее с первым не повторяющимся персонажем

Ответ 1

Хорошо, возьмите пример tooth - вот что делает регулярное выражение (много упрощено для лучшего понимания)

Начните с t, затем посмотрите вперед в строке - и не получите lookahead, так как есть еще один t.

tooth
^  °

Далее возьмите o, посмотрите в строку и проиграйте, так как есть еще o.

tooth
 ^°

Далее возьмите второй o, посмотрите вперед в строке - нет другого o present - сопоставьте его, верните, выполните работу.

tooth
  ^

Итак, ваше регулярное выражение не соответствует первому неповторяемому символу, но первое, у которого больше нет повторений в конце строки.

Ответ 2

Ответ Себастьяна уже довольно хорошо объясняет, почему ваша текущая попытка не работает.

.NET

Так как you revo интересуется обходным решением .NET, решение становится тривиальным:

(?<letter>.)(?!.*?\k<letter>)(?<!\k<letter>.+?)

Демо-ссылка

Это работает, потому что .NET поддерживает переменные длины lookbehinds. Вы также можете получить этот результат с помощью Python (см. Ниже).

Итак, для каждой буквы (?<letter>.) мы проверяем:

• если он повторится на входе (?!.*?\k<letter>)
• если он уже встречался до (?<!\k<letter>.+?)
  (мы должны пропустить букву, которую мы тестируем при движении назад, следовательно +).

Python

Модуль 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

Хорошо, теперь все становится грязным: поскольку PCRE не поддерживает lookbehind переменной длины, нам нужно как-то вспомнить, было ли данное письмо уже встречено во входе или нет.

К сожалению, механизм regex не поддерживает поддержку оперативной памяти. Самое лучшее, что мы можем получить с точки зрения общей памяти, - это стек, но этого недостаточно для этой цели, поскольку стек позволяет нам получить доступ к его самому верхнему элементу.

Если мы соглашаемся сдерживать себя определенным алфавитом, мы можем злоупотреблять группами захвата с целью хранения флагов. Давайте посмотрим на ограниченный алфавит из трех букв abc:

# Anchor the pattern
\A

# For each letter, test to see if it 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 нашего алфавита мы создадим a-дубликат флага 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))
)

Это несколько более оптимизировано. Он сначала совпадает с текущим письмом и только затем проверяет, является ли это дубликат.

Полный шаблон для строчных букв a-z выглядит следующим образом:

# Anchor the pattern
\A

# For each letter, test to see if it 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>... ), и обработать ее содержимое как результат.

Единственная требуемая, но несколько необычная конструкция - это условная группа (?(cond)then|else).

Ответ 3

Регулярные выражения не являются оптимальными для задачи, даже если вы используете альтернативные реализации re, которые не ограничивают lookbehind строками фиксированной длины (например, регулярным выражением Мэтью Барнетта).

Самый простой способ - подсчет вхождений букв и печать первой с частотой, равной 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)))

Ответ 4

Причина, по которой ваше регулярное выражение не работает, заключается в том, что он не будет соответствовать символу, за которым следует один и тот же символ, но нет ничего, что помешало бы ему совместить символ, за которым не следует тот же символ, даже если ему предшествует один и тот же символ.