java regex avec précédant et finissant (. *) Lent

Question

J'ai remarqué que lorsque je fais correspondre une expression régulière comme la suivante sur un texte, elle est beaucoup plus lente que celle sans parties précédentes et suivantes (.*). J'ai fait de même sur perl et j'ai trouvé que pour perl cela ne faisait pas vraiment de différence. Est-il possible d'optimiser l'expression régulière d'origine "(.*)someRegex(.*)" pour Java?

Pattern p = Pattern.compile("(.*)someRegex(.*)"); 
Matcher m = p.matcher("some text"); 
m.matches(); 

Pattern p = Pattern.compile("someRegex"); 
Matcher m = p.matcher("some text"); 
m.matches(); 

Edit: Voici un exemple concret:

(.*?)<b>\s*([^<]*)\s*<\/b>(.*) 

Answer 1

. matchs tous les personnages

au lieu de . essayer de limiter votre recherche en utilisant des classes comme \w ou \s.

Mais je ne vous garantis pas que ça fonctionnerait vite.

Tout dépend de la quantité de texte que vous faites correspondre!

Answer 2

Votre meilleur pari est de sauter essayer de faire correspondre le front et la fin de la chaîne du tout. Vous devez le faire si vous utilisez la méthode matches(), mais vous ne le faites pas si vous utilisez la méthode find(). C'est probablement ce que vous voulez à la place.

Pattern p = Pattern.compile("<b>\\s*([^<]*)\\s*<\\/b>"); 
Matcher m = p.matcher("some <b>text</b>"); 
m.find(); 

Vous pouvez utiliser start() et end() pour trouver les indices dans la chaîne source contenant le match.

Dans mon expérience, l'utilisation d'expressions régulières pour traiter le HTML est très fragile et ne fonctionne que dans les plus minces. . cas, vous pourriez avoir plus de chance à l'aide d'un analyseur XML Full Blown à la place, mais si c'est l'un de ces cas triviaux, ont à ce

réponse d'origine:. Voici ma réponse originale partagent pourquoi un .* au début d'un match sera si mal

Le problème avec l'utilisation .* à l'avant est que cela causera beaucoup de retour en arrière dans votre match. Par exemple, tenez compte des éléments suivants:

Pattern p = Pattern.compile("(.*)ab(.*)"); 
Matcher m = p.matcher("aaabaaa"); 
m.matches(); 

Le match se déroulera comme suit:

1. Le matcher tentera d'aspirer toute la chaîne, « aaabaaa », dans la première .*, mais essaie ensuite correspondre a et échoue.
2. Le matcher va sauvegarder et faire correspondre "aaabaa", puis essaie de faire correspondre a et réussit, mais essaie de faire correspondre b et échoue.
3. Le matcher sauvegarde et correspond à "aaaba", puis essaie de faire correspondre a et réussit, mais essaie de faire correspondre b et échoue.
4. Le matcher sauvegarde et correspond à "aaab", puis essaie de faire correspondre a et réussit, mais essaie de faire correspondre b et échoue.
5. Le matcher va sauvegarder et faire correspondre "aaa", puis essaie de faire correspondre a et échoue.
6. Le matcher sauvegarde et correspond à "aa", puis essaie de faire correspondre a et réussit, essaie b et réussit, puis fait correspondre "aaa" à la finale .*. Succès.

Vous souhaitez éviter une correspondance très large vers le début de vos correspondances de motif autant que possible. Sans connaître votre problème réel, il serait très difficile de suggérer quelque chose de mieux.

Mise à jour: Anirudha suggère d'utiliser (.*?)ab(.*) comme solution possible pour éviter les retours en arrière. Cela ralentira dans une certaine mesure le retour en arrière, mais au prix d'essayer d'appliquer le prochain match à chaque essai. Alors maintenant, considérez ce qui suit:

Pattern p = Pattern.compile("(.*?)ab(.*)"); 
Matcher m = p.matcher("aaabaaa"); 
m.matches(); 

Il se déroulera comme ceci:

1. Le matcher tentera de rien correspondre « », dans la première .*?, tente de faire correspondre a et réussit, mais ne correspond pas b.
2. Le matcher tentera de faire correspondre la première lettre, "a", dans le premier .*?, essayera d'apparier a et réussira, mais ne pourra pas correspondre à b.
3. Le matcher tentera de faire correspondre les deux premières lettres, « aa », dans la première .*?, tente de faire correspondre a et réussit, tente de faire correspondre b et réussit, et Slurps puis le reste dans .*, « aaa ». Succès.

Il n'y a pas de backtrack cette fois, mais nous avons toujours un processus de correspondance plus compliqué pour chaque mouvement vers .*?. Cela peut être un gain de performance pour un match particulier ou une perte si l'itération à travers le match avant s'avère être plus lente.

Cela modifie également la façon dont la correspondance va se dérouler. Le match .* est gourmand et tente de correspondre autant que possible où .*? est plus conservatrice.

Par exemple, la chaîne "aaabaaabaaa".

Le premier modèle, (.*)ab(.*), correspondra à "aaabaa" à la première capture et "aaa" à la seconde.

Le deuxième motif, (.*?)ab(.*) correspondra « aa » à la première capture et « aaabaaa » à la seconde.

Answer 3

Au lieu de faire "(.*)someRegex(.*)", pourquoi ne pas simplement diviser la chaîne sur « someRegex » et obtenir les pièces du tableau résultant? Cela vous donnera le même résultat, mais beaucoup plus rapide et plus simple. Java prend en charge le fractionnement par regex si vous en avez besoin - http://www.regular-expressions.info/java.html