Блог

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

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

Существует существенная разница, когда вы выполняете подстановку строк слово за словом / символ за символом, однако в этом случае это не сработает, если не используется какая-либо форма сопоставления строк.

Вот мои предыдущие попытки сделать это.

 import re 

def standard_for_loop(string, replacements):
    # case sensitive for loop
    for key, value in replacements.items():
        # would not work unless case specific
        string = string.replace(key, value)
        
    return string 


def regex_loop(string, replacements):
    #case insensitive regex substitution in for
    for key, value in replacements.items():
        string = re.sub(key, value, string, re.IGNORECASE)
        
    return string
    

def regex_multiple(string, replacements):
    # case insensitive regex substitution using lambda 
    pattern = re.compile("({})".format("|".join(replacements.keys())), re.IGNORECASE)
    return pattern.sub(lambda m: replacements[m.string.lower()[m.start():m.end()]], string)
    

    
def case_insensitive_for_loop(string, replacements):
    def find_next(string, pattern, sub):
        if pattern.lower() in string.lower():
            
            match = string.lower().index(pattern.lower())
            end = int(match   len(pattern))
            
            new_string = string[end:]
            
            # yield a replaced substring of original string
            yield string[:match]   sub
            yield from find_next(new_string, pattern, sub)
            
    '''
    # this is what I'm unsure about. How to negate need for 
    # for loop here and how to fix the append issue.
    # Currently the functionality works but it appends output 
    # replacement to the result. I know the " =" is the 
    # cause of the problem, but I'm not sure how to fix this. 
    '''
    result = ''
    for k, v in replacements.items():
        for output in find_next(string, k, v):
            result  = output
    return result
 

Есть две проблемы, по моему опыту, regex_multiple наиболее точная, но для ее решения требуется довольно много времени. Следующим наиболее точным является case_sensitive_for_loop , но я не знаю, как преодолеть проблему замены и добавления.

Например, он заменит документ:

 # for a sample document 

doc = """Lorem ipsum dolor sit amet, consectetur adipiscing elit. Phasellus accumsan pulvinar massa ut pulvinar. Cras blandit quam non dictum tempus. Maecenas id posuere nibh. Nullam sit amet pharetra neque. Etiam nec imperdiet tellus. Nulla facilisi. Proin sit amet massa aliquam, pulvinar justo in, suscipit purus. Fusce in tempus orci. In consectetur, ipsum nec volutpat dapibus, felis magna scelerisque enim, et rutrum nunc ligula eget augue. Phasellus aliquam feugiat venenatis. Sed lobortis pharetra ipsum ut venenatis.

Nullam ut accumsan orci. Vivamus faucibus augue in facilisis facilisis. Donec ut scelerisque ipsum. Ut mollis elit nibh, ut vulputate eros ultrices ac. Nunc ac urna sed libero imperdiet maximus non sed dui. Morbi ornare eu eros eget pharetra. Vivamus vestibulum nisi eu eros pulvinar aliquet.

Maecenas at justo bibendum, viverra urna nec, pellentesque orci. Cras ut molestie sem. Proin in tincidunt ex. Aliquam euismod id ligula a bibendum. Morbi at diam euismod, auctor ex non, venenatis ante. Proin convallis ex eu semper posuere. Etiam sed tincidunt massa. Vivamus aliquam mollis massa, nec lacinia est dictum vitae. In varius convallis pulvinar. Pellentesque aliquet pulvinar nibh vel dictum"""

#replacement strings where k is the substring to be searched and v is the value to be replaced with
repl = { 'venenatis ante':'', 
'ipsum nec volutpat dapibus' : '',
'ipsum vulputate accumsan' : '',
'dolor sit amet':'', 
'vivamus aliquam mollis massa':''
}
 

с :

 Lorem ipsum dolor sit amet, consectetur adipiscing elit. Phasellus accumsan pulvinar massa ut pulvinar. Cras blandit quam non dictum tempus. Maecenas id posuere nibh. Nullam sit amet pharetra neque. Etiam nec imperdiet tellus. Nulla facilisi. Proin sit amet massa aliquam, pulvinar justo in, suscipit purus. Fusce in tempus orci. In consectetur, ipsum nec volutpat dapibus, felis magna scelerisque enim, et rutrum nunc ligula eget augue. Phasellus aliquam feugiat venenatis. Sed lobortis pharetra ipsum ut venenatis.

Nullam ut accumsan orci. Vivamus faucibus augue in facilisis facilisis. Donec ut scelerisque ipsum. Ut mollis elit nibh, ut vulputate eros ultrices ac. Nunc ac urna sed libero imperdiet maximus non sed dui. Morbi ornare eu eros eget pharetra. Vivamus vestibulum nisi eu eros pulvinar aliquet.

Maecenas at justo bibendum, viverra urna nec, pellentesque orci. Cras ut molestie sem. Proin in tincidunt ex. Aliquam euismod id ligula a bibendum. Morbi at diam euismod, auctor ex non, Lorem ipsum dolor sit amet, consectetur adipiscing elit. Phasellus accumsan pulvinar massa ut pulvinar. Cras blandit quam non dictum tempus. Maecenas id posuere nibh. Nullam sit amet pharetra neque. Etiam nec imperdiet tellus. Nulla facilisi. Proin sit amet massa aliquam, pulvinar justo in, suscipit purus. Fusce in tempus orci. In consectetur, Lorem ipsum Lorem ipsum dolor sit amet, consectetur adipiscing elit. Phasellus accumsan pulvinar massa ut pulvinar. Cras blandit quam non dictum tempus. Maecenas id posuere nibh. Nullam sit amet pharetra neque. Etiam nec imperdiet tellus. Nulla facilisi. Proin sit amet massa aliquam, pulvinar justo in, suscipit purus. Fusce in tempus orci. In consectetur, ipsum nec volutpat dapibus, felis magna scelerisque enim, et rutrum nunc ligula eget augue. Phasellus aliquam feugiat venenatis. Sed lobortis pharetra ipsum ut venenatis.

Nullam ut accumsan orci. Vivamus faucibus augue in facilisis facilisis. Donec ut scelerisque ipsum. Ut mollis elit nibh, ut vulputate eros ultrices ac. Nunc ac urna sed libero imperdiet maximus non sed dui. Morbi ornare eu eros eget pharetra. Vivamus vestibulum nisi eu eros pulvinar aliquet.

Maecenas at justo bibendum, viverra urna nec, pellentesque orci. Cras ut molestie sem. Proin in tincidunt ex. Aliquam euismod id ligula a bibendum. Morbi at diam euismod, auctor ex non, venenatis ante. Proin convallis ex eu semper posuere. Etiam sed tincidunt massa.
 

После их сравнения, самая standard_for_loop быстрая скорость составляет 4u секунд на цикл в 50 тысяч циклов. Второй по скорости- regex_loop 14 u секунд на цикл в 20-километровом цикле. Затем последовал case_sensitive_for_loop цикл, который занял 28,3 u секунд на цикл в 10 тыс. циклов. На regex_multiple удивление, лямбда-выражение в циклах 2k занимает больше всего времени-103 секунды.

Вот выходные данные python timeit для каждой функции.

Интересно, есть ли какие-либо алгоритмы сопоставления строк, которые я отрицал, чтобы посмотреть на это. Любые советы приветствуются

regex_multiple неэффективно, потому что если пересчитывать всю строку каждый раз, когда есть совпадение. Вы можете просто опустить соответствующую строку. Вот как:

 def regex_multiple(string, replacements):
    # case insensitive regex substitution using lambda 
    pattern = re.compile("({})".format("|".join(replacements.keys())), re.IGNORECASE)
    return pattern.sub(lambda m: replacements[m[0].lower()], string)
 

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

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

Наконец, если вы работаете только с документами ASCII. Вы можете добавить флаг re.ASCII в регулярное выражение. Это делает синтаксический анализ немного быстрее.