Python 3에서 수백만 개의 정규식 교체 속도 향상
두 가지 목록이 있습니다.
- 약 750,000개의 "문장"(긴 문자열) 목록
- 내 750K 문장에서 삭제하고 싶은 약 2만 개의 "단어" 목록
그래서 저는 750,000개의 문장을 반복해서 읽고 약 20,000개의 대체를 수행해야 합니다. 하지만 제 단어가 실제로 "단어"이고 더 큰 문자열의 일부가 아닌 경우에만 가능합니다.
나는 내 말을 미리 컴파일해서 그들이 옆에 있도록 하는 것입니다.\b단어로 구분된 메타문자:
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만약 내 단어의 길이가 내 문장의 길이보다 >이지만, 그것은 크게 개선되지 않습니다.
파이썬 3.5.2를 사용하고 있습니다.
TLDR
가장 빠른 정규식 기반 솔루션을 원하는 경우 이 방법을 사용합니다.OP와 유사한 데이터 세트의 경우, 승인된 답변보다 약 1000배 더 빠릅니다.
정규식에 관심이 없다면 정규식 유니온보다 2000배 빠른 이 세트 기반 버전을 사용하십시오.
Trie를 통한 최적화된 정규식
정규식 엔진이 패턴 최적화를 잘 수행하지 못하기 때문에 간단한 정규식 조합 접근 방식은 많은 금지 단어와 함께 느려집니다.
모든 금지 단어가 포함된 트라이를 생성하고 해당 정규식을 작성할 수 있습니다.결과적으로 나타나는 트라이나 정규식은 실제로 사람이 읽을 수 있는 것은 아니지만 매우 빠른 조회 및 일치를 허용합니다.
예
['foobar', 'foobah', 'fooxar', 'foozap', 'fooza']
목록이 트라이로 변환됩니다.
{
'f': {
'o': {
'o': {
'x': {
'a': {
'r': {
'': 1
}
}
},
'b': {
'a': {
'r': {
'': 1
},
'h': {
'': 1
}
}
},
'z': {
'a': {
'': 1,
'p': {
'': 1
}
}
}
}
}
}
}
그리고 다음 정규식 패턴으로 이동합니다.
r"\bfoo(?:ba[hr]|xar|zap?)\b"
가장 큰 장점은 테스트를 할 수 있다는 것입니다.zoo일치합니다. 정규식 엔진은 5개의 단어를 사용하는 대신 첫 번째 문자만 비교하면 됩니다(일치하지 않습니다).5개 단어에 대한 전처리 오버킬이지만 수천 개 단어에 대한 유망한 결과를 보여줍니다.
비캡처 그룹은 다음과 같은 이유로 사용됩니다.
코드
여기 약간 수정된 요지가 있는데, 우리는 이것을 사용할 수 있습니다.trie.py라이브러리:
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())
시험
# 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))
출력:
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)|on)|b(?:\'s|es)|a(?:c(?::(?:\'s|es)?|[ik])|ft|ft(?:(?:\'s|s)?|ndon(?:(?:ed|ing(?:\'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)?)|ot(?:(?:\'s)|s)|reviat(?:e[ds]?|i(?:ng|on(?:(?:\'s)?)|y(?:\'s)?|\é(?:(?:(?:\'s)?)|d(?:icat(?)?:e[ds]?|i(?:ng|on(?:(?:(?:\'s|s)?)|om(?:en(?:(?:\'s|s)?|inal)|u(?:ct(?:::(?:ed|i)?:ng|on(?:(?:\'s|s)|또는(?:(?:\'s)|s)?|l(?:\'s)?)|e(?:\'s|am(?:(?:\'s)?)|r(?:deen(?:\'s)|nathy(?:\'s)?|ra(?:nt|tion(?:(?:(?\s|s)?)|t(?:(?:e(?:r(?:(?:\s|s)?)|d)|ing|또는(?:(?:(?:\s)|s)|s)|yance(?:\'s)?|d)?|hor(?:r(?:e(?:n(?:ce(?:\'s)|t)|ing)|s)?|i(?:d(?:e[ds])?|ing|jan(?:\'s)?|가일|l(?:ene|그것(?: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)?r(?:it(?:ies|y(?:\'s)|ly)?|o(?:ard)|de(?:(:(?:(?:\'s)s)?)|li?(ds)?|tion(?:(?:\'s|ist(?:(?:\'s|s)?)|t(?:bl[ey]|t(?):e[ds]?|i(?:ng|on(?:(?:(?:\'s)?)|r(?:igin(?:al(?:(?:\'s|s)?)|e(?:(?:\'s|s)?)|t(?:(?:ed|i)?:ng|on(?:(?:\'s)|ist(?:(?:(?:\'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|lyness)?:\'s)?|s)?)|동|idg(?:e(?:(?:ment(?:(?:(?:\'s|s)?|[ds]?|ing|ment(?:(?:\'s|s)|o(?:ad|gat(?):e[ds]?|i(?:ng|on(?:(?:\'s|s)?) ||ness(?:(?:e(?:st|r)|lyness(?):\'s)?)|s(?:alom|c(?:ess(?:(?:\'s|e[ds]|ing))?|issa(?:(?:\'s|[es])? |ond(?:(?:ed|ing|s)?)|en(?:ce(?:(?:\'s|s)?|t(?:(?:e(?:e(?:\'s)|d)|ing|ly|s)?)|inth(?:(?:\'s)?|o(?:l(?:ut(?:e(?:(?:\'s)?|sm(?::\'s)?)|v(?:e[ds]|ing)|r(?:(?:e?:(cy):(s):(s?)|t?)?)|d)|ing|s)?|pti...
정말 읽을 수 없는 일이지만, 100,000개의 금지 단어 목록을 위해, 이 트리렉스는 단순한 정규식 연합보다 1000배 더 빠릅니다!
다음은 trie-python-graphviz 및 graphviz와 함께 내보낸 전체 trie의 다이어그램입니다.
TLDR
가장 빠른 해결 방법을 원하는 경우 이 방법(설정 조회 포함)을 사용합니다.OP와 유사한 데이터 세트의 경우, 승인된 답변보다 약 2,000배 더 빠릅니다.
조회에 정규식을 사용해야 하는 경우 정규식 유니온보다 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+악센트가 있는 예: 악가있예문자는트센예(자문:▁accers▁(는)와 일치합니다."ångström"). - 단어가 아닌 모든 문자(탭, 공백, 새 줄, 표시 등)는 그대로 유지됩니다.
성능
의 문장이 있는데, 백만개문있고이장의,있,고▁sentences▁there이▁million장,banned_words거의 100,000개의 단어가 있으며 스크립트는 7초 이내에 실행됩니다.
이에 비해 Liteeye의 답변은 1만 문장에 160이 필요했습니다.
와 함께n와 의말총되는것과이의 것m단어의 는 금지단의양, OP와 Liteeye의입니다.O(n*m).
그에 비해, 내 코드는 실행되어야 합니다.O(n+m)금지된 단어보다 더 많은 문장이 있다는 것을 고려하면, 알고리즘은O(n).
정규식 조합 테스트
은 무엇입니까?'\b(word1|word2|...|wordN)\b'패턴?그런가요?O(N)또는O(1)?
정규식 엔진의 작동 방식을 파악하기가 상당히 어려운데, 간단한 테스트를 작성해 보겠습니다.
는 이코는추다니됩출을 추출합니다.10**i영어 단어를 무작위로 목록에 넣다대응하는 정규식 유니언을 생성하고 다른 단어로 테스트합니다.
- . (이 단어는 는분그단아다닙니어가다시 ( 하나은작니합히명것그▁(다다▁with니니아▁one닙시▁(합it)로 시작합니다.
#) - 하나는 목록의 첫 번째 단어입니다.
- 하나는 목록의 마지막 단어입니다.
- 하나는 단어처럼 보이지만 그렇지 않습니다.
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))
출력:
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)의 경우
이러한 결과는 단순 루프 검색과 일치합니다.
정규식 조합에 대한 훨씬 빠른 대안은 트라이에서 정규식 패턴을 만드는 것입니다.
할 수 한 는 한가시도수있것다은같것다컴입니패파는하일턴단을일은음과 같은 하나의 입니다."\b(word1|word2|word3)\b".
ㅠㅠreC 코드를 사용하여 실제 매칭을 수행하면 비용을 크게 절감할 수 있습니다.
@pvg가 코멘트에서 지적했듯이, 그것은 또한 단일 패스 매칭의 혜택을 받습니다.
만약 당신의 말이 정규 표현이 아니라면, 에릭의 대답이 더 빠릅니다.
한 가지 시도하고 싶은 것은 단어 경계를 인코딩하기 위해 문장을 사전 처리하는 것입니다.기본적으로 단어 경계를 분할하여 각 문장을 단어 목록으로 전환합니다.
문장을 처리하려면 단어 하나하나를 훑어보고 일치하는지 확인하기만 하면 되기 때문에 이것이 더 빨라야 합니다.
현재 정규식 검색은 단어 경계를 찾고 다음 패스 전에 이 작업의 결과를 "폐기"할 때마다 전체 문자열을 다시 검색해야 합니다.
테스트 세트와 함께 빠르고 쉬운 해결책이 있습니다.
최상의 전략:
re.sub("\w+",repl,sentence)단어 검색.- "callable"은 호출할 수 있습니다.딕트 룩업을 수행하는 기능을 사용했는데 딕트에는 검색하고 대체할 단어가 포함되어 있습니다.
- 해결책입니다().
replace4예: 아래 코드).
차선책 전략:
- 그 아이디어는 문장을 단어로 나누는 것입니다.
re.split나중에 문장을 재구성하기 위해 구분자를 보존하는 동안.그런 다음 간단한 딕트 조회를 통해 교체를 수행합니다. - (: (함수 참조)
replace3예: 아래 코드).
예제 기능의 타이밍:
replace1: 0.62 sentences/s
replace2: 7.43 sentences/s
replace3: 48498.03 sentences/s
replace4: 61374.97 sentences/s (...and 240,000/s with PyPy)
... 및 코드:
#! /bin/env python3
# -*- coding: utf-8
import time, random, re
def replace1( sentences ):
for n, sentence in enumerate( sentences ):
for search, repl in patterns:
sentence = re.sub( "\\b"+search+"\\b", repl, sentence )
def replace2( sentences ):
for n, sentence in enumerate( sentences ):
for search, repl in patterns_comp:
sentence = re.sub( search, repl, sentence )
def replace3( sentences ):
pd = patterns_dict.get
for n, sentence in enumerate( sentences ):
#~ print( n, sentence )
# Split the sentence on non-word characters.
# Note: () in split patterns ensure the non-word characters ARE kept
# and returned in the result list, so we don't mangle the sentence.
# If ALL separators are spaces, use string.split instead or something.
# Example:
#~ >>> re.split(r"([^\w]+)", "ab céé? . d2eéf")
#~ ['ab', ' ', 'céé', '? . ', 'd2eéf']
words = re.split(r"([^\w]+)", sentence)
# and... done.
sentence = "".join( pd(w,w) for w in words )
#~ print( n, sentence )
def replace4( sentences ):
pd = patterns_dict.get
def repl(m):
w = m.group()
return pd(w,w)
for n, sentence in enumerate( sentences ):
sentence = re.sub(r"\w+", repl, sentence)
# Build test set
test_words = [ ("word%d" % _) for _ in range(50000) ]
test_sentences = [ " ".join( random.sample( test_words, 10 )) for _ in range(1000) ]
# Create search and replace patterns
patterns = [ (("word%d" % _), ("repl%d" % _)) for _ in range(20000) ]
patterns_dict = dict( patterns )
patterns_comp = [ (re.compile("\\b"+search+"\\b"), repl) for search, repl in patterns ]
def test( func, num ):
t = time.time()
func( test_sentences[:num] )
print( "%30s: %.02f sentences/s" % (func.__name__, num/(time.time()-t)))
print( "Sentences", len(test_sentences) )
print( "Words ", len(test_words) )
test( replace1, 1 )
test( replace2, 10 )
test( replace3, 1000 )
test( replace4, 1000 )
EDIT: 소문자로 된 문장 목록을 전달하고 repl을 편집하는지 확인할 때 소문자를 무시할 수도 있습니다.
def replace4( sentences ):
pd = patterns_dict.get
def repl(m):
w = m.group()
return pd(w.lower(),w)
아마도 Python은 여기서 올바른 도구가 아닐 것입니다.다음은 유닉스 툴체인과 함께 제공되는 것입니다.
sed G file |
tr ' ' '\n' |
grep -vf blacklist |
awk -v RS= -v OFS=' ' '{$1=$1}1'
단어 경계가 추가된 블랙리스트 파일이 사전 처리된 것으로 가정합니다.이 단계는 파일을 두 줄 간격으로 변환하고, 각 문장을 한 줄에 하나의 단어로 분할하고, 파일에서 블랙리스트 단어를 대량으로 삭제하고, 줄을 다시 병합하는 것입니다.
이 작업은 최소한 몇 배 더 빨리 실행되어야 합니다.
단어에서 블랙리스트 파일을 사전 처리하는 경우(한 줄에 한 단어씩)
sed 's/.*/\\b&\\b/' words > blacklist
이거 어때:
#!/usr/bin/env python3
from __future__ import unicode_literals, print_function
import re
import time
import io
def replace_sentences_1(sentences, banned_words):
# faster on CPython, but does not use \b as the word separator
# so result is slightly different than replace_sentences_2()
def filter_sentence(sentence):
words = WORD_SPLITTER.split(sentence)
words_iter = iter(words)
for word in words_iter:
norm_word = word.lower()
if norm_word not in banned_words:
yield word
yield next(words_iter) # yield the word separator
WORD_SPLITTER = re.compile(r'(\W+)')
banned_words = set(banned_words)
for sentence in sentences:
yield ''.join(filter_sentence(sentence))
def replace_sentences_2(sentences, banned_words):
# slower on CPython, uses \b as separator
def filter_sentence(sentence):
boundaries = WORD_BOUNDARY.finditer(sentence)
current_boundary = 0
while True:
last_word_boundary, current_boundary = current_boundary, next(boundaries).start()
yield sentence[last_word_boundary:current_boundary] # yield the separators
last_word_boundary, current_boundary = current_boundary, next(boundaries).start()
word = sentence[last_word_boundary:current_boundary]
norm_word = word.lower()
if norm_word not in banned_words:
yield word
WORD_BOUNDARY = re.compile(r'\b')
banned_words = set(banned_words)
for sentence in sentences:
yield ''.join(filter_sentence(sentence))
corpus = io.open('corpus2.txt').read()
banned_words = [l.lower() for l in open('banned_words.txt').read().splitlines()]
sentences = corpus.split('. ')
output = io.open('output.txt', 'wb')
print('number of sentences:', len(sentences))
start = time.time()
for sentence in replace_sentences_1(sentences, banned_words):
output.write(sentence.encode('utf-8'))
output.write(b' .')
print('time:', time.time() - start)
이러한 솔루션은 단어 경계에서 분할되고 집합에서 각 단어를 찾습니다.은 realternates ( solution)보다. 왜냐하면 이 솔루션들은 "sub of word alternates" (Liteyes's sub of word alternates)이기 입니다.O(n)은 서은 n 다로 입한 크기니로 입니다.amortized O(1)regex 대체를 사용하는 동안 regex 엔진은 단어 경계가 아닌 모든 문자에서 단어 일치를 확인해야 합니다.내 솔루션은 원본 텍스트에 사용된 공백을 보존하기 위해 특별히 주의를 기울이지만(즉, 공백을 압축하지 않고 탭, 줄 바꿈 및 기타 공백 문자를 보존하지 않음), 신경 쓰지 않기로 결정한 경우에는 출력에서 해당 공백을 제거하는 것이 매우 간단합니다.
말뭉치 검사를 했습니다.txt는 구텐베르크 프로젝트에서 다운로드한 여러 eBook과 금지된_words의 연결입니다.txt는 Ubuntu의 단어 목록(/usr/share/dict/american-english)에서 무작위로 선택한 20000 단어입니다.862462 문장을 처리하는 데 약 30초가 걸립니다(그리고 PyPy에서는 그 절반).저는 문장을 " "로 구분된 모든 것으로 정의했습니다.
$ # replace_sentences_1()
$ python3 filter_words.py
number of sentences: 862462
time: 24.46173644065857
$ pypy filter_words.py
number of sentences: 862462
time: 15.9370770454
$ # replace_sentences_2()
$ python3 filter_words.py
number of sentences: 862462
time: 40.2742919921875
$ pypy filter_words.py
number of sentences: 862462
time: 13.1190629005
PyPy는 특히 두 번째 접근 방식에서 더 많은 이익을 얻는 반면, Cython은 첫 번째 접근 방식에서 더 나은 결과를 얻었습니다.위의 코드는 Python 2와 3 모두에서 작동해야 합니다.
실용적 접근법
아래 설명된 솔루션은 많은 메모리를 사용하여 모든 텍스트를 동일한 문자열에 저장하고 복잡성 수준을 줄입니다.RAM이 문제라면 사용하기 전에 두 번 생각해 보세요.
와 함께join/split알고리즘 속도를 높이는 루프를 전혀 피할 수 있는 요령.
merged_sentences = ' * '.join(sentences)
| 문 " 는또정" 식규문 문::regex = re.compile(r'\b({})\b'.format('|'.join(words)), re.I) # re.I is a case insensitive flag
clean_sentences = re.sub(regex, "", merged_sentences).split(' * ')
성능
"".join복잡도는 O(n)입니다.이것은 꽤 직관적이지만 어쨌든 출처에서 인용한 단축형이 있습니다.
for (i = 0; i < seqlen; i++) {
[...]
sz += PyUnicode_GET_LENGTH(item);
따서이 함께와와 함께 합니다.join/splitO(단어) + 2*O(문장)는 여전히 선형 복잡도 대 초기 접근 방식의 2*O(N2)입니다.
b.t.w. 멀티스레딩을 사용하지 마십시오. GIL은 각 작업을 차단합니다. 이는 작업이 CPU 바인딩되어 있기 때문에 GIL을 해제할 기회가 없기 때문입니다. 그러나 각 스레드가 틱을 동시에 전송하여 추가적인 노력을 유발하고 작업을 무한대로 이끌 수 있습니다.
모든 문장을 하나의 문서로 연결합니다.모든 "나쁜" 단어를 찾으려면 Aho-Corasick 알고리즘의 구현(여기 하나)을 사용합니다.파일을 이동하여 각 잘못된 단어를 바꾸고, 뒤에 오는 발견된 단어의 오프셋을 업데이트합니다.
언급URL : https://stackoverflow.com/questions/42742810/speed-up-millions-of-regex-replacements-in-python-3
'programing' 카테고리의 다른 글
| Python에서 두 목록이 순환적으로 동일한지 확인하는 방법 (0) | 2023.07.19 |
|---|---|
| 부분 문자열 형식 지정 (0) | 2023.07.19 |
| Python 생성기 패턴에 해당하는 C++ (0) | 2023.07.19 |
| 그리드 보기 정렬:방향 정렬 항상 오름차순 (0) | 2023.07.19 |
| 파이썬의 다른 함수 안에서 호출자 함수 이름을 가져오는 중? (0) | 2023.07.19 |