模糊匹配的组织

Question

我已经完成了 20,000 多个电影片名列表中的每个元素与其他元素的模糊匹配，return每对都有一个值：

from fuzzywuzzy import fuzz

titles = ['Scary Movie', 'Happy Movie', 'Sappy Movie', 'Crappy Movie']

print fuzz.ratio(titles[2],titles[3])
>>> 91 #/100 higher value denotes closer match 

for x in titles:
    for y in titles:
        fuzzed = fuzz.ratio(x,y)

    print "value for %r and %r is %r" % (x, y, fuzzed)

如何有效地组织这些数据？更具体地说，我怎样才能根据匹配值将匹配项组合在一起？

从嵌套循环中捕获 return 值，然后将它们与 x 和 y 打包成元组或列表显然是多余和混乱的。我尝试使用类实现，但我遗漏了一些东西。

Answer 1

也许您可以将 fuzzed 比率存储在以 (x,y) 元组为键的字典中，这样以后搜索每对的 ratio 会更容易。为此，您可以在 for 循环之外创建一个空字典，然后在 for 循环中将 fuzz.ratio(x , y) 分配给该字典的键 (x, y)。

示例代码-

fuzzDict = {}
for x in titles:
    for y in titles:
        fuzzDict[(x,y)] = fuzz.ratio(x,y)

稍后当您想要检索比率时，您可以简单地调用 fuzzDict[(x , y)] 来获取它。

您还可以在 Python 2.7+ -

中使用字典理解

{(x, y) : fuzz.ratio(x,y) for x in titles for y in titles}

Answer 2

使用列表理解和 itertools.product:

from itertools import product
[(x, y, fuzz.ratio(x, y)) for (x, y) in product(titles, repeat=2)]

使用 toolz

的漂亮而懒惰的解决方案

from toolz.curried import pipe, filter, map
pipe(
    product(titles, repeat=2),
    # No reason to check duplicates
    filter(lambda (x, y): x > y),
    map(lambda (x, y): (x, y, fuzz.ratio(x, y))))

Answer 3

您只需要迭代 combinations of the titles since the ratio doesn't depend on the order. This is significantly faster than iterating over a product 即可。

对于包含 20,000 个标题的列表，如果您使用 product，您将迭代 400 000 000 对。使用 combinations，您仅迭代 199 990 000.

from fuzzywuzzy import fuzz

import collections
import itertools

titles = ['Scary Movie', 'Happy Movie', 'Sappy Movie', 'Crappy Movie']

然后您可以将比率存储在字典中，您可以在字典中查找比率以获得 set 个具有该比率的对。

fuzzes_by_ratio = collections.defaultdict(set)

或者在字典中查找 frozenset 对并得到它们的比率。

fuzzes_per_pair = {}

-

for m1, m2 in itertools.combinations(titles, 2):
    pair = frozenset({m1, m2})
    ratio = fuzz.ratio(m1, m2)

    fuzzes_by_ratio[ratio].add(pair)
    fuzzes_per_pair[pair] = ratio

那么您可以稍后检索数据：

# I don't have fuzzywuzzy installed so this is just made up:
>>> fuzzes_by_ratio[91]
{frozenset({"Scary Movie", "Happy Movie"}), frozenset({"Sappy Movie", "Happy Movie"})}

>>> fuzz_per_pair[frozenset({"Scary Movie", "Sappy Movie"})]
82

请记住，此存储需要大量内存。您可以仅使用上述两种方法中的一种将其减半，具体取决于您的需要/方便。

模糊匹配的组织

Organization of fuzzy matches

python

fuzzy-comparison