Как в RegEx найти строку, содержащую не более трех уникальных символов?

Question

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

Вся помощь приветствуется.

(Я пишу скрипт на PHP, если это поможет)

Answer 1

Возможно, это сработает:

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)*)?)?$/

Answer 2

Оптимизация Regex - веселое времяпрепровождение для детей! Принимая регулярное выражение Гнарфа в качестве отправной точки:

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

Я заметил, что здесь были вложенные и последовательные * s, которые могут вызвать большой откат назад. Например, в 'abcaaax' он будет пытаться сопоставить последнюю строку из строки & # 8217; s как один \ 1 * длины 3, a \ 1 * длины два, за которым следует один \ 1, a \ 1, за которым следует 2-длина \ 1 * или три одинарных \ 1. Эта проблема усугубляется, когда у вас более длинные строки, особенно когда из-за регулярного выражения ничто не мешает \ 1 быть тем же символом, что и \ 2.

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

Это было в два раза быстрее, чем оригинал, тестирование на Python PCRE matcher. (Это быстрее, чем настраивать его в PHP, извините.)

Это все еще проблема в том, что (.)? ничего не может сопоставить, а затем продолжить сопоставление. \ 1 | \ 2 все равно будет совпадать с \ 1, даже если не найдется совпадения с \ 2, что приведет к потенциальному возвращению назад при попытке ввести \ 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

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

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

Answer 3

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

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

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

Answer 4

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

Скорее всего, вам потребуется создать ключ структуры данных hashMap / array: символьное значение: подсчитать и перебрать большой текстовый файл, перестроив карту для каждой строки. в каждом новом символе проверяйте, равно ли количество встреченных символов 2, если это так, пропустите текущую строку.

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