Случайная строка, соответствующая регулярному выражению

StackOverflow https://stackoverflow.com/questions/205411

  •  03-07-2019
  •  | 
  •  

Вопрос

Как бы вы поступили, создав случайную буквенно-цифровую строку, соответствующую определенному регулярному выражению?

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

Это было полезно?

Решение 9

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

Другие советы

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

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

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

Однако нет никакой конкретной гарантии относительно того, когда и достигнете ли вы начального состояния.Нужно было бы выяснить, в каком смысле сгенерированные строки являются "случайными", и в каком смысле вы вообще надеетесь на случайный элемент из языка.

Хотя, возможно, это отправная точка для размышлений о проблеме!

Теперь, когда я это записал, мне кажется, что было бы проще многократно разрешать варианты для упрощения шаблона регулярных выражений, пока у вас не останется простая строка.Найдите первый не алфавитный символ в шаблоне.Если это *, повторите предыдущий элемент некоторое количество раз и удалите * .Если это |, выберите, какой из элементов OR'd сохранить, а остальные удалите.Для левой пары сделайте то же самое, но смотрите на символ, следующий за соответствующей правой парой.Вероятно, это будет проще, если вы сначала преобразуете регулярное выражение в древовидное представление, что упростит работу со структурой парной группировки.

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

Строка:: Случайная в Perl будет сгенерирована случайная строка из подмножества регулярных выражений:

#!/usr/bin/perl

use strict;
use warnings;

use String::Random qw/random_regex/;

print random_regex('[A-Za-z]{3}[0-9][A-Z]{2}[!@#$%^&*]'), "\n";

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

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

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

Я написал Петрушка, которые состоят из лексера и генератора.

  • Lexer предназначен для преобразования строки, подобной регулярному выражению, в последовательность токенов.
  • Генератор использует эти токены для создания определенного количества кодов.
$generator = new \Gajus\Parsley\Generator();

/**
 * Generate a set of random codes based on Parsley pattern.
 * Codes are guaranteed to be unique within the set.
 *
 * @param string $pattern Parsley pattern.
 * @param int $amount Number of codes to generate.
 * @param int $safeguard Number of additional codes generated in case there are duplicates that need to be replaced.
 * @return array
 */
$codes = $generator->generateFromPattern('FOO[A-Z]{10}[0-9]{2}', 100);

Приведенный выше пример сгенерирует массив, содержащий 100 кодов, каждый с префиксом "FOO", за которым следуют 10 символов из "ABCDEFGHKMNOPRSTUVWXYZ23456789" haystack и 2 числа из "0123456789" haystack.

Эта библиотека PHP выглядит многообещающе: Обратный алгоритм

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

([A-PR-UWYZ]([0-9]([0-9]|[A-HJKSTUW])?|[A-HK-Y][0-9]([0-9]|[ABEHMNPRVWXY])?) ?[0-9][ABD-HJLNP-UW-Z]{2}|GIR0AA)

Результаты

D43WF
B6 6SB
MP445FR
P9 7EX
N9 2DH
GQ28 4UL
NH1 2SL
KY2 9LS
TE4Y 0AP

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

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

Предполагая, что у вас есть как минимальная длина, так и требование 3 из 4 * (или аналогичное), я бы просто был склонен использовать приличный генератор паролей.

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

  • 3-из-4:должен обладать по крайней мере тремя из следующих характеристик:нижний регистр, верхний регистр, число, символ

Это возможно (например, модуль регулярных выражений Haskell имеет набор тестов, который автоматически генерирует строки, которые должны соответствовать определенным регулярным выражениям).

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

Почему бы не обработать регулярное выражение в обратном направлении?Простой пример:если ваше регулярное выражение равно

/[a-zA-Z]{6}/

тогда вы знаете, что вам нужно 6 букв a-z или A-Z, поэтому сгенерируйте их.Конечно, это может усложниться, и, в зависимости от ваших потребностей, вам может в конечном итоге потребоваться обратное написание всего анализатора регулярных выражений, но вы можете прекратить добавлять функции, когда удовлетворите свои потребности.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top