Эффективно выполнять множество множественных замен в строке

Question

Эффективно выполнять множество множественных замен в строке

Раньше люди обращались к вопросу о том, как сделать несколько замен в строке на основе словаря (см., Например). Кажется, есть группа вариантов, основанная наstring.replace и группа опций, основанных на регулярных выражениях, и еще пара опций.

Но меня интересует эффективность различных методов в зависимости от размера словаря, что, как я обнаружил, имеет очень важное значение.

my_subs = {'Hello world': 'apple', 'is': 'ship'}
string = 'Hello world! This is nice.'
new_string = my_efficient_method(string, my_subs)

Чтобы было ясно, этот вопрос не о том, как сделать эти замены, а о том, какой метод более эффективен в каких условиях и какие предостережения применяются. В частности, я ищу наиболее практичный подход, когда имеется много (>100 тыс.) Длинных строк (10-20 тыс. Символов), а словарь огромен (>80 тыс. Пар). В этих условиях предпочтительные методы, основанные на регулярных выражениях, работают очень плохо.

7

python text replace

Источник

user5346123 27 ноя '19 в 17:34

2 ответа

Решение

Скомпилировав таблицу замен в конечный автомат. Вы можете завершить замену в однофазном char с помощью сканирования char. А использование предварительно скомпилированного FSM повысит вашу производительность, если вы будете применять одну и ту же таблицу замещения ко многим разным строкам.

По сравнению с другими методами:

FSM похож на Trie: значения замены нелистовых узлов также предварительно вычисляются. Таким образом, вам не нужно будет возвращаться к Trie, чтобы сэкономить еще немного времени.
FSM похож на предварительно скомпилированное регулярное выражение: поскольку регулярное выражение — это просто дружественная форма FSM.
FSM также похож на метод: поиск подстрок с использованием алгоритма KMP на самом деле является FSM. Мы просто объединяем несколько FSM в один.

Временная сложность равно O(mk²) , где m — записи таблицы замены, а k — длина одного правила замены. Временная сложность равно O(n+n'), где n - длина ввода, n' - длина вывода.

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

      import typing

mismatch = ''

ConvertTree = typing.Dict[str, typing.Tuple[str, 'ConvertTree']]
def compile(rulePairs:typing.Iterable[typing.Tuple[str, str]]) -> ConvertTree:
    # Build Trie
    root: ConvertTree = {}
    for src, dst in rulePairs:
        current = root
        for ch in src:
            if ch not in current:
                node: ConvertTree = {}
                node[mismatch] = None
                current[ch] = ('', node)
            current = current[ch][1]
        if not current.get(mismatch, None):
            current[mismatch] = (dst, root)
        else:
            old_dst = current[mismatch][0]
            if dst != old_dst:
                raise KeyError(f"Found conflict rules:\n  * {src} -> {old_dst}\n  * {src} -> {dst}")

    # Fill non-leaf nodes
    node_with_suffix: typing.List[typing.Tuple[ConvertTree, str, str]] = [(root, '', '')]
    for node, output, suffix in node_with_suffix:
        node_output, node_suffix = output, suffix;
        if node.get(mismatch, None):
            leaf = node[mismatch]
            node_output, node_suffix = leaf[0], ''
        for key in node:
            if key == mismatch: continue
            val = node[key]
            next_node = val[1]
            if next_node is root: continue
            if len(next_node) == 1:
                node[key] = next_node[mismatch]
            else:
                node_with_suffix.append((next_node, node_output, node_suffix + key))
        if not node_suffix: continue
        node_next = root
        for ch in node_suffix:
            while node_output != '' and ch not in node_next and node_next is not root:
                ref_output, node_next = node_next[mismatch]
                node_output += ref_output
            if not node_output:
                node_output += ch
            elif ch in node_next:
                ref_output, node_next = node_next[ch]
                node_output += ref_output
                break
            elif node_next is root:
                node_output += ch
                break
        node[mismatch] = (node_output, node_next)

    return root

def replace(input_text: str, root: ConvertTree) -> str:
    current = root
    output_arr = []
    for ch in input_text:
        while True:
            try:
                output, current = current[ch]
                output_arr.append(output)
            except:
                if current is root:
                    output_arr.append(ch)
                else:
                    output, current = current[mismatch]
                    output_arr.append(output)
                    continue
            break
    while current is not root:
        output, current = current['']
        output_arr.append(output)
    return ''.join(output_arr)

my_subs = [('Hello world', 'apple'), ('is', 'ship')]
string = 'Hello world! This is nice.'
new_string = replace(string, compile(my_subs))
print(new_string) # "apple! Thship ship nice."

Пожалуйста, оставьте комментарий, если вы обнаружили какие-либо ошибки в коде. Я постараюсь исправить их, если они есть.

Я использовал тот же алгоритм в своем новом ридере, который использует замену строк для преобразования между китайским упрощенным и традиционным вариантами. Соответствующий код Python также можно найти в моем репозитории GitHub (китайский).

1

Источник

user2045384 12 апр '22 в 07:35

Другие вопросы по тегам python text replace

user5346123 27 ноя '19 в 17:34 2019-11-27 17:34 · Accepted Answer · 2019-11-27 17:34

Как указывалось ранее, существуют разные подходы, каждый из которых имеет свои преимущества. Для сравнения я использую три разные ситуации.

Краткий словарь (847 пар замен)
Средний словарь (2528 пар)
Длинный словарь (80430 пар)

Для словарей 1 и 2 (более коротких) я повторяю каждый метод 50 раз в цикле, чтобы получить более согласованный выбор времени. С более длинным один проход для одного документа занимает достаточно много времени (к сожалению). Я тестировал 1 и 2, используя онлайн- сервис tio с Python 3.8. Длинный тестировался на моем ноутбуке с Python 3.6. Важна только относительная производительность между методами, поэтому мелкие детали не важны.

Моя строка составляет от 28 до 29 тысяч символов.

Время указано в секундах.

ОБНОВЛЕНИЕ: Flashtext

Коллега нашел Flashtext, библиотеку Python, которая специализируется именно на этом. Это позволяет искать по запросу, а также применять замены. Это примерно на два порядка быстрее, чем другие альтернативы. В эксперименте 3 мое текущее лучшее время составляло 1,8 секунды. Flashtext занимает 0,015 секунды.

Регулярные выражения

Есть много вариантов, но лучшие, как правило, очень похожи на эти:

import re
rep = dict((re.escape(k), v) for k, v in my_dict.items())
pattern = re.compile("|".join(rep.keys()))
new_string = pattern.sub(lambda m: rep[re.escape(m.group(0))], string)

Сроки исполнения были:

1,63
5,03
7,7

Заменить

Этот метод просто применяется string.replaceв петле. (Позже я расскажу о проблемах с этим.)

for original, replacement in self.my_dict.items():
    string = string.replace(original, replacement)

Это решение предлагает вариант с использованиемreduce, который итеративно применяет лямбда-выражение. Лучше всего это понять на примере из официальной документации. Выражение

reduce(lambda x, y: x+y, [1, 2, 3, 4, 5])

равно ((((1+2)+3)+4)+5)

import functools
new_string = functools.reduce(lambda a, k: a.replace(*k), 
                              my_dict.items(), string)

Python 3.8 позволяет использовать выражения присваивания, как в этом методе. По своей сути это также зависит отstring.replace.

[string := string.replace(f' {a} ', f' {b} ') for a, b in my_dict.items()]

Время выполнения было (в скобках результаты для вариантов выражения сокращения и присваивания):

1,37 (1,39) (1,50)
4,10 (4,12) (4,07)
1.9 (1.8) (нет Python 3.8 в машине)

Рекурсивная лямбда

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

mrep = lambda s, d: s if not d else mrep(s.replace(*d.popitem()), d)
new_string = mrep(string, my_dict)

Сроки исполнения были:

0,07
RecursionError
RecursionError

Практические замечания

См. Обновление выше: Flashtext намного быстрее, чем другие альтернативы.

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

Регулярные выражения обеспечивают больший контроль над вашими заменами. Например, вы можете использовать\bдо или после элемента, чтобы гарантировать, что на этой стороне целевой подстроки нет словесных символов (чтобы предотвратить применение {'a': '1'} к 'apple'). Цена заключается в том, что производительность для более длинных словарей резко падает, что почти в четыре раза больше, чем для других вариантов.

Выражения присваивания, сокращение и простая циклическая замена предлагают аналогичную производительность (выражения присваивания не могут быть протестированы с более длинным словарем). Принимая во внимание удобочитаемость,string.replaceвроде как лучший вариант. Проблема с этим, по сравнению с регулярными выражениями, заключается в том, что замены происходят последовательно, а не за один проход. Итак, {'a': 'b', 'b': 'c'} возвращает 'c' для строки 'a'. Словари теперь упорядочены в Python (но вы, возможно, захотите сохранить с помощью OrderedDict), поэтому вы можете тщательно установить порядок замен, чтобы избежать проблем. Конечно, при 80к замен на это рассчитывать нельзя.

В настоящее время я использую цикл с заменой и делаю некоторую предварительную обработку, чтобы минимизировать проблемы. Я добавляю пробелы с обеих сторон знаков препинания (также в словаре для элементов, содержащих знаки пунктуации). Затем я могу искать подстроки, окруженные пробелами, а также вставлять замены с пробелами. Это также работает, когда ваши цели - несколько слов:

string = 'This is: an island'
my_dict = {'is': 'is not', 'an island': 'a museum'}

Используя замену и регулярные выражения, я получаю string = ' This is : an island ' так что мой цикл замены

for original, replacement in self.my_dict.items():
    string = string.replace(f' {original} ', f' {replacement} ')

возвращается ' This is not : a museum 'как предполагалось. Обратите внимание, что "is" в "This" и "island" остались без изменений. Для исправления знаков препинания можно использовать регулярные выражения, хотя этот шаг мне не нужен.