Медленный разбор с регулярным выражением - PullRequest
0 голосов
/ 27 мая 2011

У меня есть следующее регулярное выражение для проверки данных:

lexer = /(?:
      (.{18}|(?:.*)(?=\s\S{2,})|(?:[^\s+]\s){1,})\s*
      (.{18}|(?:.*)(?=\s\S{2,})|(?:[^\s+]\s){1,})\s*
      (?:\s+([A-Za-z][A-Za-z0-9]{2}(?=\s))|(\s+))\s*
      (Z(?:RO[A-DHJ]|EQ[A-C]|HIB|PRO|PRP|RMA)|H(?:IB[2E]|ALB)|F(?:ER[2T]|LUP2|ST4Q))\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\s+\d{10}|\s+)\s*
      (\d{6})\s*
      (.*)(?=((?:\d{2}\/){2}\d{4}))\s*
      ((?:\d{2}\/){2}\d{4})\s*
      (\S+)
    )/x

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

  filename = File.new(@file, "r")
  filename.each_line.with_index do |line, index|
    next if index < INFO_AT + 1

    lexer = /(?:
      (.{18}|(?:.*)(?=\s\S{2,})|(?:[^\s+]\s){1,})\s*
      (.{18}|(?:.*)(?=\s\S{2,})|(?:[^\s+]\s){1,})\s*
      (?:\s+([A-Za-z][A-Za-z0-9]{2}(?=\s))|(\s+))\s*
      (Z(?:RO[A-DHJ]|EQ[A-C]|HIB|PRO|PRP|RMA)|H(?:IB[2E]|ALB)|F(?:ER[2T]|LUP2|ST4Q))\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\S+)\s*
      (\s+\d{10}|\s+)\s*
      (\d{6})\s*
      (.*)(?=((?:\d{2}\/){2}\d{4}))\s*
      ((?:\d{2}\/){2}\d{4})\s*
      (\S+)
    )/x

    m = lexer.match(line)
    begin
      if (m) then ...

Редактировать Здесь вы можете найти некоторые строки, которые мне нужно проанализировать: Файл

Edit II @Mike R

Я анализирую файл, который содержит 25 столбцов в строке, и каждый столбец может иметь свой собственный способ проверки.Это может быть либо пробел, либо полный набор символов.

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

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

Если вы увидите файл, возможно, вы пойметепочему я это делаю!Давайте приведем в качестве примера первый столбец.Я должен соответствовать «номеру детали», и у меня нет никаких правил, как это сделать, примеры:

  • 123456789
  • 1 555 989
  • 0123456789123456789

Ни простой \ S +, ни (\ S + \ s) {1,} не могут решить эту проблему, потому что я не гарантирую целостность данных.

Ты!

Есть какие-нибудь улучшения, предложения?

~ Eder Quiñones

Ответы [ 4 ]

5 голосов
/ 27 мая 2011
  1. Регулярное выражение не изменяется в цикле, поэтому потяните назначение lexer = вверх и из цикла. («Движение по инвариантному коду цикла».)

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

  3. Так что это очевидно, я уверен, но может иметь смысл написать настоящий парсер. Ruby имеет расширенный генератор синтаксического анализатора PEG под названием Treetop. Традиционные подходы - это Lex + Yacc (например, flex + bison) или просто программа на C, реализующая сканер и парсер рекурсивного спуска. Старая школа, да, но легко написанная и отчасти забавная по сравнению с еще одной программой CRUD.

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

2 голосов
/ 27 мая 2011

Вы, вероятно, получаете катастрофическое возвращение назад .

А именно, но не только, из-за ваших жадных \S+\s* последовательностей. Вероятно, они тоже недействительны, так как:

(\S+)\s*
(\S+)\s*
(\S+)\s*
(\S+)\s*

будет соответствовать 'abcd' (после болезненного отступления).

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

1 голос
/ 29 мая 2011

Ваш файл имеет формат с полями фиксированной ширины. В Ruby есть строковый метод с именем unpack, специально предназначенный для анализа файлов этого типа.

field_widths = [19,41,14,11,11,11,11,11,11,11] #etc
field_pattern = "A#{fields.join('A')}"

Тогда в вашем цикле строки:

row = line.unpack(field_pattern)

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

1 голос
/ 27 мая 2011

Что вы на самом деле ищете при разборе?

Насколько я могу судить, в строке есть только несколько значимых элементов, которые вы ищете.

  • Вы ищете буквенно-цифровой символ, начинающийся с Z.
    (Z(?:RO[A-DHJ]|EQ[A-C]|HIB|PRO|PRP|RMA)|H(?:IB[2E]|ALB)|F(?:ER[2T]|LUP2|ST4Q))\s*

  • Вы ищете 6-значный номер
    (\d{6})\s*

  • Вы ищете дату
    (?=((?:\d{2}\/){2}\d{4}))\s*<br> ((?:\d{2}\/){2}\d{4})\s*

(Обратите внимание, что последнее выражение даты является примеромкак плохо это построено. У него есть предвосхищение даты, за которой сразу же следует сопоставление без захвата с той же самой датой. Поэтому заблаговременное рассмотрение бессмысленно. См. другой ответ о катастрофическом возврате, который, несомненно, происходит здесь.)

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

Итак, полностью отбросьте выражениеи прекратите пытаться сделать все это сразу. Делайте отдельные части (разбивая строку на \ s по мере необходимости) и разбивайте это на несколько небольших регулярных выражений, которые на самом деле соответствуют тому, что вам действительно нужно проверить.

...