如何在Python中将Levenshtein距离大于80%的单词分组

Question

如何在Python中将Levenshtein距离大于80%的单词分组

pythongroup-bylevenshtein-distancefuzzy-searchfuzzy-logic

11

假设我有一个列表：

person_name = ['zakesh', 'oldman LLC', 'bikash', 'goldman LLC', 'zikash','rakesh']

我正尝试以这样的方式对列表进行分组，以便两个字符串之间的萊文斯坦距離最大。为了找出两个单词之间的比率，我使用了一个 Python 包 fuzzywuzzy。

示例：

>>> from fuzzywuzzy import fuzz
>>> combined_list = ['rakesh', 'zakesh', 'bikash', 'zikash', 'goldman LLC', 'oldman LLC']
>>> fuzz.ratio('goldman LLC', 'oldman LLC')
95
>>> fuzz.ratio('rakesh', 'zakesh')
83
>>> fuzz.ratio('bikash', 'zikash')
83
>>>

我的最终目标：

我的最终目标是将单词分组，使它们之间的Levenshtein距离大于80%？

我的列表应该长这样:-

person_name = ['bikash', 'zikash', 'rakesh', 'zakesh', 'goldman LLC', 'oldman LLC'] because the distance between `bikash` and `zikash` is very high so they should be together.

代码:

我正在尝试通过排序来实现这一点，但关键函数应该是fuzz.ratio。好吧，下面的代码不起作用，但我正在用这个角度来解决问题。

from fuzzywuzzy import fuzz
combined_list = ['rakesh', 'zakesh', 'bikash', 'zikash', 'goldman LLC', 'oldman LLC']
combined_list.sort(key=lambda x, y: fuzz.ratio(x, y))
print combined_list

有谁能帮我把这些单词组合起来，使它们之间的Levenshtein距离大于80%？

- python

“合并”、“相似”、“非常高”和“类似于此”的定义都不够明确。您必须澄清您的规格说明。 - timgeb

4

我有些困惑。我看到了一个优化问题，即“将这组词语分成具有最大内部距离的簇”，但你继续谈论“排序”，也就是“将列表按顺序排列”。我不确定这两者如何混合在一起。你只是希望两个连续字符串之间的距离最大吗？ - dhke

2

在Python 2中，你可以将比较函数cmp传递给sort（及相关函数）。但是在Python 3中已经将其删除，但有一个解决方法：参见cmp_to_key。 - PM 2Ring

1

关于聚类问题（如果是的话）：听起来像最大团。节点是单词，如果这些单词之间的编辑距离>=80%，则它们之间有一条边。其余部分是NP完全问题，可以选择一个逼近算法，networkx实现了一些。 - dhke

1

@python 对于group by，您需要一个函数，根据单词本身确定单词的分组关联。问题在于：如果您可以将一个单词添加到一个组中取决于已经在该组中的所有元素。这是一个组合优化问题，据我所知，最大团正好符合要求。 - dhke

显示剩余6条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pynchia · Accepted Answer

这将对名称进行分组

from fuzzywuzzy import fuzz

combined_list = ['rakesh', 'zakesh', 'bikash', 'zikash', 'goldman LLC', 'oldman LLC']
combined_list.append('bakesh')
print('input names:', combined_list)

grs = list() # groups of names with distance > 80
for name in combined_list:
    for g in grs:
        if all(fuzz.ratio(name, w) > 80 for w in g):
            g.append(name)
            break
    else:
        grs.append([name, ])

print('output groups:', grs)
outlist = [el for g in grs for el in g]
print('output list:', outlist)

生产

input names: ['rakesh', 'zakesh', 'bikash', 'zikash', 'goldman LLC', 'oldman LLC', 'bakesh']
output groups: [['rakesh', 'zakesh', 'bakesh'], ['bikash', 'zikash'], ['goldman LLC', 'oldman LLC']]
output list: ['rakesh', 'zakesh', 'bakesh', 'bikash', 'zikash', 'goldman LLC', 'oldman LLC']

正如你所看到的，名称已经被正确地分组，但顺序可能不是你想要的。