Pandas Groupby 但在 % 匹配范围内而不是完全匹配

Question

我有一个 400k 行数据框，其中有一列字符串，如果它们相似于 90% 以内，我想对它们进行分组，而不仅仅是由于拼写错误等而完全匹配。我已经尝试过 Rapidfuzz，但仍在努力寻找不需要很长时间的解决方案。

到目前为止，我只使用了标准的 Pandas.groupby，但仍然有一些非常接近，但没有分组，因为它们不精确。我还尝试过针对所有其他值运行每个值的循环，但这需要几个小时。我使用模糊 QRatio 和 SequenceMatcher 来查找匹配率，但无法将其扩展到数十万行。

示例数据：

data = pd.DataFrame(data=["Apple", "Apple", "apple", "appel", "aple", "Orange", "Banana"],columns=["Fruits"], dtype="str")

期望的结果： 至于“类别”的名称，无论是最常用的值还是它的第一个实例都可以。

水果	发生
苹果	5
橙色	1
香蕉	1

提前致谢！

Answer 1

您可以使用编辑距离：编辑距离是两个字符串之间相似性的度量，它考虑了将一个字符串转换为另一个字符串所需的插入、删除和替换操作的数量。 正如这里所解释的 https://www.geeksforgeeks.org/introduction-to-levenshtein-distance/

建立在 levenshteinRecursive 函数的基础上，专门针对您的情况：

import pandas as pd
from collections import defaultdict
data = pd.DataFrame(data=["Apple", "Apple", "apple", "appel", "aple", "Orange", "Banana"],columns=["Fruits"], dtype="str")

def levenshteinRecursive(str1, str2, m, n):
      # str1 is empty
    if m == 0:
        return n
    # str2 is empty
    if n == 0:
        return m
    if str1[m - 1] == str2[n - 1]:
        return levenshteinRecursive(str1, str2, m - 1, n - 1)
    return 1 + min(
          # Insert     
        levenshteinRecursive(str1, str2, m, n - 1),
        min(
              # Remove
            levenshteinRecursive(str1, str2, m - 1, n),
          # Replace
            levenshteinRecursive(str1, str2, m - 1, n - 1))
    )

def group_similar_strings(data, threshold=4):
    categories = {}

    for index, row in data.iterrows():
        matched = False

        for category in categories:
            if levenshteinRecursive(row["Fruits"], category, len(row["Fruits"]), len(category)) <= threshold:
                categories[category].append(row["Fruits"])
                matched = True
                break

        if not matched:
            categories[row["Fruits"]] = [row["Fruits"]]

    occurrences = {category: len(values) for category, values in categories.items()}
    
    return occurrences

result = group_similar_strings(data)
result = pd.DataFrame.from_dict(result, orient="index", columns=["Occurs"]).reset_index().rename(columns={"index": "Fruit"})

print(result)