Как оптимизировать производительность регулярных выражений?

Question

У меня очень длинное регулярное выражение. Мое регулярное выражение - это сочетание около 5000 или более фраз.

Кроме того, текст, над которым я выполняю регулярное выражение, также огромен. Размер текста составляет около 5 КБ.

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

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

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

(ACS | ADDR.com Технологии | ADP частное ограниченное | ADP | ADP Индия частное ограниченное | Программные услуги AIT PTE ограниченное | AMK Technologies частное ограниченное | ANMSoft Technologies частное ограниченное | ANZ частное информационное технологии ограниченное | ASD Global India private Limited | ASD India частная компания с ограниченной ответственностью | ASM Technologies частная компания с ограниченной ответственностью | AXA Group Solutions Индия частная компания с ограниченной ответственностью | AXA технология Индия с ограниченной ответственностью | Aarkay Infonet частная компания с ограниченной ответственностью | Research and Analytics частная компания с ограниченной ответственностью | Accenture Индия частная компания с ограниченной ответственностью | Accenture Services Индия | Accenture Services P Limited | Accenture Services частное общество с ограниченной ответственностью | Accenture | Accenture Software частное общество с ограниченной ответственностью | Accurum India частное общество с ограниченной ответственностью | AceTechnologies Inc | Aclat Inc | AcmeCeeYess Softech частное общество с ограниченной ответственностью | Adaequare Индия частное общество с ограниченной ответственностью | Adea International частное общество с ограниченной ответственностью | Adea международное частное общество с ограниченной ответственностью | Adea Technologies | Adeptra | Aditi Technologies | Adobe Системы | Adroit Business Solutions | Adroit и Claretdene Infotech private limited | Affron Infotech | Agile Software En частное общество с ограниченной ответственностью | Международное частное общество с ограниченной ответственностью Agilent Technologies International | частное общество с ограниченной ответственностью Akebono Soft Technologies | частное общество с ограниченной ответственностью AkebonoSoft Technologies | частное общество с ограниченной ответственностью «Algorhythm Technologies» | частное общество с ограниченной ответственностью «Allsec Technologies» | частное общество с ограниченной ответственностью «Alphonso Informex» | Клиентские услуги Altria | частное общество с ограниченной ответственностью «Altruist India» | Amdocs | Центр развития Amdocs в Индии, частная компания с ограниченной ответственностью | Центр развития Amdocs, Индия | Американские кибер-системы | American Express Service, Индия, частная компания с ограниченной ответственностью | Американская фондовая биржа | Amrok Securities | Аниш Информационные технологии, частная компания с ограниченной ответственностью | Ankhnet Informations, частная компания с ограниченной ответственностью | Apex Technologies, частная компания с ограниченной | AppLabs | AppLabs Technologies private ограниченное | Appshark India | Apptix Software private ограниченное | Aquila Technologies | Arcot R and D Software частное ограниченное | Arsin Systems частное ограниченное | Ascendum Solutions частное ограниченное | AskMe Software частное ограниченное | Atos Origin частное ограниченное | Atos Origin | Atos Origin Индия частное ограниченное | Aurigo Software Technolo gies private limited | Aurona Technologies частная с ограниченной ответственностью | Autopower Software Solutions | Aztecsoft | BMC Software Индия с ограниченной ответственностью | Balasai Net с ограниченной ответственностью | Bayon Solutions с ограниченной ответственностью | Beachwood Computing Limited | Birlasoft с ограниченной | Blue Bird Technologies частная с ограниченной | Blue Fountain Media частная с ограниченной | Blue Star InfoTech | Boden Inc | Бостон | Braahamam Net Solutions частный с ограниченной ответственностью | Braahmam Net Solutions частный с ограниченной ответственностью | Технология Brain Soft частный с ограниченной ответственностью | Brigade Corporation частный с ограниченной ответственностью | Business Link Automation India с ограниченной ответственностью | BusinessLink Automation частный с ограниченной | C Впереди информационные технологии Индия с ограниченной ограниченное | Корпорация CDI | CCG India частное с ограниченной ответственностью | CEM Solutions | CGI Информационные системы и консультанты по управлению частное с ограниченной ответственностью | CGI Информационные системы частное с ограниченной ответственностью | CGI Информационные системы и консультанты по управлению частное с ограниченной | CGI Информация и управление частное с ограниченной | CGI Netvorks | CISCO Systems India частный ограниченный | CMC Limited | COMSYS Inc | CORE SHELL TEC HNOLOGIES | CRC Software India частная компания с ограниченной ответственностью | CRV Executive Search частная компания с ограниченной ответственностью | CS Software Solutions частная компания с ограниченной ответственностью | CSC India частная компания с ограниченной ответственностью | CSS Corp частная компания с ограниченной ответственностью | Cambridge Solutions Limited | Cambridge Solutions | Cambridge Solutions Sdn. Bhd | Candor Ind. Частный ограниченный | Candor India частный ограниченный | Canvas Creatives частный ограниченный | Canvera | Capgemini Business Service India Limited | Capgemini частный)

Я использую C # для этого материала.

Пожалуйста, просветите !!!!

Answer 1

Вы можете значительно улучшить производительность этого регулярного выражения, добавив \b в начале:

\b(ACS| ... |Z)

Это предотвратит проверку каждого символа и проверку каждого слова вместо этого.

Answer 2

Одной из оптимизаций было бы извлечение общих префиксов. Изменить вхождения как

(This is some text|This is some other text)

до

This is some (text|other text)

Это также должно быть сделано на каждом уровне. Изменить вхождения как

ABCD|ADCB|BACD|BADC|BCAD|BCDA|BDAC|BDCA|CABD

до

A(BCD|DCB)|B(A(CD|DC)|C(AD|DA)|D(AC|CA))|CABD

Эта оптимизация такова, что движку Regex не придется проверять одни и те же символы несколько раз.

Это может быть достигнуто путем сортировки фаз и рассмотрения последовательных элементов. Будьте осторожны, чтобы не разделить мета-символы. Вы не хотите разбивать в середине .* или \..

Другим способом было бы использование Trie-структуры для поиска префиксов. Это более надежно, но немного сложнее.

Answer 3

Вы можете оптимизировать регулярное выражение, используя атомарную группировку или притяжательные квантификаторы , где это возможно.

Кроме того, если в вашем регулярном выражении есть такие вещи, как .* или .+, которые могут быть реальными запоминающими / исполняющими свиньями, замените их на (притяжательные) классы символов (снова, если возможно) .

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

Удачи!

Answer 4

Я знаю, что он старый, но все же ...

Правила «ИЛИ» (в этом случае все стандартные правила: concat, repeat и or) не требуют ручной оптимизации. При компиляции большинство движков регулярных выражений оптимизируют его. Иногда все наоборот - слишком большое количество групп может повлиять на производительность, так как движок должен сохранять совпадение каждой группы.

Что действительно сильно влияет на производительность, так это смотреть в будущее и смотреть за правилами, которые не используются в вашем запросе.

В этом случае автор может добавить правило '\ b' в начале и конце запроса, чтобы потребовать поиск по всему слову, что значительно ограничит количество мест, в которых механизм начнет совпадать.

Answer 5

Пример с Python (также есть C-инструмент для оптимизации регулярных выражений на https://github.com/ksx123/regex-optimization):

import hachoir_regex
optimized = hachoir_regex.parse("(ACS|ADDR.com Technologies|ADP private limited|ADP|ADP India private limited|AIT Software Services PTE limited|AMK Technologies private limited|ANMSoft Technologies private limited|ANZ Information Technology private limited|ASD Global India private Limited|ASD India private Limited|ASM Technologies private limited|AXA Group Solutions India private limited|AXA technology India limited|Aarkay Infonet private limited|AbsolutData Research and Analytics private limited|Accenture India private limited|Accenture Services India|Accenture Services P Limited|Accenture Services private Limited|Accenture|Accenture Software Private Limited|Accurum India private limited|AceTechnologies Inc|Aclat Inc|AcmeCeeYess Softech Private Limited|Adaequare India private limited|Adaequare Info private limited|Adea International private limited|Adea Technologies|Adeptra|Aditi Technologies|Adobe Systems|Adroit Business Solutions|Adroit and Claretdene Infotech private limited|Affron Infotech|Agile Software Enterprise private limited|Agilent Technologies International private limited|Akebono Soft Technologies private limited|AkebonoSoft Technologies private limited|Akmin Technologies|Algorhythm Technologies private limited|Allsec Technologies private limited|Alphonso Informex private limited|Altria Client Services|Altruist India private limited|Amdocs|Amdocs Development Center India private limited|Amdocs Development Centre India|American CyberSystems|American Express Service India private limited|American Stock Exchange|Amrok Securities|Anish Information Technology private limited|Ankhnet Informations private limited|Apex Technologies private limited|AppLabs|AppLabs Technologies private limited|Appshark India|Apptix Software private limited|Aquila Technologies|Arcot R and D Software private limited|Arsin Systems private limited|Ascendum Solutions private limited|AskMe Software private limited|Atos Origin private limited|Atos Origin|Atos Origin India private limited|Aurigo Software Technologies private limited|Aurona Technologies private limited|Autopower Software Solutions|Aztecsoft|BMC Software India private limited|Balasai Net private limited|Bayon Solutions private limited|Beachwood Computing Limited|Birlasoft limited|Blue Bird Technologies private limited|Blue Fountain Media private limited|Blue Star InfoTech|Boden Inc|Boston|Braahamam Net Solutions private limited|Braahmam Net Solutions private limited|Brain Soft technology private limited|Brigade Corporation Private Limited|Business Link Automation India private limited|BusinessLink Automation private limited|C Ahead Info Technologies India private limited|C.D.I Corporation|CCG India private limited|CEM Solutions|CGI Information Systems and Management Consultants private limited|CGI Information Systems private limited|CGI Information System and Management Consultants private limited|CGI Information and Management private limited|CGI Netvorks|CISCO Systems India private limited|CMC Limited|COMSYS Inc|CORE SHELL TECHNOLOGIES|CRC Software India private limited|CRV Executive Search private limited|CS Software Solutions private Limited|CSC India private Limited|CSS Corp private limited|Cambridge Solutions Limited|Cambridge Solutions|Cambridge Solutions Sdn. Bhd|Candor Ind. private limited|Candor India private limited|Canvas Creatives private limited|Canvera|Capgemini Business Service India Limited|Capgemini private)")
len(str(optimized)) # has length 3048

Пока исходная строка имеет длину 3399. Чем больше строка, тем больше возможностей для оптимизации. При этом используется библиотека hachoir-regex . Вы можете использовать это в дополнение к добавлению \b, как предлагается.