Высокое использование ЦП на соответствие шаблону Regex

Question

Я использую сопоставление шаблонов для строки в Java. У меня проблема, процессор идет высоко и ничего не делает при попытке сопоставить шаблоны. У меня есть строка 100, которую нужно проверить, если она соответствует двум шаблонам.

Ниже приведен пример кода, который я использую. Он останавливается, и процессор переходит на 100% для первой строки (patternList), когда сопоставляет ее для шаблона 2 i.e patternMatch [1]. Как я могу сделать это лучше?

String[] patternMatch = {"([\\w\\s]+)+([+\\-/*])+([\\w\\s]+)", 
    "([\\w\\s]+)+([+\\-/*])+([\\w\\s]+)+([+\\-/*])+([\\w\\s]+)"}; 
    List<String> patternList = new ArrayList<String>(); 

    patternList.add("Avg Volume Units product A + Volume Units product A"); 
    patternList.add("Avg Volume Units/Volume Units product A"); 
    patternList.add("Avg retailer On Hand/Volume Units Plan/Store Count"); 
    patternList.add("Avg Hand Volume Units Plan Store Count"); 
    patternList.add("1 - Avg merchant Volume Units"); 
    patternList.add("Total retailer shipment Count"); 

    for (String s :patternList){ 

     for(int i=0;i<patternMatch.length;i++){ 
      Pattern pattern = Pattern.compile(patternMatch[i]); 

      Matcher matcher = pattern.matcher(s); 
      System.out.println(s); 
      if (matcher.matches()) { 

       System.out.println("Passed"); 
      }else 
       System.out.println("Failed;"); 
     } 

    } 

Answer 1

Похоже, вы столкнулись с изменением catastrophic backtracking, вероятно, вызванного ([\\w\\s]+)+. Попробуйте использовать вместо ([\\w\\s]+)

String[] patternMatch = { 
     "([\\w\\s]+)([+\\-/*])+([\\w\\s]+)", 
     "([\\w\\s]+)([+\\-/*])+([\\w\\s]+)([+\\-/*])+([\\w\\s]+)" 
}; 

Answer 2

@Pshemo, вероятно, правы относительно катастрофического возвратов. Тем не менее, я бы предложил совершенно другой подход, используя String.split() и ноль с просмотром, чтобы соответствовать непосредственно до и после оператора (+-*/).

String[] x = s.split("((?<=[\\-\\+\\*/])|(?=[\\-\\+\\*/]))"); 
if (x.length == 3 || x.length== 5) 
    System.out.println("Passed"); 
else 
    System.out.println("Failed"); 

split возвращает массив, содержащий операторы в нечетных смещениях (1,3), и строке между операторами на четных смещениях (0, 2 и 4). Это должно быть много быстрее, чем регулярное выражение с обратным отсчетом.

Answer 3

Я не думаю, что существует необходимость количественно определить количественную унитарную группу.
Как это, например (?:(?:X)+)* просто равен

Определенной количественная унитарная группа приводит к экспоненциальным возвратам таким образом.
Чтобы использовать модель, это было бы лучше (?:(?:X))*, которая сама не будет
вызывает катастрофическое откат.

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

В вашем примере классы являются примерами унитарной (базовой) конструкции.

Кроме того, используйте кластер (?:,,) вместо захвата (,,), если сможете.
Конструкция, подобная этому ([+\-/*])+, будет соответствовать 1 ко многим любым из этих символов
в этом классе, но будет захватывать только символ.
Итак, группа захвата не имеет реального использования ни в группировке, ни в захвате.

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

# "([\\w\\s]+)([+\\-/*]+)([\\w\\s]+)" 

([\w\s]+)     # (1) 
([+\-/*]+)     # (2) 
([\w\s]+)     # (3) 

и

# "([\\w\\s]+)([+\\-/*]+)([\\w\\s]+)([+\\-/*]+)([\\w\\s]+)" 

([\w\s]+)     # (1) 
([+\-/*]+)     # (2) 
([\w\s]+)     # (3) 
([+\-/*]+)     # (4) 
([\w\s]+)     # (5)