Вопрос-Ответ

Speed up millions of regex replacements in Python 3

Ускорьте миллионы замен регулярных выражений в Python 3

У меня есть два списка:


  • список из около 750 Тыс. "предложений" (длинные строки)

  • список из примерно 20 Тыс. "слов", которые я хотел бы удалить из своих 750 тыс. предложений

Итак, мне приходится перебирать 750 Тыс. предложений и выполнять около 20 тыс. замен, но только если мои слова на самом деле "слова" и не являются частью более крупной строки символов.

Я делаю это, предварительно скомпилировав свои слова так, чтобы они были окружены метасимволом \b word-boundary:

compiled_words = [re.compile(r'\b' + word + r'\b') for word in my20000words]

Затем я перебираю свои "предложения":

import re

for sentence in sentences:
for word in compiled_words:
sentence = re.sub(word, "", sentence)
# put sentence into a growing list

Этот вложенный цикл обрабатывает около 50 предложений в секунду, что приятно, но все равно требуется несколько часов, чтобы обработать все мои предложения.


  • Есть ли способ использовать str.replace метод (который, я считаю, быстрее), но по-прежнему требующий, чтобы замены происходили только на границах слов?



  • В качестве альтернативы, есть ли способ ускорить re.sub метод? Я уже немного улучшил скорость, пропустив re.sub если длина моего слова > превышает длину моего предложения, но это не такое уж большое улучшение.



Я использую Python 3.5.2

Переведено автоматически
Ответ 1

TLDR

Используйте этот метод, если вам нужно самое быстрое решение на основе регулярных выражений. Для набора данных, аналогичного OP, это примерно в 1000 раз быстрее принятого ответа.

Если вам не нужны регулярные выражения, используйте эту версию на основе наборов, которая в 2000 раз быстрее, чем объединение регулярных выражений.

Оптимизировано регулярное выражение с помощью Trie

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

Можно создать Trie со всеми запрещенными словами и записать соответствующее регулярное выражение. Результирующее trie или регулярное выражение на самом деле не читается человеком, но они позволяют выполнять очень быстрый поиск и сопоставление.

Пример

['foobar', 'foobah', 'fooxar', 'foozap', 'fooza']

Объединение регулярных выражений

Список преобразуется в trie:

{
'f': {
'o': {
'o': {
'x': {
'a': {
'r': {
'': 1
}
}
},
'b': {
'a': {
'r': {
'': 1
},
'h': {
'': 1
}
}
},
'z': {
'a': {
'': 1,
'p': {
'': 1
}
}
}
}
}
}
}

And then to this regex pattern:

r"\bfoo(?:ba[hr]|xar|zap?)\b"

Regex trie

The huge advantage is that to test if zoo matches, the regex engine only needs to compare the first character (it doesn't match), instead of trying the 5 words. It's a preprocess overkill for 5 words, but it shows promising results for many thousand words.

Note that (?:) non-capturing groups are used because:

Code

Here's a slightly modified gist, which we can use as a trie.py library:

import re


class Trie():
"""Regex::Trie in Python. Creates a Trie out of a list of words. The trie can be exported to a Regex pattern.
The corresponding Regex should match much faster than a simple Regex union."""


def __init__(self):
self.data = {}

def add(self, word):
ref = self.data
for char in word:
ref[char] = char in ref and ref[char] or {}
ref = ref[char]
ref[''] = 1

def dump(self):
return self.data

def quote(self, char):
return re.escape(char)

def _pattern(self, pData):
data = pData
if "" in data and len(data.keys()) == 1:
return None

alt = []
cc = []
q = 0
for char in sorted(data.keys()):
if isinstance(data[char], dict):
try:
recurse = self._pattern(data[char])
alt.append(self.quote(char) + recurse)
except:
cc.append(self.quote(char))
else:
q = 1
cconly = not len(alt) > 0

if len(cc) > 0:
if len(cc) == 1:
alt.append(cc[0])
else:
alt.append('[' + ''.join(cc) + ']')

if len(alt) == 1:
result = alt[0]
else:
result = "(?:" + "|".join(alt) + ")"

if q:
if cconly:
result += "?"
else:
result = "(?:%s)?" % result
return result

def pattern(self):
return self._pattern(self.dump())

Test

Here's a small test (the same as this one):

# Encoding: utf-8
import re
import timeit
import random
from trie import Trie

with open('/usr/share/dict/american-english') as wordbook:
banned_words = [word.strip().lower() for word in wordbook]
random.shuffle(banned_words)

test_words = [
("Surely not a word", "#surely_NöTäWORD_so_regex_engine_can_return_fast"),
("First word", banned_words[0]),
("Last word", banned_words[-1]),
("Almost a word", "couldbeaword")
]

def trie_regex_from_words(words):
trie = Trie()
for word in words:
trie.add(word)
return re.compile(r"\b" + trie.pattern() + r"\b", re.IGNORECASE)

def find(word):
def fun():
return union.match(word)
return fun

for exp in range(1, 6):
print("\nTrieRegex of %d words" % 10**exp)
union = trie_regex_from_words(banned_words[:10**exp])
for description, test_word in test_words:
time = timeit.timeit(find(test_word), number=1000) * 1000
print(" %s : %.1fms" % (description, time))

It outputs:

TrieRegex of 10 words
Surely not a word : 0.3ms
First word : 0.4ms
Last word : 0.5ms
Almost a word : 0.5ms

TrieRegex of 100 words
Surely not a word : 0.3ms
First word : 0.5ms
Last word : 0.9ms
Almost a word : 0.6ms

TrieRegex of 1000 words
Surely not a word : 0.3ms
First word : 0.7ms
Last word : 0.9ms
Almost a word : 1.1ms

TrieRegex of 10000 words
Surely not a word : 0.1ms
First word : 1.0ms
Last word : 1.2ms
Almost a word : 1.2ms

TrieRegex of 100000 words
Surely not a word : 0.3ms
First word : 1.2ms
Last word : 0.9ms
Almost a word : 1.6ms

Для справки, регулярное выражение начинается так:


(?:a(?:(?:\'s|a(?:\'s|chen|liyah(?:\'s)?|r(?:dvark(?:(?:\'s|s))?|on))|b(?:\'s|a(?:c(?:us(?:(?:\'s|es))?|[ik])|ft|lone(?:(?:\'s|s))?|ndon(?:(?:ed|ing|ment(?:\'s)?|s))?|s(?:e(?:(?:ment(?:\'s)?|[ds]))?|h(?:(?:e[ds]|ing))?|ing)|t(?:e(?:(?:ment(?:\'s)?|[ds]))?|ing|toir(?:(?:\'s|s))?))|b(?:as(?:id)?|e(?:ss(?:(?:\'s|es))?|y(?:(?:\'s|s))?)|ot(?:(?:\'s|t(?:\'s)?|s))?|reviat(?:e[ds]?|i(?:ng|on(?:(?:\'s|s))?))|y(?:\'s)?|\é(?:(?:\'s|s))?)|d(?:icat(?:e[ds]?|i(?:ng|on(?:(?:\'s|s))?))|om(?:en(?:(?:\'s|s))?|inal)|u(?:ct(?:(?:ed|i(?:ng|on(?:(?:\'s|s))?)|or(?:(?:\'s|s))?|s))?|l(?:\'s)?))|e(?:(?:\'s|am|l(?:(?:\'s|ard|son(?:\'s)?))?|r(?:deen(?:\'s)?|nathy(?:\'s)?|ra(?:nt|tion(?:(?:\'s|s))?))|t(?:(?:t(?:e(?:r(?:(?:\'s|s))?|d)|ing|or(?:(?:\'s|s))?)|s))?|yance(?:\'s)?|d))?|hor(?:(?:r(?:e(?:n(?:ce(?:\'s)?|t)|d)|ing)|s))?|i(?:d(?:e[ds]?|ing|jan(?:\'s)?)|gail|l(?:ene|it(?:ies|y(?:\'s)?)))|j(?:ect(?:ly)?|ur(?:ation(?:(?:\'s|s))?|e[ds]?|ing))|l(?:a(?:tive(?:(?:\'s|s))?|ze)|e(?:(?:st|r))?|oom|ution(?:(?:\'s|s))?|y)|m\'s|n(?:e(?:gat(?:e[ds]?|i(?:ng|on(?:\'s)?))|r(?:\'s)?)|ormal(?:(?:it(?:ies|y(?:\'s)?)|ly))?)|o(?:ard|de(?:(?:\'s|s))?|li(?:sh(?:(?:e[ds]|ing))?|tion(?:(?:\'s|ist(?:(?:\'s|s))?))?)|mina(?:bl[ey]|t(?:e[ds]?|i(?:ng|on(?:(?:\'s|s))?)))|r(?:igin(?:al(?:(?:\'s|s))?|e(?:(?:\'s|s))?)|t(?:(?:ed|i(?:ng|on(?:(?:\'s|ist(?:(?:\'s|s))?|s))?|ve)|s))?)|u(?:nd(?:(?:ed|ing|s))?|t)|ve(?:(?:\'s|board))?)|r(?:a(?:cadabra(?:\'s)?|d(?:e[ds]?|ing)|ham(?:\'s)?|m(?:(?:\'s|s))?|si(?:on(?:(?:\'s|s))?|ve(?:(?:\'s|ly|ness(?:\'s)?|s))?))|east|idg(?:e(?:(?:ment(?:(?:\'s|s))?|[ds]))?|ing|ment(?:(?:\'s|s))?)|o(?:ad|gat(?:e[ds]?|i(?:ng|on(?:(?:\'s|s))?)))|upt(?:(?:e(?:st|r)|ly|ness(?:\'s)?))?)|s(?:alom|c(?:ess(?:(?:\'s|e[ds]|ing))?|issa(?:(?:\'s|[es]))?|ond(?:(?:ed|ing|s))?)|en(?:ce(?:(?:\'s|s))?|t(?:(?:e(?:e(?:(?:\'s|ism(?:\'s)?|s))?|d)|ing|ly|s))?)|inth(?:(?:\'s|e(?:\'s)?))?|o(?:l(?:ut(?:e(?:(?:\'s|ly|st?))?|i(?:on(?:\'s)?|sm(?:\'s)?))|v(?:e[ds]?|ing))|r(?:b(?:(?:e(?:n(?:cy(?:\'s)?|t(?:(?:\'s|s))?)|d)|ing|s))?|pti...


Это действительно нечитабельно, но для списка из 100000 запрещенных слов это Trie regex в 1000 раз быстрее, чем простое объединение регулярных выражений!

Вот схема полного trie, экспортированного с помощью trie-python-graphviz и graphviz twopi:

Введите описание изображения здесь

Ответ 2

TLDR

Используйте этот метод (с заданным поиском), если вам нужно самое быстрое решение. Для набора данных, аналогичного OP, это примерно в 2000 раз быстрее принятого ответа.

Если вы настаиваете на использовании регулярных выражений для поиска, используйте эту версию на основе trie, которая по-прежнему в 1000 раз быстрее, чем объединение регулярных выражений.

Теория

Если ваши предложения не представляют собой огромные строки, вероятно, возможно обрабатывать намного больше 50 в секунду.

Если вы сохраните все запрещенные слова в наборе, будет очень быстро проверить, включено ли в этот набор другое слово.

Упакуйте логику в функцию, передайте эту функцию в качестве аргумента re.sub и готово!

Код

import re
with open('/usr/share/dict/american-english') as wordbook:
banned_words = set(word.strip().lower() for word in wordbook)


def delete_banned_words(matchobj):
word = matchobj.group(0)
if word.lower() in banned_words:
return ""
else:
return word

sentences = ["I'm eric. Welcome here!", "Another boring sentence.",
"GiraffeElephantBoat", "sfgsdg sdwerha aswertwe"] * 250000

word_pattern = re.compile('\w+')

for sentence in sentences:
sentence = word_pattern.sub(delete_banned_words, sentence)

Преобразованные предложения представляют собой:

' .  !
.
GiraffeElephantBoat
sfgsdg sdwerha aswertwe

Обратите внимание, что:


  • поиск не чувствителен к регистру (благодаря lower())

  • замена слова на "" может оставить два пробела (как в вашем коде)

  • В python3 \w+ также используются символы с ударением (например, "ångström").

  • Любой символ, не являющийся словом (табуляция, пробел, перевод строки, метки, ...), останется нетронутым.

Производительность

Существует миллион предложений, banned_words содержит почти 100000 слов, а скрипт выполняется менее чем за 7 секунд.

Для сравнения, для ответа Liteye потребовалось 160 секунд на 10 тысяч предложений.

Благодаря n общему количеству слов и m количеству запрещенных слов, код OP и Liteye является O(n*m).

Для сравнения, мой код должен выполняться в O(n+m). Учитывая, что предложений намного больше, чем запрещенных слов, алгоритм становится O(n).

Тест объединения регулярных выражений

В чем сложность поиска регулярных выражений с помощью '\b(word1|word2|...|wordN)\b' шаблона? Это O(N) или O(1)?

Довольно сложно понять, как работает движок регулярных выражений, поэтому давайте напишем простой тест.

Этот код извлекает 10**i случайные английские слова в список. Он создает соответствующее объединение регулярных выражений и тестирует его с другими словами :


  • one - это явно не слово (оно начинается с #)

  • первое слово в списке - one

  • одно - последнее слово в списке

  • одно из них выглядит как word, но таковым не является


import re
import timeit
import random

with open('/usr/share/dict/american-english') as wordbook:
english_words = [word.strip().lower() for word in wordbook]
random.shuffle(english_words)

print("First 10 words :")
print(english_words[:10])

test_words = [
("Surely not a word", "#surely_NöTäWORD_so_regex_engine_can_return_fast"),
("First word", english_words[0]),
("Last word", english_words[-1]),
("Almost a word", "couldbeaword")
]


def find(word):
def fun():
return union.match(word)
return fun

for exp in range(1, 6):
print("\nUnion of %d words" % 10**exp)
union = re.compile(r"\b(%s)\b" % '|'.join(english_words[:10**exp]))
for description, test_word in test_words:
time = timeit.timeit(find(test_word), number=1000) * 1000
print(" %-17s : %.1fms" % (description, time))

It outputs:

First 10 words :
["geritol's", "sunstroke's", 'fib', 'fergus', 'charms', 'canning', 'supervisor', 'fallaciously', "heritage's", 'pastime']

Union of 10 words
Surely not a word : 0.7ms
First word : 0.8ms
Last word : 0.7ms
Almost a word : 0.7ms

Union of 100 words
Surely not a word : 0.7ms
First word : 1.1ms
Last word : 1.2ms
Almost a word : 1.2ms

Union of 1000 words
Surely not a word : 0.7ms
First word : 0.8ms
Last word : 9.6ms
Almost a word : 10.1ms

Union of 10000 words
Surely not a word : 1.4ms
First word : 1.8ms
Last word : 96.3ms
Almost a word : 116.6ms

Union of 100000 words
Surely not a word : 0.7ms
First word : 0.8ms
Last word : 1227.1ms
Almost a word : 1404.1ms

Похоже, что поиск одного слова с '\b(word1|word2|...|wordN)\b' шаблоном имеет:


  • O(1) наилучший вариант

  • O(n/2) средний случай, который все еще O(n)

  • O(n) наихудший вариант

Эти результаты согласуются с простым циклическим поиском.

Гораздо более быстрой альтернативой объединению регулярных выражений является создание шаблона регулярных выражений из дерева.

Ответ 3

Единственное, что вы можете попробовать, это скомпилировать один-единственный шаблон, подобный "\b(word1|word2|word3)\b".

Поскольку re фактическое сопоставление выполняется на C-коде, экономия может быть значительной.

Как указал @pvg в комментариях, он также выигрывает от однопроходного сопоставления.

Если ваши слова не являются регулярными выражениями, ответ Эрика будет быстрее.

Ответ 4

Возможно, вам захочется попробовать предварительную обработку предложений для кодирования границ слов. По сути, превратите каждое предложение в список слов, разделив его по границам слов.

Это должно быть быстрее, потому что для обработки предложения вам просто нужно пройтись по каждому слову и проверить, совпадает ли оно.

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

python regex string performance