Regex: производительность ретроспективного просмотра при сохранении данных?

В моем проекте на C # я разбираю текст на предмет дат. Даты могут быть в различных форматах, цель - найти и исправить ряд ошибок формата даты. Различные форматы даты означают, что набор определенных форматов даты невозможен. Первоначально у меня был набор из примерно 10 регулярных выражений, применяемых одно за другим к входной строке. Функционально это было нормально, но когда строка приблизилась к 200 КБ текста, производительность стала проблемой, поскольку функция заняла около 150 мс.

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

\b(January|February|March|April|May|June|July|August|September|October|November|December)\b

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

.{0,25}\b(January|February|March|April|May|June|July|August|September|October|November|December)\b.{0,25}

функционально нормально. Однако производительность этого регулярного выражения составляет около 3500 мс для поиска совпадений в одной и той же длинной входной строке.

Теперь похожее регулярное выражение

(?<=.{0,25})\b(January|February|March|April|May|June|July|August|September|October|November|December)\b.{0,25}

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

Итак, мой вопрос: могу ли я иметь регулярное выражение, которое имеет производительность использования ретроспективного просмотра, но имеет функциональность предоставления всего текста в результате совпадения?


c# regex regex-lookarounds
person user1906580    schedule 15.12.2012    source источник
comment
y не согласовывать форматы даты в первую очередь ... и если вы можете согласовать форматы даты, просто сделайте это вместо того, чтобы писать regex, который всегда не работает в некоторых случаях .. есть n! + возможности, где n - количество способов, которыми может быть дата ..   -  person Anirudha    schedule 15.12.2012
comment
Вы можете просто захватить ретроспективный просмотр и связать его с совпадением: (?<=(.{0,25})). Вы найдете содержимое ретроспективного обзора в Groups[1]. Это то, что вы хотите?   -  person Martin Ender    schedule 15.12.2012

Ответы (1)


arrow_upward
2
arrow_downward

Прирост производительности - это иллюзия. Обычно что-то вроде .{0,25} вызывает много откатов, что объясняет наблюдаемую вами низкую производительность. Однако при размещении в ретроспективе он перестает вести себя жадно и не выполняет обратный поиск, а ретроспективный поиск будет искать наименьшее возможное совпадение, что означает, что будут пробоваться символы 0 без возврата. Это означает, что поиск назад совершенно бесполезен, поскольку он всегда будет соответствовать нулевым символам перед названием месяца.

Что, если вы извлечете контекст после того, как найдете совпадение в названии месяца, используя позицию совпадения? Для каждого _2 _ в regex.Matches(str), получите match.Index и match.Length и подстрока до и после эти позиции.

person Sergiu Dumitriu    schedule 05.01.2013
comment
Да, именно этим я сейчас и занимаюсь. Общая функциональность правильная, производительность неплохая, но решение кажется мне неопрятным, также нужно проверять начало / конец статьи при подстроке. Я надеюсь найти решение с хорошей производительностью, но при этом смогу использовать MatchEvaluator - подход, который я успешно использовал в других частях приложения и, похоже, приводит к аккуратному коду. Хотя, возможно, это невозможно в рамках обозначенных мною ограничений. - person user1906580; 19.01.2013