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

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 Stackru

Я знаю, что lookbehind и отрицательный lookbehind ограничены строками с фиксированной длиной не более 3 символов и не могут содержать обратных ссылок, даже если они оцениваются как строки фиксированной длины, но я не видел, чтобы документация указывала какие-либо ограничения на отрицательный просмотр.

Источник

4 ответа

Решение

Ну давай возьмем твои tooth пример - вот что делает regex-engine (очень упрощенный для лучшего понимания)

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

tooth
^  °

Следующий дубль oпосмотри вперед в строке - и провалишься, так как есть другой o,

tooth
 ^°

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

tooth
  ^

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

Источник

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

.СЕТЬ

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

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

Демо-ссылка

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

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

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

питон

Модуль регулярных выражений Python также поддерживает просмотр за разной длиной, поэтому приведенное выше регулярное выражение будет работать с небольшим синтаксическим изменением: вам необходимо заменить \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 не поддерживает вид сзади переменной длины, нам нужно как-то вспомнить, встречалась ли уже заданная буква во вводе или нет.

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

Если мы соглашаемся ограничиться определенным алфавитом, мы можем злоупотреблять захватом групп с целью хранения флагов. Давайте посмотрим на это на ограниченном алфавите из трех букв 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))
)

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

Полный шаблон для строчных букв 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))
)

А вот демонстрация на regex101, в комплекте с юнит-тестами.

Вы можете расширить этот шаблон, если вам нужен больший алфавит, но, очевидно, это не универсальное решение. Это в первую очередь представляет образовательный интерес и не должно использоваться для каких-либо серьезных приложений.

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

  • \A становится ^
  • X (*THEN) (?(dX)(*FAIL)) можно заменить на (?(dX)(?!)|X)
  • Вы можете выбросить \K и заменить последнюю некаптурную группу (?:... ) с именованной группой, как (?<letter>... ) и обработать его содержание как результат.

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

Источник

Регулярные выражения не оптимальны для этой задачи, даже если вы используете альтернативные реализации 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)))
Источник

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

Источник
Другие вопросы по тегам