python - 在 Python 中进行字符串匹配时，有没有办法提高匹配性能？

Question

我有一个非常大的字典，里面存储了大量的英语句子和它们的西类牙语翻译。当给定一个随机的英文句子时，我打算使用 Python 的 Fuzzywuzzy 库在字典中找到最接近的匹配项。我的代码:

from fuzzywuzzy import process
sentencePairs = {'How are you?':'¿Cómo estás?', 'Good morning!':'¡Buenos días!'}
query= 'How old are you?'
match = process.extractOne(query, sentencePairs.keys())[0]
print(match, sentencePairs[match], sep='\n')

在现实生活场景中， sentencePairs字典会非常大，至少存储一百万个项目。所以即使安装了python-Levenshtein来提供加速，用fuzzywuzzy也需要很长时间才能得到结果。
那么有没有更好的方法来实现更好的性能呢？我的目标是在几秒钟内甚至实时获得结果。

Answer 1

提高性能的方法
使用 Levenshtein 距离的模糊匹配永远不会超快，但您可以优化代码中的一些内容:

将字符串和列表传递给 process.extractOne 时，它​​将通过小写、删除非字母数字字符和修剪空格来预处理这些字符串。由于您每次都重复使用相同的 English:Spanish 映射，因此您应该提前一次进行此预处理。

即使使用 python-Levenshtein FuzzyWuzzy 在很多地方也没有真正优化。您应该将其替换为 RapidFuzz它使用类似的接口(interface)实现相同的算法，但主要是用 C++ 实现的，并带有一些额外的算法改进，使其速度更快。

内部process.extractOne正在使用 fuzz.WRatio默认情况下比较字符串。这是多种字符串匹配算法的组合。因此，通过传递例如选择更快的算法scorer=fuzz.ratio process.extractOne 提高了性能。但是请记住，这会改变比较字符串的方式，因此根据您的数据，您可能不想这样做。

使用 1 和 2 的实现

from rapidfuzz import process, utils
# english sentences are already lower cased
# and without special characters like question marks
sentencePairs = {'how are you':'¿Cómo estás?', 'good morning':'¡Buenos días!'}
query= 'How old are you?'
match, _ = process.extractOne(
   utils.default_process(query),
   sentencePairs.keys(),
   processor=None)
print(match, sentencePairs[match], sep='\n')

利用1、2、3的实现

from rapidfuzz import process, utils, fuzz
# english sentences are already lower cased
# and without special characters like question marks
sentencePairs = {'how are you':'¿Cómo estás?', 'good morning':'¡Buenos días!'}
query= 'How old are you?'
match, _ = process.extractOne(
   utils.default_process(query),
   sentencePairs.keys(),
   processor=None,
   scorer=fuzz.ratio)
print(match, sentencePairs[match], sep='\n')

基准
为了提供一些时间比较，我生成了一百万个句子:

import string
import random
random.seed(18)
sentencePairs = {
    ''.join(random.choice(string.ascii_lowercase + string.digits)
       for _ in range(15)
    ): "spanish text"
    for s in range(1000000)
}
query= 'How old are you?'

下表显示了不同解决方案在我的计算机上需要多长时间

| Implementation                           | Runtime        |
|------------------------------------------|----------------|
| Your current implementation              | 18.98 seconds  |
| Implementation making use of 1 and 2     | 1.4 seconds    |
| Implementation making use of 1, 2 and 3  | 0.4 seconds    |