对大长度列表中的字符串进行模糊比较（考虑性能）-解网

问：

我有两个清单：

我从数据库中得到的第一个列表是各种公司的名称（可以用大写、小写或组合书写）

list_from_DB = [“锐步”， “马自达”， “巡逻”， “AsbEngland-bank”， “马自达INCC”， “HIGHWAY lcc”， “马自达”， “015 Amazon”， ......]

此列表中大约有 400,000 个项目。

第二个列表我通过解析用户的文本来获得（绝对可以有任何单词、数字、符号等）

list_from_user = ['ts'， '$243'， '马自达'， '军官'， '签名'， 'Date：07/20/2022'， 'Wilson'， 'Bank'， .......]

此列表中大约有 1000 个项目。

我需要做的是找到list_from_user中的哪些项目处于list_from_DB状态，并按最相似的顺序显示它们。如下图所示，两个列表中的项目可能相同，或者拼写不同。

输出

[“马自达”， “马自达”， “马自达INCC”， “AsbEngland-bank”]

我做什么：是的，我知道模糊字符匹配库，我使用 rapidfuzz。

res = []
for e in list_from_user:
    r = rapidfuzz.process.extract_iter(e, list_from_DB, processor=str.lower, scorer=rapidfuzz.fuzz.ratio, score_cutoff=95)
    res += r

是的，结果是有效的，但很长，大约 30 秒，因为循环必须执行 1000 * 400.000 = 400.000.000 次操作。

因此，问题如下：是否有可能在不枚举所有选项的情况下以其他方式解决这个问题？（我不反对枚举所有选项的方法，但如果它适合时间）

我的时间目标是最多 3 秒。

python 性能搜索模糊比较

import numpy as np
import rapidfuzz


def find_fuzzy(list_from_user, list_from_DB, score_cutoff: int):
    score_matrix = rapidfuzz.process.cdist(
        list_from_user,
        list_from_DB,
        processor=str.lower,
        scorer=rapidfuzz.fuzz.ratio,
        dtype=np.uint8,  # Output the score as uint8, which is faster.
        workers=-1,  # Use multithreading. -1 means use all cores.
        score_cutoff=score_cutoff,
    )

    results = []
    user_indices, db_indices = np.nonzero(score_matrix)
    for user_index_of_match, db_index_of_match in zip(user_indices, db_indices):
        results.append(
            {
                "user_index_of_match": user_index_of_match,
                "db_index_of_match": db_index_of_match,
                "user_item_of_match": list_from_user[user_index_of_match],
                "db_item_of_match": list_from_DB[db_index_of_match],
                "score_of_match": score_matrix[user_index_of_match, db_index_of_match],
            }
        )
    return results

在研究代码和各种可能性时，我有以下想法：是否有可能立即获得没有零的score_matrix？这是为了避免使用 np.nonzero（score_matrix）。这再次导致代码的最佳性能。只是我在文档中看到，有一个参数scorer_kwargs .也许它可以以某种方式使用？

0赞 ken 8/27/2023

@Paul 不幸的是，这是不可能的。被传递给记分器（在上面的代码中，函数），并且不会改变其本身的行为。更深入地看，这是 cdist 实现。矩阵是在函数的第一步分配的，因此没有办法绕过它。scorer_kwargsrapidfuzz.fuzz.ratiocdist

上一个：在 BigQuery 上使用 Double Metaphone 进行名称匹配

下一个：使用 fuzzywuzzy 库根据特定列查找 pyspark 数据帧的相似行

对大长度列表中的字符串进行模糊比较（考虑性能）

Fuzzy comparison of strings in lists of huge length (taking into account performance)

评论

评论