代码之家 › 专栏 › 技术社区 › Abhi

在Python中加速正则表达式

optimization regex python

Abhi · 技术社区 · 16 年前

我需要从HTML文件中快速提取文本。我使用以下正则表达式而不是一个成熟的解析器,因为我需要的是快速而不是精确(我有超过1TB的文本)。探查器显示脚本中的大部分时间都花在re.sub公司程序。有什么好方法可以加快我的进程?我可以用C实现一些部分,但是考虑到所花费的时间,我想知道这是否有帮助里面 re.sub公司,我认为这将是有效的实施。

# 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)
....

谢谢!

6 回复 | 直到 16 年前

Community Mohan Dere 9 年前

首先,使用为此构建的HTML解析器,如BeautifulSoup:

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

然后,您可以使用探查器识别剩余的特定慢点:

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

对于学习正则表达式,我发现掌握正则表达式非常有价值,无论编程语言是什么:

http://oreilly.com/catalog/9781565922570

也:

How can I debug a regular expression in python?

Speeding up regular expressions in Python

Alan Moore Chris Ballance 16 年前

每个文件都要处理五次,所以第一件事(正如paulsanwald所说)是通过组合regex来减少这个数量。我也会避免使用不情愿的量词,这些量词的设计是为了方便而牺牲效率。考虑一下这个正则表达式:

<script.*?</script>

每次 . 去消耗另一个角色,它首先要确保 </script> 在那个地方不匹配。这几乎就像在每个位置都做一个消极的展望:

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

但我们知道如果下一个角色是 < ,我们可以相应地调整正则表达式:

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

当我用这个目标字符串在RegexBuddy中测试它们时:

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

……不情愿的正则表达式需要173步才能匹配,而定制的正则表达式只需要28步。

将前三个regex合并为一个会产生以下结果:

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

你可能想把 <HEAD> 当你在做的时候(即。, (script|style|head) ).

我不知道你在用第四个正则表达式对字符实体做什么——你是不是也删除了那些?我猜第五个regex必须单独运行,因为它清理的一些空白是由前面的步骤生成的。但尝试将前三个正则表达式组合在一起,看看会有多大的不同。这会告诉你是否值得继续采用这种方法。

Paul Sanwald 16 年前

可以做的一件事是使用反向引用组合脚本/样式正则表达式。以下是一些示例数据:

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

使用perl:

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

它将匹配脚本或样式。我支持推荐的“掌握正则表达式”,这是一本很好的书。

eruciform 16 年前

如果您的用例确实要为数百万个文档中的每一个解析一些内容,那么我上面的答案将不会有帮助。我推荐一些启发式的方法,比如在它们上面做一对“纯文本”正则表达式,就像纯文本一样 /script/ 和 /style/ 如果可以的话,赶快把东西扔出去。事实上,你真的需要做结束标签检查吗?不是吗 <style 够好了吗?把验证留给其他人。如果快速的成功了,那么将其余的放入一个regex中,比如 /<script|<style|\s{2,}|etc.../ 这样就不必为每个regex遍历这么多文本。

David Z 16 年前

建议使用HTML解析器是一个很好的建议,因为它可能比正则表达式更快。但是我不确定beauthoulsoup是否适合这个工作,因为它从整个文件构造一个解析树并将整个内容存储在内存中。对于一TB的HTML,您需要一个淫秽的RAM来实现这一点;-)我建议您看看 HTMLParser ,它的编写级别比beauthoulsoup低,但我相信它是一个流解析器,因此它一次只加载一部分文本。

Tony Veijalainen 16 年前

## 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()