代码之家 › 专栏 › 技术社区 › Dalvtor

Python-高效地比较字符串

fuzzywuzzy algorithm python

Dalvtor · 技术社区 · 6 年前

我有一个大约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)

我怎样才能提高绩效?

1 回复 | 直到 6 年前

tobias_k 6 年前

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

相反,你可以试着从你的单词中提取一些“特征”,并据此对它们进行分组。我的第一个想法是用 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 首先,就像 and 或者把它们和周围的单词放在一起。这可能仍然会产生一些误报,例如,使用像 polo 或 collection 这可能会出现在几个不同的品牌,但我认为同样的情况下使用 fuzzywuzzy

r.ook jpp 6 年前

尝试使用列表理解代替,它比 list.append()

with open('words.csv', encoding='utf-8') as csvfile:
    words = [row[0] for row in csv.reader(csvfile)]

    possible_matches = [(words[i], words[j]) 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]

    print(possible_matches)

不幸的是,用这种方法你不能 print(i) 在每个迭代中,但是假设您只需要 印刷品(一) 对于调试来说,它不会影响您的最终结果。

将循环转换为列表理解非常简单,考虑一下您有这样一个循环:

for i in iterable_1:
    lst.append(something)

列表理解变成:

lst = [something for i in iterable_1]

iterable_1:
    iterable_2:
        ...
        some_condition:
            lst.append(something)

# becomes

lst = [something <iterable_1> <iterable_2> ... <some_condition>]

# Or if you have an else clause:

iterable_1:
    ...
    if some_condition:
        lst.append(something)
    else:
        lst.append(something_else)

lst = [something if some_condition else something_else <iterable_1> <iterable_2> ...]