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

Question

我有一本很大的字典，里面储存了大量的英语句子和它们的西班牙语翻译。当给出一个随机的英语句子时，我打算使用Python的fuzzyfuzzy库在字典中查找最接近的匹配项。我的代码：

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

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

Answer 1

可能有更好的解决方案，但在我的脑海中，我可以想到分区

您可以创建26个不同的字典，每个字典代表一个英语字母表。然后你可以加载所有这些字典和所有以字母表开头的键。 例如，adict、bdict。。。zdict等。 所以hdict将包含以h开头的键的键值。比如key=“你好吗？”

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

Answer 2

提高绩效的途径

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

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

2. 即使在使用python时，Levenshtein FuzzyWzzy在很多地方也没有得到真正的优化。您应该用RapidFuzz来替换它，它用相同的接口实现相同的算法，但大部分是用C++实现的，并且附带了一些额外的算法改进，使它更快。p>

3. 默认情况下，内部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    |