有效地在字符串中进行多次替换

Question

人们已经解决了如何基于字典对字符串进行多次替换的问题（例如，参见）。似乎有一组基于选项string.replace，一组基于正则表达式的选项，还有更多选项。

但是我对取决于字典大小的不同方法的效率感兴趣，我发现这具有非常重要的影响。

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

明确地说，这个问题 不是 关于如何进行这些替换，而是关于哪种方法在哪些条件下以及哪些警告适用的情况下更有效。特别是，当有很多（>
100k）字符串很长（10-20k个字符）并且字典很大（> 80k对）时，我正在寻找最实用的方法。在这些情况下，基于正则表达式的首选方法执行效果非常差。

Answer 1

如前所述，有不同的方法，每种方法都有不同的优势。我正在使用三种不同的情况进行比较。

1. 短字典（847个替换对）
2. 中型词典（2528对）
3. 长字典（80430对）

对于字典1和2（较短的字典），我将每个方法循环重复50次，以获得更一致的时间安排
。如果文件越长，则一次通过一个文档所花费的时间就越长（可悲）。我使用在线服务tio和Python
3.8测试了1和2 。长长的一个在我的笔记本电脑上使用Python 3.6进行了测试。方法之间的相对性能是相关的，因此次要细节并不重要。

我的字符串介于28k和29k之间。

所有时间以秒为单位。

更新：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. 1.63
2. 5.03
3. 7.7

更换

此方法仅适用string.replace于循环。（稍后我讨论与此有关的问题。）

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

此解决方案使用提出了一个变体reduce，该变体可迭代地应用Lambda表达式。通过官方文档中的示例可以最好地理解这一点。表达方式

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()]

执行时间为（括号 结果 为reduce和 assigning expression的 变体）：

1. 1.37（1.39）（1.50）
2. 4.10（4.12）（4.07）
3. 1.9（1.8）（机器上没有Python 3.8）

递归Lambda

该建议涉及使用递归Lambda。

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

执行时间为：

1. 0.07
2. RecursionError
3. RecursionError

请参阅上面的更新：Flashtext 比其他替代方法快得多。

从执行时间可以看出，递归方法显然是最快的，但仅适用于小型词典。这是不建议增加递归深度多在Python，所以这种方式完全抛弃更长的字典。

正则表达式可以更好地控制您的替换。例如，您可以\b在元素之前或之后使用来确保目标子字符串的该侧没有单词字符（以防止将{‘a’：‘1’}应用于’apple’）。代价是，对于较长的词典来说，性能会急剧下降，几乎是其他选项的四倍。

赋值表达式 ， reduce 和简单地循环 替换
提供了类似的性能（赋值表达式无法使用更长的字典进行测试）。考虑到可读性，这string.replace似乎是最佳选择。与正则表达式相比，这样做的问题是替换是顺序发生的，而不是单步执行。因此{‘a’：’b’，’b’：’c’}为字符串’a’返回’c’。现在已经在Python中对字典进行了排序（但是您可能希望使用OrderedDict保持），因此您可以仔细设置替换顺序以避免出现问题。当然，对于80k替换，您不能依靠它。

我目前正在使用带有替换的循环，并进行了一些预处理以最大程度地减少麻烦。我在标点符号的两侧都添加了空格（也在字典中包含标点符号的项目中）。然后，我可以搜索用空格包围的子字符串，并用空格插入替换项。当您的目标是多个单词时，这也适用：

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

通过使用replace和正则表达式，我得到string = ' This is : an island '了replace循环

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

返回' This is not : a museum '预期的结果。请注意，“ This”和“ island”中的“
is”是单独保留的。尽管我不需要此步骤，但是可以使用正则表达式来修复标点符号。