在 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

可能有更好的解决方案，但我首先想到的是分区。

您可以创建 26 部不同的词典，每部代表一个英文字母表。然后你可以用所有以相应字母开头的键加载所有这些字典。例如。 adict，bdict ... zdict 等。所以。 hdict 将包含以 h 开头的 Key 的 Key 值。喜欢键=“你好吗？”

这样，您只需要查询与起始字母匹配的字典。

Answer 2

提高性能的方法

使用 Levenshtein 距离的模糊匹配永远不会超快，但您的代码中有几处可以优化：

将字符串和列表传递给 process.extractOne 时，它将通过将这些字符串小写化、删除非字母数字字符和修剪空格来预处理这些字符串。由于您每次都重复使用相同的 English:Spanish 映射，因此您应该提前进行一次预处理。
即使使用 python-Levenshtein FuzzyWuzzy 在很多地方都没有真正优化。您应该将其替换为 RapidFuzz，它实现了具有相似接口的相同算法，但主要是在 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?'

以下table显示不同的解决方案在我的电脑上需要多长时间

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

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

Is there a way to boost matching performance when doing string matching in Python?

python

performance

fuzzywuzzy

提高性能的方法

利用 1 和 2 的实现

利用 1、2 和 3 的实现

基准