如何合并列表中的相似项

Question

我在谷歌上没找到相关的信息，所以希望能在这里得到一些帮助 :)

我有一个Python列表，内容如下：

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

我有一个函数，可以计算两个字符串之间的Levenshtein距离，比如“House”和“hoose”之间的距离是2，等等。

现在我想把那些Levenshtein分数小于5的列表元素合并在一起，同时把它们的分数加起来。所以我想要的结果列表是这样的：

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

或者

[['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()

10: ('Bananaphone', 5)
500: ('trousers', 5), ('hoose', 5), ('House', 5)

返回

Answer 2

为了更好地说明我的观点，我从这里找到了一个计算距离的实现，并计算了一些距离：

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

假设你的阈值是4。那么你需要把House和hoose合并在一起，也要把House和trousers合并，但不需要把trousers和hoose合并。你确定在你的数据中不会出现这样的情况吗？

最后，我觉得这更像是一个聚类问题，所以你可能需要研究一下聚类算法。SciPy提供了一种层次聚类的实现，可以使用自定义的距离函数（要注意，对于较大的数据集，这可能会非常慢，而且也会消耗很多内存）。

主要的问题是要决定一个聚类质量的衡量标准，因为对于你的问题并没有一个正确的解决方案。这篇论文(pdf)可以作为你理解这个问题的起点。

Answer 3

和其他评论一样，我也不太确定这样做是否有意义，不过我想这里有一个能实现你想要的解决方案。这个方法效率很低 - 复杂度是 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 的回答 点了个赞；)