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

Question

我在谷歌上没有找到任何相关的东西，所以我希望能在这里找到一些帮助：）

我有一个Python列表，如下所示：

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

我有一个函数，返回2个字符串之间的Levenshtein距离，对于House和hoose，它将返回2，依此类推

现在我想合并levenshtein分数为f.e.<；5，while（！）加上他们的分数，所以对于结果列表，我想要以下内容：

^{pr2}$

或者

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

等等

只要他们的价值得到增加就没关系了。在

列表中只有两个非常相似的项目，因此任何一个项目与其他项目的连锁效应都是不可预料的。在

Answer 1

import Levenshtein
import operator
import cluster

class Item(object):
    @classmethod
    def fromList(cls,lst):
        return cls(lst[0][0], lst[0][1], lst[1])

    def __init__(self, name, val=0, score=0):
        super(Item,self).__init__()
        self.name     = name
        self.val      = val
        self.score    = score

    def dist(self, other):
        return 100 if other is self else Levenshtein.distance(self.name, other.name)

    def __str__(self):
        return "('{0}', {1})".format(self.name, self.val)

def main():
    myList = [
        [['hoose', 5], 200],
        [['House', 5], 200],
        [["Bananaphone", 5], 10],
        [['trousers', 5], 100]
    ]
    items = [Item.fromList(i) for i in myList]

    cl = cluster.HierarchicalClustering(items, (lambda x,y: x.dist(y)))
    for group in cl.getlevel(5):
        groupScore = sum(item.score for item in group)
        groupStr   = ', '.join(str(item) for item in group)
        print "{0}: {1}".format(groupScore, groupStr)

if __name__=="__main__":
    main()

退货

^{2}$

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

输出为：

^{2}$

这种方法的一个明显的问题是，您正在考虑的单词可能与您已经考虑过的许多不同的单词集非常接近，但是这段代码只会将它合并到它找到的第一个单词集中。我投了+1票给Space_C0wb0y's answer；）

Answer 3

为了从我的评论中理解这一点，我只是从here抓取了一个距离的实现，并计算了一些距离：

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

现在，假设你的阈值是4。您必须合并House和{}，以及House和{}，但是不是trousers和{}。你确定这样的事情永远不会发生在你的数据上吗？在

最后，我认为更多的是一个聚类问题，所以你可能需要研究聚类算法。SciPy提供了一个hierarchical clustering的实现，它与自定义的距离函数一起工作（请注意，对于较大的数据集，这可能会非常慢，而且会消耗大量内存）。在

主要的问题是决定集群质量的度量，因为对于您的问题没有一个正确的解决方案。This paper（pdf）为您提供了一个了解该问题的起点。在