Оптимизация регулярных выражений метода

Question

мне интересно, о методах оптимизации для регулярных выражений

Так что я пытаюсь разобрать каждый случай денег из 400k линии корпуса. Мне также необходимо было включить такие строки, как "$10,999.04", а также "one billion and six hundred twenty five thousand dollars" и все, что между ними. Это требовало очень длинного регулярного выражения с несколькими экземплярами групп, как

MONEYEXPRESSION = '(?:\d\d?\d?(?:,?\d{3})*(?:\.\d+)?)' 
(one|two|...|ninety[\s-]?nine|hundred|a hundred|MONEYEXPRESSION)((\s*and\s*|\s*-\s*|\s*)(one|two|...|ninety[\s-]?nine|hundred|a hundred|MONEYEXPRESSION))* 

Даже более того, для того, чтобы потребовать его быть экземпляром денег и избежать соответствующих линий, такие как "five hundred people were at the event" У меня есть 4 варианта OR-нут которые требуют, чтобы "$", "dollars?", or "cents?" находился в определенных местах в предложении хотя бы один раз.

регулярное выражение почти 20 тыс. Символов! :(

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

Answer 1

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

1. Из ссылки обратного прослеживания выше: «Когда вложенности операторов повторения, чтобы быть абсолютно уверены, что есть только один способ, чтобы соответствовать один и тот же матч.»

2. Избегайте больших дополнительных компонентов. Вместо чего-то вроде (<number>? <number>)? <number>, чтобы соответствовать последовательности с элементами, разделенными пробелами, напишите (<number> ?)+.

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

4. Убедитесь, что неограниченные части в ваших регулярных выражениях ограничены по длине, особенно если более поздняя часть не может быть надежно распознана. Такие вещи, как A.*B?, задают проблемы - это может соответствовать что-нибудь, которое начинается с A.

5. Не используйте lookahead/lookbehind. Почти всегда есть более простой способ.

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

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

((one|two|three|...|twenty|thirty|...|ninety|hundred|thousand|and) ?)+ (dollars?|euros?)\b 

Поскольку это помечено «питон», вот еще два предложения:

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

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

Answer 2

Я бы попытался сделать что-то в этом роде:

keywords = ["$","dollar","dollars","cent","cents"] 
my_file = r"c:\file.txt" 
output = r"c:\output.txt" 
filtered_lines = [] 
with open(my_file,"r") as f: 
    for line in f: 
     for k in keywords: 
      if k in line: 
       filtered_lines.append(line) 
       break 
with open(output,"w") as o: 
    o.write("\n".join(filtered_lines)) 

Answer 3

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

Наиболее проблематичная вещь с письменным отказом части является то, что если у вас есть one hundred people будет попробовать все миллиарды и тысячи и все уже на слове one просто чтобы узнать, в конце концов, что нет dollars. Но, что еще хуже, он попробует снова все для слова hundred, а затем за people ...
В идеале это было бы поэтому начинаться со спины, чтобы он не пытался сопоставлять все с каждым словом, а только «доллары», центов "или вообще, и только тогда сделать дорогостоящую часть.

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

Ах, и некоторые границы слов могут также помочь уменьшить соответствие с на каждый персонаже к при каждом начале слова ... Я не упоминал об этом выше, но на самом деле для этого примера двигателя запускается для соответствия в 'o', затем снова в 'n', 'e', ​​'' и так далее.