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

Question

我有一个清单清单如下

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

我如何才能得到两个词最多的共同点？在这种情况下，它将是第一和第二列表，因为它们都有共同的单词test

我试图通过找到两个列表的每个组合的交集并跟踪具有最多共同词的组合来解决此问题。但是，此方法在说100,000个列表时似乎效率低下。我认为是（100,000个选择2个）组合。有更快的方法吗？

这是我的代码尝试

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

我的程序的输出是我所期望的，但是在较大的测试用例中它非常慢

输出：

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

Answer 1

根据我对问题的理解，我认为这应该有效：

\n\n

import numpy as np\nfrom sklearn.feature_extraction.text import CountVectorizer\nfrom sklearn.neighbors import KDTree, DistanceMetric\n\ndata = np.array([\' \'.join(words) for words in [[\'This\', \'is\', \'a\', \'test\'], [\'test\', \'something\', \'here\'], [\'cat\', \'dog\', \'fish\']]])\n\nvectorised = CountVectorizer(binary=True).fit_transform(data).todense()\nmetric = DistanceMetric.get_metric(\'manhattan\')\nkdtree = KDTree(vectorised, metric=metric)\ndistances, indices = [result[:, 1] for result in kdtree.query(vectorised, k=2, dualtree=True)]\n\nnearest_distances = (distances == distances.min())\nprint(data[nearest_distances])\n

\n\n

输出：

\n\n

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

\n\n

我通过以下方式重新解决了这个问题：

\n\n

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

\n\n

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

\n\n

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

\n\n

使用，我在此页面%%timeit上的文本上测试了我的解决方案与 blhsing\'s 解决方案的运行时，将导入保留在计时循环之外：

\n\n

# my solution\n198 ms \xc2\xb1 1.6 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 1 loop each)  \n# blhsing\'s solution\n4.76 s \xc2\xb1 374 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 1 loop each)  \n

\n\n

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

\n\n

# my solution\n3.2 ms \xc2\xb1 294 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 100 loops each)\n# blhsing\'s solution\n6.08 ms \xc2\xb1 714 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 100 loops each)\n

\n