Ускорение регулярных выражений в Python - PullRequest
Новая
       11

Ускорение регулярных выражений в Python

4 голосов
/ 19 июля 2010

Мне нужно быстро извлечь текст из файлов HTML.Я использую следующие регулярные выражения вместо полноценного парсера, так как мне нужно быть быстрым, а не точным (у меня больше терабайта текста).Профилировщик показывает, что большую часть времени в моем скрипте тратится на процедуру re.sub.Каковы хорошие способы ускорить мой процесс?Я могу реализовать некоторые части в C, но мне интересно, поможет ли это, учитывая, что время потрачено внутри re.sub, что, я думаю, будет эффективно реализовано.!

Ответы [ 6 ]

9 голосов
/ 19 июля 2010

Во-первых, используйте для этого встроенный HTML-анализатор, например BeautifulSoup:

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

Затем вы можете идентифицировать оставшиеся конкретные медленные точки с помощью профилировщика:

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

И для изучения регулярных выражений я нашел очень полезным освоение регулярных выражений, независимо от языка программирования:

http://oreilly.com/catalog/9781565922570

Также:

Как отладить регулярное выражение в python?

Из-за повторного объяснения варианта использования, для этого запроса я бы сказал, что вышесказанное не то, что вам нужно Моя альтернативная рекомендация: Ускорение регулярных выражений в Python

5 голосов
/ 19 июля 2010

Вы обрабатываете каждый файл пять раз, поэтому первое, что вы должны сделать (как сказал Пол Санвальд), это попытаться уменьшить это число путем объединения ваших регулярных выражений. Я бы также не использовал квантификаторы с неохотой, которые созданы для удобства за счет эффективности. Рассмотрим это регулярное выражение: 

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

Я не знаю, что вы делаете с четвертым регулярным выражением для сущностей персонажей - вы тоже просто удаляете их? Я предполагаю, что пятое регулярное выражение должно быть запущено отдельно, так как некоторые из пробелов, которые он очищает, генерируются более ранними шагами. Но попробуйте это с первыми тремя объединенными регулярными выражениями и посмотрите, насколько это важно. Это должно сказать вам, стоит ли идти вперед с таким подходом.

1 голос
/ 19 июля 2010

Если ваш вариант использования действительно предназначен для разбора нескольких вещей для каждого из миллионов документов, то мой ответ выше не поможет. Я рекомендую некоторые эвристики, например, для начала сделать пару регулярных выражений с ними - например, простые /script/ и /style/, чтобы быстро выкинуть все, если можете. На самом деле, вам действительно нужно делать проверку конечных тегов вообще? Разве <style не достаточно хорош? Оставьте проверку для кого-то еще. Если быстрые из них удачны, оставьте остальные в одном регулярном выражении, например, /<script|<style|\s{2,}|etc.../, чтобы не нужно было проходить столько текста один раз для каждого регулярного выражения.

1 голос
/ 19 июля 2010

Предложение использовать синтаксический анализатор HTML является хорошим, поскольку вполне вероятно, что оно будет быстрее, чем регулярные выражения.Но я не уверен, что BeautifulSoup - правильный инструмент для работы, поскольку он создает дерево разбора из всего файла и сохраняет все это в памяти.Для терабайта HTML вам потребуется неприличное количество оперативной памяти для этого ;-) Я бы посоветовал вам взглянуть на HTMLParser, который написан на более низком уровне, чем BeautifulSoup, но яПолагайте, что это потоковый парсер, поэтому он будет загружать только немного текста за раз.

1 голос
/ 19 июля 2010

одна вещь, которую вы можете сделать, это объединить регулярные выражения сценария / стиля, используя обратные ссылки.Вот некоторые примеры данных: 

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

с использованием perl: 

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

это будет соответствовать как сценарию, так и стилю.Я рекомендую «освоить регулярные выражения», это отличная книга.

0 голосов
/ 19 июля 2010

Я бы использовал простую программу с обычным разделом 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()
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...