如何合并列表中的类似项目

Question

我在Google上找不到任何相关内容,所以我希望在这里找到一些帮助:)

我有一个Python列表如下:

[['hoose', 200], ["Bananphone", 10], ['House', 200], ["Bonerphone", 10], ['UniqueValue', 777] ...]

我有一个函数返回2个字符串之间的Levenshtein距离,对于House和hoose它将返回2,等等.

现在我想合并levenshtein得分为fe <5的列表元素,而(!)添加他们的得分,所以对于结果列表我想要以下内容:

[['hoose', 400], ["Bananaphone", 20], ['UniqueValue', 777], ...]

要么

[['House', 400], ["Bonerphone", 20], ['UniqueValue', 777], ...]  

等等

只要它们的值被添加就没关系.

列表中只有2个项目非常相似,因此任何一个项目的链式效果与很多其他项目相似都不会出现.

Answer 1

为了从我的评论中提出要点,我只是从这里抓住了那个距离的实现,并计算了一些距离:

d('House', 'hoose') = 2
d('House', 'trousers') = 4
d('trousers', 'hoose') = 5

现在,假设你的阈值是4,你将不得不合并House和hoose,以及House和trousers,但不 trousers和hoose.您确定您的数据永远不会发生这种情况吗？

最后,我认为更多的是聚类问题,因此您可能需要研究聚类算法.SciPy提供了一种层次聚类的实现,可以使用自定义距离函数(请注意,对于较大的数据集,这可能会非常慢 - 它也会消耗大量内存).

主要问题是决定群集质量的衡量标准,因为没有一个正确的解决方案可以解决您的问题.本文(pdf)为您提供了一个解决问题的起点.

Answer 2

与其他评论一样，我不确定这样做是否有意义，但我认为这是一个可以满足您要求的解决方案。这是非常低效的 - O(n ² ) 其中 n 是列表中的单词数 - 但我不确定是否有更好的方法：

data = [['hoose', 200],
        ["Bananphone", 10],
        ['House', 200],
        ["Bonerphone", 10],
        ['UniqueValue', 777]]

already_merged = []

for word, score in data:
    added_to_existing = False
    for merged in already_merged:
        for potentially_similar in merged[0]:
            if levenshtein(word, potentially_similar) < 5:
                merged[0].add(word)
                merged[1] += score
                added_to_existing = True
                break
        if added_to_existing:
            break
    if not added_to_existing:
        already_merged.append([set([word]),score])

print already_merged

输出是：

[[set(['House', 'hoose']), 400], [set(['Bonerphone', 'Bananphone']), 20], [set(['UniqueValue']), 777]]

这种方法的一个明显问题是，您正在考虑的单词可能与您已经考虑过的许多不同单词集足够接近，但此代码只会将其集中到它找到的第一个单词中。我对Space_C0wb0y 的答案投了 +1 票；）