python - 使用 fuzzywuzzy 时如何更有效地比较字符串？

Question

我有一个包含约 20000 个单词的 CSV 文件，我想按相似性对这些单词进行分组。为了完成这样的任务，我正在使用神奇的 fuzzywuzzy包，它似乎工作得非常好，并且用一个小数据集(~100 字)实现了我正在寻找的东西

这些词实际上是品牌名称，这是我刚才提到的小型数据集的示例输出，其中我得到了按名称分组的相似品牌:

[
    ('asos-design', 'asos'), 
    ('m-and-s', 'm-and-s-collection'), 
    ('polo-ralph-lauren', 'ralph-lauren'), 
    ('hugo-boss', 'boss'), 
    ('yves-saint-laurent', 'saint-laurent')
]

现在，我的问题是，如果我为整个数据集运行我当前的代码，它真的很慢，而且我真的不知道如何提高性能，或者如果不使用 2 for循环。

这是我的代码。

import csv
from fuzzywuzzy import fuzz

THRESHOLD = 90

possible_matches = []


with open('words.csv', encoding='utf-8') as csvfile:
    words = []
    reader = csv.reader(csvfile)
    for row in reader:
        word, x, y, *rest = row
        words.append(word)

    for i in range(len(words)-1):
        for j in range(i+1, len(words)): 
            if fuzz.token_set_ratio(words[i], words[j]) >= THRESHOLD:
                possible_matches.append((words[i], words[j]))

        print(i)
    print(possible_matches)

如何提高性能？

Answer 1

对于 20,000 个单词或品牌，任何将每个单词与其他单词进行比较的方法(即具有二次复杂度 O(n²))可能都太慢了。对于 20,000 个，它可能仍然勉强可以接受，但对于任何更大的数据集，它很快就会崩溃。

相反，您可以尝试从您的单词中提取一些“特征”并相应地对它们进行分组。我的第一个想法是使用 stemmer , 但是因为你的话是名字而不是真正的的话，这将不起作用。我不知道您的示例数据的代表性如何，但您可以尝试根据由 - 分隔的组件对单词进行分组，然后获得唯一的非平凡组，您就完成了。

words = ['asos-design', 'asos', 'm-and-s', 'm-and-s-collection', 
         'polo-ralph-lauren', 'ralph-lauren', 'hugo-boss', 'boss',
         'yves-saint-laurent', 'saint-laurent']

from collections import defaultdict
parts = defaultdict(list)
for word in words:
    for part in word.split("-"):
        parts[part].append(word)

result = set(tuple(group) for group in parts.values() if len(group) > 1)

结果:

{('asos-design', 'asos'),
 ('hugo-boss', 'boss'),
 ('m-and-s', 'm-and-s-collection'),
 ('polo-ralph-lauren', 'ralph-lauren'),
 ('yves-saint-laurent', 'saint-laurent')}

您可能还想过滤掉一些 stop words首先，像 和 ，或者将它们与它们周围的词放在一起。这可能仍会产生一些误报，例如像 polo 或 collection 这样的词可能会出现在几个不同的品牌中，但我认为使用 fuzzywuzzy 或类似的词也是如此。可能需要对组进行一些后处理和手动过滤。