В RegEx, как найти строку, которая содержит не более 3 уникальных символов?

Question

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

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

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

Answer 1

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

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

Я заметил, что здесь были вложенные и последовательные * s, которые могут вызвать большой возврат. Например, в «abcaaax» он будет пытаться сопоставить последнюю строку из «a» как единое целое \ 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 2

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

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

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

Answer 3

Возможно, это будет работать:

preg_match("/^(.)\\1*(.)?(?:\\1*\\2*)*(.)?(?:\\1*\\2*\\3*)*$/", $string, $matches);
// aaaaa:Pass
// abababcaaabac:Pass
// aaadsdsdads:Pass
// aasasasassa:Pass
// aasdasdsadfasf:Fail

Explaination:

/
 ^                 #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] будет содержать три символа, которые вы хотите. Регулярное выражение ищет первый символ, затем сохраняет его и сопоставляет до тех пор, пока не будет найдено что-либо, отличное от этого символа, поймает его как второй символ, сопоставляя любой из этих символов столько раз, сколько может, перехватит третий символ и сопоставляет все три до тех пор, пока совпадение не завершится или строка не закончится и тест не пройдет.

EDIT

Это регулярное выражение будет намного быстрее из-за того, как работает механизм синтаксического анализа и возврата, прочитайте ответ Бобинса для объяснения:

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

Answer 4

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

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

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