Реализация Regex, которая может обработать сгенерированный машиной regex's: *не отслеживающий в обратном порядке*, O (n)?

Редактирование 2: Для практической демонстрации того, почему это остается важным, посмотрите не далее, чем собственное regex-вызванное отключение электричества stackoverflow сегодня (2016-07-20)!

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

Где я могу найти надежно быструю реализацию Regex?

Делает любой знает о нормальном неотслеживании в обратном порядке (System.Text.RegularExpressions отслеживание в обратном порядке) линейное время regex реализация или для.NET или собственный и довольно применимый от.NET? Чтобы быть полезным, это должно было бы:

  • имейте худшую временную сложность случая regex оценки O (m*n), где m является длиной regex и n длина входа.
  • имейте нормальную временную сложность O (n), так как почти никакие регулярные выражения на самом деле не инициировали экспоненциальное пространство состояний, или, если они могут, только сделать так на мелком подмножестве входа.
  • имейте разумную скорость конструкции (т.е. никакой потенциально экспоненциальный DFA's)
  • будьте предназначены для использования людьми, не математиками - например, Я не хочу повторно реализовывать unicode классы символов:.NET или классы символов стиля PCRE плюс.

Бонусные очки:

  • бонусные очки для практичности, если это реализует стековые опции, которые позволяют ему обработать вложение за счет потребления O (n+m) память, а не O (m) память.
  • бонусные очки или для подвыражений получения или для замен (если существует экспоненциальное количество возможных соответствий подвыражения, то перечисление всех их по сути экспоненциально - но перечисление нескольких первых не должно быть, и так же для замен). Вы можете обходное решение, пропускающее любую функцию при помощи другого, так наличие любого достаточно.
  • бонусные очки lotsa для обработки regexes как первый класс оценивают (таким образом, можно взять объединение, пересечение, конкатенацию, отрицание - в особенности отрицание и пересечение, поскольку это очень трудно сделать обработкой строк regex определения),
  • ленивое соответствие т.е. соответствие на неограниченных потоках, не помещая все это в память плюс. Если потоки не поддерживают поиск, получая подвыражения, и/или замены не (в целом) возможны в единственной передаче.
  • Обратные ссылки отсутствуют, они существенно ненадежны; т.е. может всегда показывать экспоненциальное поведение, данное патологические входные случаи.

Такие алгоритмы существуют (Это - основная теория автоматов...) - но есть ли какие-либо практически применимые реализации, доступные от.NET?

Фон: (можно пропустить это),

Мне нравится использовать Regex для быстрых и грязных текстовых очисток, но я неоднократно сталкивался с проблемами, где общее отслеживание в обратном порядке NFA implemtation используемый perl/java/python/.NET показывает экспоненциальное поведение. Эти случаи, к сожалению, довольно легко инициировать, как только Вы начинаете автоматически генерировать свои регулярные выражения. Даже неэкспоненциальная производительность может стать чрезвычайно плохой, когда Вы чередуетесь между regexes, которые соответствуют тому же префиксу - например, в действительно основном примере, если Вы берете словарь и превращаете его в регулярное выражение, ожидаете ужасную производительность.

Для быстрого обзора того, почему лучшие реализации существуют и имеют с 60-х, посмотрите, что Регулярное выражение Соответствовать Может Быть Простым И Быстрым.

Не совсем практические опции:

  • Почти идеал: инструментарий FSA. Может скомпилировать regexes в быстрые реализации C DFA'S+NFA, позволяет преобразователи (!) также, имеет первый класс regexes (инкапсуляция yay!) включая синтаксис для пересечения и параметризации. Но это находится в прологе... (почему что-то находится с этот вид практический функции не доступно на основном языке???)
  • Быстрый, но непрактичный: полный синтаксический анализатор, такой как превосходный ANTLR обычно поддерживает надежно быстрый regexes. Однако синтаксис antlr является намного более подробным, и конечно разрешает конструкции, которые не могут генерировать действительные синтаксические анализаторы, таким образом, необходимо было бы найти некоторое безопасное подмножество.

Хорошие реализации:

  • RE2 - библиотека открытого исходного кода Google, стремящаяся к разумной совместимости PCRE минус обратные ссылки. Я думаю, что это - преемник порта Unix regex lib plan9, учитывая автора.
  • TRE - также главным образом совместимый с PCRE и даже делает обратные ссылки, хотя с помощью тех, которые Вы теряете гарантии скорости. И это имеет мегаизящный приблизительный режим соответствия!

К сожалению, обе реализации являются C++ и потребовали бы, чтобы interop использовал от.NET.

16
задан 15 revs 20 July 2016 в 20:22
поделиться

4 ответа

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

Единственное, что я прокомментирую, прежде чем продолжить, это то, что я бы посоветовал вам усомниться в выборе использования RegEx. Очевидно, вы лучше знакомы со своей конкретной проблемой и тем, что пытаетесь решить, поэтому только вы можете ответить на вопрос. Я не думаю, что ANTLR будет хорошей альтернативой; тем не менее, механизм правил домашнего приготовления (если он ограничен по объему) может быть настроен под ваши конкретные нужды. Все зависит от вашей конкретной проблемы.

Для тех, кто читает это и «упускает суть», вот некоторые справочные материалы:

На том же сайте есть несколько реализаций , ссылки на которые приведены на этой странице .

Суть всего обсуждения вышеупомянутой статьи состоит в том, что лучший ответ - использовать оба. С этой целью я знаю только одну широко используемую реализацию, используемую языком TCL. Насколько я понимаю, изначально он был написан Генри Спенсером и использует этот гибридный подход. Было несколько попыток перенести его в библиотеку ac, хотя я не знаю ни одной из широко используемых. Оба Уолтера Вальдо и Томаса Лакнера упомянуты и связаны здесь . Также упоминается библиотека повышения , хотя я не уверен в реализации. Вы также можете посмотреть сам код TCL (ссылка на их сайт ) и поработать оттуда.

Короче говоря, я бы выбрал TRE или Plan 9 , поскольку оба они активно поддерживаются.

Очевидно, что ни один из них не является C # /. Net, и я не знаю ни одного из них.

11
ответ дан 30 November 2019 в 22:50
поделиться

Consider how DFAs are created from regular expressions:

You start with a regular expression. Each operation (concat, union, Kleene closure) represents a transition between states in an NFA. The resulting DFA's states represent power sets of the states in the NFA. The states in the NFA are linear to the size of the regular expression, and therefore the DFA's states are exponential to the size of the regular expression.

So your first constraint,

have a worst case time-complexity of regex evaluation of O(m*n) where m is the length of the regex, and n the length of the input

Is impossible. The regex needs to be compiled to a 2^m-state DFA (worst case), which won't be done in linear time.

This is always the case with all but the simplest regular expressions. Ones that are so simple you can just write a quick .contains expression more easily.

0
ответ дан 30 November 2019 в 22:50
поделиться

Если вы можете справиться с использованием небезопасного кода (и проблемы с лицензированием), вы можете взять реализацию из этого порта Windows TRE .

Возможно, вы сможете использовать это непосредственно с помощью P / Invoke и явных структур макета для следующего:

typedef int regoff_t;
typedef struct {
  size_t re_nsub;  /* Number of parenthesized subexpressions. */
  void *value;     /* For internal use only. */
} regex_t;

typedef struct {
  regoff_t rm_so;
  regoff_t rm_eo;
} regmatch_t;


typedef enum {
  REG_OK = 0,       /* No error. */
  /* POSIX regcomp() return error codes.  (In the order listed in the
     standard.)  */
  REG_NOMATCH,      /* No match. */
  REG_BADPAT,       /* Invalid regexp. */
  REG_ECOLLATE,     /* Unknown collating element. */
  REG_ECTYPE,       /* Unknown character class name. */
  REG_EESCAPE,      /* Trailing backslash. */
  REG_ESUBREG,      /* Invalid back reference. */
  REG_EBRACK,       /* "[]" imbalance */
  REG_EPAREN,       /* "\(\)" or "()" imbalance */
  REG_EBRACE,       /* "\{\}" or "{}" imbalance */
  REG_BADBR,        /* Invalid content of {} */
  REG_ERANGE,       /* Invalid use of range operator */
  REG_ESPACE,       /* Out of memory.  */
  REG_BADRPT            /* Invalid use of repetition operators. */
} reg_errcode_t;

Затем используйте экспорт, способный обрабатывать строки со встроенными нулями (с поддержкой широкого диапазона символов)

/* Versions with a maximum length argument and therefore the capability to
   handle null characters in the middle of the strings (not in POSIX.2). */
int regwncomp(regex_t *preg, const wchar_t *regex, size_t len, int cflags);

int regwnexec(const regex_t *preg, const wchar_t *string, size_t len,
      size_t nmatch, regmatch_t pmatch[], int eflags);

В качестве альтернативы оберните его через решение C ++ / CLI для упрощения перевода и т. д. гибкость (я бы определенно предположил, что это разумно, если вам комфортно с C ++ / CLI).

3
ответ дан 30 November 2019 в 22:50
поделиться

Где я могу найти надежно быструю реализацию Regex?

Вы не можете.

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

Кстати, я уверен, что вы уже пробовали это, но скомпилировали ли вы регулярное выражение (с опцией, которая выводит в сборку) - я говорю, потому что:

если у вас сложное регулярное выражение и миллионы коротких строк для тестирования

1
ответ дан 30 November 2019 в 22:50
поделиться
Другие вопросы по тегам:

Похожие вопросы: