Поиск дат в строке

Question

Я ищу быстрый путь в C #, чтобы найти все даты в строке (строка представляет собой большой текст, я должен отсканировать около 200 000 различных строк).

, так как их многоспособы записи даты (например, 31/12/2012 или 31 декабря 2012 года и многое другое), я использую это регулярное выражение (которое должно охватывать почти все частые способы написания дат):

string findDates = "(?: (\ d {1,4}) - /.- /.)|(?:(\s\dndom1,2 innovative)\s+(jan(?:uary) enj0,1} \ {0,1} | февраль (? ruary) {0,1} \ {0,1} | Март (? ч) {0,1} \ {0,1} | апрель (.: илы) {0,1} \ {0,1} | может \ {0,1} | Июнь (:. д.) {0,1} \ {0,1} | июль (?.? у) {0,1} \ {0,1} | август (:. усть) {0,1} \ {0,1} | Сентябрь (?.?. сентябрьском) {0,1} \ {0,1} | октябрь (?: обер) {0,1} \ {0,1} | ноября (?: уголек) {0,1} \ {0,1} | декабрь (?: уголек) {0,1} \ {0,1}) \ s + (\ д {2,4})) | (:( январь (:. uary) {0,1} \ {0,1} | февраль (?:?.? ruary) {0,1} \ {0,1} | Мары (:. ч) {0,1} \ {0,1} | апреля (?.?. иль) {0,1} \ {0,1} | может \ {0,1} | июн.: {0,1} \ {0,1} | Юль (е?).. (? у) {0,1} \ {0,1} | августу(: усть?) {0,1} \ {0,1} | сентябрь (? тябрь) {0,1} \ {0,1} | октябрь (?: обер) {0,1} \.{0,1} | ноября (?: уголек) {0,1} \ {0,1} | декабрь (? уголек). {0,1} \ {0,1}) \ s + ([0-9] {1,2}) [\ с,] + (\ д {2,4})) ";

с" RegexOptions.Compiled |RegexOptions.IgnoreCase |RegexOptions.IgnorePatternWhitespace ". Кроме того, я попытался предварительно скомпилировать регулярное выражение, чтобы сделать его еще более быстрым.

Проблема в том, что он очень медленный (на некоторых текстовых файлах больше 2 секунд) Есть ли что-нибудь лучше?и эффективный способ сделать это?

Спасибо

Answer 1

Выражение выглядит в целом хорошо, как уже упоминали другие, оно может быть немного многословным со всеми {0,1} вместо ? и (?: вместо применения RegexOptions.ExplicitCapture. Но это не должно замедлять выражение. Они только улучшают читаемость.

Что может вызывать медлительность, так это то, что в выражении есть много опций обратного отслеживания, сделанных как расширенный месяц, так и. необязательный. Интересно, что произойдет, если вы измените выражение, чтобы применить только необязательные. один раз, после названия месяца, и что произойдет, если вы сделаете название месяца жадной группой ((?>pattern) невыраженное (или «жадное») подвыражение.)

Так что:

 (jan(?:uary){0,1}\.{0,1}|feb(?:ruary){0,1}\.{0,1}|mar(?:ch){0,1}\.{0,1}|apr(?:il){0,1}\.{0,1}|may\.{0,1}|jun(?:e){0,1}\.{0,1}|jul(?:y){0,1}\.{0,1}|aug(?:ust){0,1}\.{0,1}|sep(?:tember){0,1}\.{0,1}|oct(?:ober){0,1}\.{0,1}|nov(?:ember){0,1}\.{0,1}|dec(?:ember){0,1}\.{0,1})\s+(\d{2,4}))

станет:

 (?>jan(uary)?|feb(ruary)?|mar(ch)?|apr(il)?|may|june?|july?|aug(ust)?|sep(tember)?|oct(ober)?|nov(ember)?|dec(ember)?)\.?\s+(\d{2,4}))

Мало того, что это намного короче, я ожидаю, что это будет быстрее.

А потом в начале есть часть выражения, которая на самом деле не имеет смысла для меня. (?:(\d{1,4})- /.- /.) Либо что-то потеряно при форматировании, либо это никуда не поможет.

\ d {1,4} будет иметь смысл для года или любой другой части даты, но - /.- /. после этого вообще не имеет смысла. Я думаю, что вы имели в виду что-то вроде:

 \d{1,4}[- /.]\d{1,2}[- /.]\d{1,2}

Или что-то в этом районе. В существующем состоянии он собирает мусор, вероятно, не ускоряя процесс сопоставления.

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

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

Так что разбиение поиска на несколько очень точных выражений может привести к гораздо более высокой производительности, это может быть началом:

 \b\d{1,2}[- .\\/]\d{1,2}[- .\\/](\d{2}|\d{4})\b
 \b((jan|feb|mar|apr|jun|jul|aug|sep|oct|nov|dec)(.|[a-z]{0,10})|\d{1,2})[- .\\/,]\d{1,2}[- .\\/,](\d{2}|\d{4})\b

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

Разбиение шаблона также улучшает читабельность:).

Последний совет: ограничьте количество возможных символов, которые нужно откатить назад, ограничив такие вещи, как \ s +, вы редко хотите, чтобы совпадало 20 000 пробелов, но если они есть в вашем исходном документе, он попытается сопоставить их. \ s {1,20} обычно достаточно и ограничивает способность двигателей пытаться найти совпадение там, где его нет.

Answer 2

Сложно придумать алгоритм без его тестирования.Мы могли бы рекомендовать что-то, что получается медленнее.Так что на самом деле он пробует разные варианты.

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

---

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

Первый - это скрининг для поиска наиболее подходящих совпадений, а другой - для дальнейшей проверки только той части файла, в которой находится совпадение.Например, '\ d {1,2} \ s *, \ s * \ d {4}', вероятно, будет частью даты, но искать ее лучше, чем искать все условия, касающиеся января (uary) / февраля(ruary) / март (ch) /....

---

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

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