时间戳

首页 > 解决方案 > 有效地在字符串中进行多次替换

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

问题描述

人们之前已经讨论过如何根据字典在字符串中进行多次替换（例如，参见 参考资料）。似乎有一组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对）时，我正在寻找最实用的方法。在这些情况下，基于正则表达式的首选方法性能很差。

标签： pythontextreplace

解决方案

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

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

对于字典 1 和 2（较短的），我在循环中重复每个方法 50 次，以获得更一致的时间。对于一个较长的文件，一个文件的单次传递需要足够长的时间（可悲）。我使用Python 3.8的在线服务 tio测试了 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 和assignment 表达式变体）：

  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'}

使用替换和正则表达式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 '按预期返回。请注意，“This”和“island”中的“is”被单独留下。正则表达式可用于修复标点符号，尽管我不需要这一步。

推荐阅读