Ускорьте миллионы замен регулярных выражений в 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"
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:
foobar|baz
would matchfoobar
orbaz
, but notfoobaz
foo(bar|baz)
would save unneeded information to a capturing group.
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
Возможно, вам захочется попробовать предварительную обработку предложений для кодирования границ слов. По сути, превратите каждое предложение в список слов, разделив его по границам слов.
Это должно быть быстрее, потому что для обработки предложения вам просто нужно пройтись по каждому слову и проверить, совпадает ли оно.
В настоящее время при поиске регулярных выражений приходится каждый раз заново проходить всю строку, ища границы слов, а затем "отбрасывать" результат этой работы перед следующим проходом.