logo标签列表

在Python中加速正则表达式

pythonregexoptimization
4

我需要快速从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)
....

谢谢！

10
我相信一个像样的（x）HTML解析器（或者是一个小型手工解析器）比正则表达式更高效。 - Bart Kiers
看起来你调用了相当多的.sub()，如果"text"很大，在一个正则表达式中完成所需操作会更有效率。在你的问题中，你没有澄清哪个正则表达式很慢，是指它们所有组合在一起都很慢，还是有一个特别慢的？ - Paul Sanwald
@Bart: 有什么理由认为完全解析比正则表达式更快吗？有什么理由认为手动制作的解析器会胜过精细调整和优化的正则表达式库吗？ - Abhi
出于同样的原因，我不是在寻求准确性，而是速度。 - Abhi
2
@Ahbi：正则表达式搜索可能比解析器递归得多，特别是如果您使用（如上所示）大量的可变宽度通配符表达式，例如.*？一个简单的解析器可能只需对字符串进行一次遍历。如果它主要依赖于内置的字符串函数，它可能非常快速。 - twneale
6个回答
8

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

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

然后，您可以使用性能分析器识别剩余的特定慢速区域：

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

对于学习正则表达式，我发现《精通正则表达式》非常有价值，无论使用哪种编程语言：

http://oreilly.com/catalog/9781565922570

同时：

如何在Python中调试正则表达式？

由于用例重新澄清，因此对于此请求，我会说上述内容不是您想要的。我的备选建议是：加快Python中的正则表达式速度

lxml可能比BeautifulSoup更快，你应该尝试两种方法。 - Juri Robl
显然，除非有一个超级厉害的HTML解析库，否则完整解析永远不可能比替换几个正则表达式更快。（我尝试过BS，它比我使用的正则表达式慢了一个数量级）。 - Abhi
2
@Abhi：嗯，这取决于您对“解析”的理解。许多解析器（包括BS在内）使用正则表达式来识别标记和属性，由于所有正则表达式都很慢，因此它们将变得很慢。但是，人们可以构造一个有限状态机作为解析器，它逐个字符进行处理，并根据字符和当前状态改变其状态，这将会快得多。（对于HTML来说编码相当复杂） - David Z
2
我认为David Zaslavsky说得很对：如果你只是简单地删除HTML的一部分，那么就写一个逐字符解析。许多解析器要处理的复杂性（标签/嵌套）不存在，因为你不关心记住它们，只是要删除它们。 - Wrikken
更新了另一个相关问题的链接，该问题涉及打开正则表达式调试功能，这也可能有助于对其进行性能分析。 - eruciform
显示剩余7条评论
5

您正在对每个文件进行五次处理，因此首先要做的事情（正如Paul Sanwald所说）是尝试通过合并您的正则表达式来减少该数量。我还建议避免使用勉强量词，这些量词为方便而设计，但会牺牲效率。请考虑以下正则表达式：

<script.*?</script>

每次 . 继续读取下一个字符之前，都必须确保该位置不会匹配 </script>。这几乎就像在每个位置上进行负向先行断言：
<script(?:(?!</script>).)*</script>

但是我们知道，如果下一个字符不是<，那么进行前瞻就没有意义，因此我们可以相应地调整正则表达式：

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

当我在RegexBuddy中测试它们时，使用此目标字符串：
<script type="text/javascript">var imagePath='http://sstatic.net/stackoverflow/img/';</script>

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

将您的前三个正则表达式合并为一个，得到这个怪物：

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

在这个过程中，你可能想要删除<HEAD>元素（即(script|style|head)）。

我不知道你对第四个正则表达式的字符实体做了什么 - 你也把它删除了吗？我猜第五个正则表达式必须单独运行，因为一些它清理的空格是由前面的步骤生成的。但是尝试将前三个正则表达式组合起来，看看它会产生多大的差异。这应该能告诉你是否值得继续使用这种方法。

感谢您提供关于勉强量词的见解。分析表明它们非常耗费资源！我会修改我的正则表达式。 - Abhi
1

你可以做的一件事是使用反向引用结合脚本/样式正则表达式。这里有一些示例数据：

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

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

它将匹配脚本或样式。我赞同“精通正则表达式”的推荐，这是一本非常好的书。

1
如果您的用例确实是为数百万个文档解析一些内容，那么我上面的答案就不会有帮助。我建议使用一些启发式方法，比如首先对它们进行一些“纯文本”正则表达式匹配，比如只是简单的/script/和/style/，以便快速排除一些东西。实际上，您真的需要进行结束标记检查吗？<style不是已经足够好了吗？将验证留给其他人。如果快速匹配成功，则将其余部分放入单个正则表达式中，例如/<script|<style|\s{2,}|etc.../，这样它就不必为每个正则表达式遍历那么多文本。
0

我会使用简单的程序和常规的Python分区来处理类似这样的东西，但是它只被一个样式示例文件测试过：

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

建议使用HTML解析器是一个好主意，因为它很可能比正则表达式更快。但我不确定BeautifulSoup是否是适合这项工作的正确工具，因为它从整个文件构造了一个解析树并将整个文件存储在内存中。对于一太字节的HTML，你需要大量的RAM来完成这个任务;-) 我建议您查看HTMLParser，它比BeautifulSoup写得更底层，但我相信它是一个流解析器，所以它只会一次加载一小部分文本。

抱歉，我的意思是五千万个HTML文件。它们不是一个大文本块。无论如何，HTMLParser没有起作用：这是野外的HTML。有没有一种干净的方法从BeautifulSoup的解析树中提取所有文本？ - Abhi
啊，明白了。我对BeautifulSoup并不是很了解，但我想提取文本可能是有可能的。你试过将它转换为字符串吗？例如soup = BeautifulSoup(...)然后str(soup)（如果我在处理你的项目，这将是我的第一个猜测）。 - David Z
谢谢回复 :) 但我匆忙中输入了那个评论。BS比正则表达式替换慢一个数量级，因此从其解析中提取文本是无意义的 :P - Abhi
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接