如何在Python的嵌套列表中获取具有最多共同元素的两个列表

Question

我有一个列表，其中包含以下内容：

我有一个列表，其中包含以下内容：

[["This", "is","a", "test"], ["test","something", "here"], ["cat", "dog", "fish"]]

我该如何获得两个最相似的列表？在这种情况下，它们是第一个和第二个列表，因为它们都有单词“test”。

我尝试通过查找每两个列表之间的交集并跟踪共同单词最多的组合来解决此问题。然而，这种方法对于100,000个列表等数据量似乎效率低下。我认为需要(100,000 choose 2)种组合方式。有没有更快的方法呢？

以下是我的代码尝试：

from itertools import combinations

a = [["This", "is","a", "test"], ["test","something", "here"], ["cat", "dog", "fish"]]
c= combinations(a,2)


max = 0
for pair in c:
    intersection = set(pair[0]).intersection(pair[1]) 
    if len(intersection) > max:
        max = len(intersection)
        mostsimilar = pair

print mostsimilar

我的程序的输出结果和我预期的一样，但是在更大的测试案例中速度非常慢。

输出结果：

(['This', 'is', 'a', 'test'], ['test', 'something', 'here'])

- yzx7243

---

这只是一个简单的测试用例，但每个列表应该有许多单词，并且可能会重复。我只需要在所有列表中具有最多共同点的两个列表。 - yzx7243

如果允许重复，那么 ['a', 'b', 'b'] 是否与 ['b'] 相比较而言更相似，还是与 ['a', 'b'] 相同？ - blhsing

@blhsing ['a', 'b', 'b'] 和 ['a', 'b'] 有2个共同元素（a和b），因此这些应该是结果。 - yzx7243

@yzx7243 平均list长度会有多长？ - gmds

@gmds 很不幸，当我用我的数据集测试你的解决方案时，程序已经耗尽了内存（10,000个子列表）。无论如何，这个解决方案有点超出了我的知识范围哈哈。 - yzx7243

Answer 1

根据我的理解，我认为这个方法可以解决问题：

import numpy as np
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.neighbors import KDTree, DistanceMetric

data = np.array([' '.join(words) for words in [['This', 'is', 'a', 'test'], ['test', 'something', 'here'], ['cat', 'dog', 'fish']]])

vectorised = CountVectorizer(binary=True).fit_transform(data).todense()
metric = DistanceMetric.get_metric('manhattan')
kdtree = KDTree(vectorised, metric=metric)
distances, indices = [result[:, 1] for result in kdtree.query(vectorised, k=2, dualtree=True)]

nearest_distances = (distances == distances.min())
print(data[nearest_distances])

输出：

['This is a test' 'test something here']

我按照以下方式重新描述了问题：

每个单词列表（或句子）可以表示为稀疏矩阵中的一行，其中特定列中的1表示单词存在，0表示不存在，使用sklearn的CountVectorizer。

然后，我们可以看到，两个句子作为稀疏矩阵中的行的相似性可以通过比较它们在每个列中的元素值来确定，这就是曼哈顿距离。这意味着我们有一个最近邻问题。

sklearn还提供了一个k维树类，我们可以使用它来找到数据集中每个点的最近的两个邻居（因为一个点的最近邻是它本身）。然后，剩下的工作就是找到距离最小的邻居，我们可以用它来索引原始数组。

使用%%timeit，我测试了我的解决方案与blhsing在this page上的解决方案的运行时间，将导入语句放在计时循环之外。

# my solution
198 ms ± 1.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)  
# blhsing's solution
4.76 s ± 374 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)  

限制句子长度在20个单词以下：

# my solution
3.2 ms ± 294 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
# blhsing's solution
6.08 ms ± 714 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

- gmds

Answer 2

在时间复杂度为O(n x m)的情况下解决这个问题更加高效（其中n是列表的大小，m是子列表中单词的平均数量，因此如果m相对较小且与列表的大小相比恒定，则此解决方案将按线性比例扩展到n）。可以遍历列表并构建一个seen字典，将子列表中的每个单词映射到迄今为止已发现包含该单词的子列表的索引列表，然后使用collections.Counter在给定列表中的单词上使用most_common方法来找到最相似的列表的索引：

from collections import Counter
seen = {}
most_common_pair = None
most_common_count = 0
for index, lst in enumerate(a):
    for common_index, common_count in Counter(
            i for word in lst for i in seen.get(word, ())).most_common(1):
        if common_count > most_common_count:
            most_common_count = common_count
            most_common_pair = a[common_index], lst
    for word in lst:
        seen.setdefault(word, []).append(index)

考虑到您的输入列表存储在变量"a"中，most_common_pair将会是：

(['This', 'is', 'a', 'test'], ['test', 'something', 'here'])

- blhsing

---

如果每个子列表都有数百个单词，那会不会很重要呢？ - yzx7243

数百个单词与数量级为数十万的列表相比仍然相对微不足道。我已经用更好的时间复杂度描述更新了我的答案。 - blhsing

Answer 3

我的解决方法。我用一个包含729个列表的列表进行了测试，速度仍然很快。 老实说，我不确定它有多快。但它没有使用集合。

这里（它包含一个测试，只需使用该函数）：

a = [1,2,3,4,5,6,7,8,9]
b = [9,10,11,12,13,14,15]
c = [11,3,99]
d = [9,10,11,12,50,1]
ls = [a,b,c,d]


for i in range(100,3000,2):
    ls.append([i,i+1,i+2,i+3])


def f(ls):
    wordDic = {}
    countDic = {}
    ind = 0
    for t in range(len(ls)):
        countDic[t]={}
    for l in ls:
        for word in l:
            try:
                for sharedIndex in wordDic[word]: #For every list that we already know has this word
                    try:
                        countDic[sharedIndex][ind] += 1  
                        try:
                            countDic[ind][sharedIndex] += 1
                        except KeyError:
                            countDic[ind][sharedIndex] = 1
                    except KeyError:
                        countDic[sharedIndex][ind] = 1
                wordDic[word].append(ind)
            except KeyError:
                wordDic[word] = [ind]
        ind += 1

    mx = 0
    ans = -1
    ind = 0
    for sLs in countDic.values():
        for rLr in sLs:
            if mx < sLs[rLr]:
                ans = (ls[ind],ls[rLr])
            mx = max(mx,sLs[rLr])
        ind += 1
    return ans

print(f(ls))  

它的功能：

它基于这两个字典：wordDic和countDic。

wordDic的键是每个使用的“单词”，其值是找到该单词的索引列表。

countDic的键是每个列表的索引，其值是保存有多少个共享单词的字典。

countDic = { listInd: {otherLists:sharedAmount , ...} , ...}

首先创建这些字典。然后它遍历每个列表一次并保存它所拥有的单词。在将自己的索引添加到每个单词的索引列表之后，将“共享单词”计数的数量加1，存储在第二个字典中。

完成后，您会得到类似于以下内容：

{0: {1: 1, 2: 1, 3: 2}, 1: {2: 1, 3: 4}, 2: {3: 1}, 3: {1: 3, 0: 1}} ([9, 10, 11, 12, 13, 14, 15], [9, 10, 11, 12, 50, 1])

这段代码的意思是：

{(列表0：与列表1共享元素=1，与列表2共享元素=1，与列表3共享元素=2)，(列表1：与列表2共享元素=1，与列表3共享元素=4)，...}

在这种情况下，列表1与列表3共享的元素最多。函数的其余部分只是遍历字典并找到这个最大值。

我可能搞砸了我的解释。我认为最好先检查该函数是否比您自己的函数更好，然后再尝试理解它。

我也刚刚注意到，你可能只需要将之前找到的列表加1，而不需要将其他列表添加到当前测试的列表中。我会看看这是否有效。

编辑1：看起来是这样的。以下是代码：

try:
    countDic[ind][sharedIndex] += 1
except KeyError:
    countDic[ind][sharedIndex] = 1

可以注释掉。

希望这可以帮到你。

- laozoka