Accélération des expressions régulières en Python

J'ai besoin d'extraire rapidement du texte à partir de fichiers HTML. J'utilise les expressions régulières suivantes au lieu d'un analyseur à part entière puisque je dois être rapide plutôt que précis (j'ai plus d'un téraoctet de texte). Le profileur montre que la plupart du temps dans mon script est passé dans la procédure re.sub. Quels sont les bons moyens d'accélérer mon processus? Je peux implémenter certaines portions en C, mais je me demande si cela va aider étant donné que le temps est passé à l'intérieur re.sub, qui je pense serait implémenté efficacement.Accélération des expressions régulières en Python

# Remove scripts, styles, tags, entities, and extraneous spaces: 
scriptRx = re.compile("<script.*?/script>", re.I) 
styleRx  = re.compile("<style.*?/style>", re.I) 
tagsRx  = re.compile("<[!/]?[a-zA-Z-]+[^<>]*>") 
entitiesRx = re.compile("&[0-9a-zA-Z]+;") 
spacesRx = re.compile("\s{2,}") 
.... 
text = scriptRx.sub(" ", text) 
text = styleRx.sub(" ", text) 
....

Merci!

Source

2010-07-18 Abhi

+10

Je suis assez sûr un analyseur html décent (x) (ou un peu parseur fait à la main) surpasse regex. –

Il semble que vous appeliez .sub() plusieurs fois, si "texte" est grand, il sera beaucoup plus efficace d'essayer de faire ce dont vous avez besoin dans une regex. Dans votre question, vous n'avez pas précisé quelle regex est lente, est-ce que vous vouliez dire que toutes les combinaisons sont lentes, ou y en a-t-il une qui soit particulièrement lente? –

@Bart: Une raison de penser faire une analyse complète sera plus rapide que regex? Toute raison de penser qu'un analyseur fait à la main surpassera une bibliothèque regex optimisée et optimisée? – Abhi

Tout d'abord, utilisez un analyseur HTML construit pour cela, comme BeautifulSoup:

http://www.crummy.com/software/BeautifulSoup/

Ensuite, vous pouvez identifier qui reste des taches lentes particulières avec le profileur:

http://docs.python.org/library/profile.html

Et pour En apprenant les expressions régulières, j'ai trouvé que la maîtrise des expressions régulières était très précieuse, quel que soit le langage de programmation:

http://oreilly.com/catalog/9781565922570

aussi:

How can I debug a regular expression in python?

En raison de la reclarification de l'utilisation-cas, pour cette demande, je dirais que ce qui précède n'est pas ce que vous voulez. Mon autre recommandation serait: Speeding up regular expressions in Python

Source

2010-07-18 21:44:07 eruciform

lxml pourrait être plus rapide que BeautifulSoup, vous devriez essayer les deux. –

Évidemment, faire une analyse complète ne peut jamais être plus rapide que de substituer quelques expressions régulières, à moins qu'il y ait une bibliothèque d'analyse HTML super-duper. (J'ai essayé BS, c'est un ordre de grandeur plus lent que la regex que j'utilise). – Abhi

Le seul inconvénient de BeautifulSoup est sa vitesse: c'est très lent. –

une chose que vous pouvez faire est de combiner les regexes de style/script en utilisant des références arrières. voici quelques exemples de données:

$ cat sample 
<script>some stuff</script> 
<html>whatever </html> 
<style>some other stuff</style>

en Perl:

perl -ne "if (/<(script|style)>.*?<\/\1>/) { print $1; } " sample

il correspondra soit script ou le style. Je seconde la recommandation pour "maîtriser les expressions régulières", c'est un excellent livre.

Source

2010-07-18 21:49:50

La suggestion d'utiliser un analyseur HTML est bonne, car elle sera probablement plus rapide que les expressions régulières. Mais je ne suis pas sûr que BeautifulSoup soit le bon outil pour le travail, car il construit une arborescence d'analyse à partir du fichier entier et stocke le tout en mémoire. Pour un téraoctet de HTML, vous auriez besoin d'une quantité de RAM obscène pour le faire ;-) Je vous suggère de regarder HTMLParser, qui est écrit à un niveau inférieur à BeautifulSoup, mais je crois que c'est un analyseur de flux, donc ne chargera qu'un peu du texte à la fois.

Source

2010-07-18 21:50:47

Désolé, je voulais dire 50 millions de fichiers HTML. Ce n'est pas un gros morceau de texte. Quoi qu'il en soit, HTMLParser n'a pas fonctionné: c'est du HTML dans la nature. Existe-t-il un moyen propre d'extraire tout le texte de l'arbre d'analyse de BeautifulSoup? – Abhi

Ah, gotcha. Je ne sais pas grand-chose sur BeautifulSoup, mais j'imagine qu'il serait possible d'extraire le texte. Avez-vous essayé de le convertir en une chaîne? ie 'soup = BeautifulSoup (...)' then 'str (soupe)' (je ne sais pas si c'est ça, mais ce serait ma première supposition si je travaillais sur votre projet) –

Merci de votre retour: Mais j'ai tapé ce commentaire à la hâte. BS est un ordre de grandeur plus lent que les substitutions regex, donc l'extraction de texte à partir de son analyse est discutable: P – Abhi

Si votre cas d'utilisation est en effet d'analyser quelques choses pour chacun des millions de documents, alors ma réponse ci-dessus n'aidera pas. Je recommande quelques heuristiques, comme faire un couple "regexes" texte droit sur eux pour commencer - comme tout simplement /script/ et /style/ pour jeter les choses rapidement si vous le pouvez. En fait, avez-vous vraiment besoin de faire la vérification de l'étiquette finale? N'est-ce pas <style assez bon? Laissez la validation pour quelqu'un d'autre. Si les rapides réussissent, placez le reste dans une seule regex, comme /<script|<style|\s{2,}|etc.../ afin qu'il ne soit pas obligé de passer autant de texte une fois pour chaque regex.

Source

2010-07-18 23:48:31 eruciform

Vous traitez chaque fichier cinq fois, donc la première chose à faire (comme l'a dit Paul Sanwald) est d'essayer de réduire ce nombre en combinant vos regex ensemble. J'éviterais également d'utiliser des quantificateurs réticents, qui sont conçus pour la commodité au détriment de l'efficacité. Considérez ceci regex:

<script.*?</script>

Chaque fois que le . va consommer un autre personnage, il doit d'abord se assurer </script> ne correspondra pas à à cet endroit. Il est presque comme faire un test avant négatif à chaque position:

<script(?:(?!</script>).)*</script>

Mais nous savons qu'il n'y a aucun point faire le test avant si le caractère suivant est tout sauf <, et nous pouvons adapter l'expression rationnelle en conséquence:

<script[^<]*(?:<(?!/script>)[^<]*)*</script>

Quand je les tester dans RegexBuddy avec cette chaîne cible:

<script type="text/javascript">var imagePath='http://sstatic.net/stackoverflow/img/';</script>

... l'expression rationnelle réticente prend 173 mesures pour rendre le match, alors que le sur mesure re gex ne prend que 28.

La combinaison de vos trois premiers regexes en un seul donne cette bête:

<(?:(script|style)[^<]*(?:<(?!/\1)[^<]*)*</\1>|[!/]?[a-zA-Z-]+[^<>]*>)

Vous pouvez zapper l'élément <HEAD> pendant que vous y êtes (à savoir (script|style|head)).

Je ne sais pas ce que vous faites avec la quatrième regex, pour les entités de caractères - est-ce que vous ne faites que les effacer? Je suppose que la cinquième regex doit être exécutée séparément, car une partie des espaces supprimés est générée par les étapes précédentes. Mais essayez-le avec les trois premières regexes combinées et voyez combien cela fait de différence. Cela devrait vous dire si cela vaut la peine d'aller de l'avant avec cette approche.

Source

2010-07-19 01:38:08

Merci pour l'aperçu sur les quantificateurs réticents. Le profilage a montré que ceux-ci sont chers! Je vais modifier mon regex. – Abhi

J'utiliser le programme simple avec partition Python régulière quelque chose comme cela, mais il est testé uniquement avec un seul style exemple de fichier:

## simple filtering when not hierarchical tags inside other discarded tags 

start_tags=('<style','<script') 
end_tags=('</style>','</script>') 

##print("input:\n %s" % open('giant.html').read()) 
out=open('cleaned.html','w') 
end_tag='' 

for line in open('giant.html'): 
    line=' '.join(line.split()) 
    if end_tag: 
     if end_tag in line: 
      _,tag,end = line.partition(end_tags[index]) 
      if end.strip(): 
       out.write(end) 
      end_tag='' 
     continue ## discard rest of line if no end tag found in line 

    found=(index for index in (start_tags.index(start_tag) 
           if start_tag in line else '' 
           for start_tag in start_tags) 
      if index is not '') 
    for index in found: 
     start,tag,end = line.partition(start_tags[index]) 
     # drop until closing angle bracket of start tag 
     tag,_ ,end = end.partition('>') 
     # check if closing tag already in same line 
     if end_tags[index] in end: 
      _,tag,end = end.partition(end_tags[index]) 
      if end.strip(): 
       out.write(end) 
      end_tag = '' # end tag reset after found 
     else: 
      end_tag=end_tags[index] 
      out.write(end) # no end tag at same line 
    if not end_tag: out.write(line+'\n') 

out.close() 
## print 'result:\n%s' % open('cleaned.html').read()

Source

2010-07-19 16:35:19

Accélération des expressions régulières en Python

Répondre

Questions connexes