给定字符串列表，找到最频繁的字符串对，第二频繁的字符串...，然后是最频繁的字符串三元组等

Question

我有一个包含k个字符串列表的列表(这k个列表中的每个列表都没有任何重复的字符串(。我们知道所有可能的字符串的并集(假设我们有n个唯一的字符串(。

我们需要找到的是：什么是最频繁的字符串对(即，在k个列表中，哪两个字符串最频繁地出现在一起？第二个最频繁的串对，第三个最频繁串对，等等

我唯一能想到的算法是非常复杂的，基本上为了求解最频繁的对，我会枚举n个字符串中所有可能的对(O(n^2((，并为每个字符串检查有多少个列表(O(k((，然后我会对结果进行排序，以获得我需要的结果，所以我的总体复杂度是O(n^2.x(，忽略最后一个排序。

有什么更好的算法的想法吗？(这有望很好地适用于三重弦和四重弦等(？python中的代码是最好的，但详细的伪代码(和数据结构，如果相关的话(或详细的总体思想也可以！

例如：如果

myList=[['AB', 'AC', 'ACC'], ['AB','ACC'],['ACC'],['AC','ACC'],['ACC','BB','AC']], 

那么配对问题的预期输出将是："AC"，"CC"是最频繁的配对，"AB"，"ACC"是第二频繁的配对。

Answer 1

您可以使用combinations、Counter和frozenset:

from itertools import combinations
from collections import Counter
combos = (combinations(i, r=2) for i in myList)
Counter(frozenset(i) for c in combos for i in c).most_common(2)

输出：

[(frozenset({'AC', 'ACC'}), 3), (frozenset({'AB', 'ACC'}), 2)]

Answer 2

这是适用于所有长度组合的通用解决方案：

import itertools
def most_freq(myList, n):
d={} #create a dictionary that will keep pair:frequency
for i in myList:
if len(i)>=n:
for k in itertools.combinations(i, n): #generates all combinations of length n in i
if k in d: #increases the frequency for this pair by 1
d[k]+=1
else:
d[k]=1
return {k: v for k, v in sorted(d.items(), key=lambda item: item[1], reverse=True)}  #this just sorts the dictionary based on the value, in descending order

示例：

myList=[['AB', 'AC', 'ACC'], ['AB','ACC'],['ACC'],['AC','ACC'],['ACC','BB','AC']]
>>> most_freq(myList,2)
{('AB', 'ACC'): 2, ('AC', 'ACC'): 2, ('AB', 'AC'): 1, ('ACC', 'BB'): 1, ('ACC', 'AC'): 1, ('BB', 'AC'): 1}
>>> most_freq(myList,3)
{('AB', 'AC', 'ACC'): 1, ('ACC', 'BB', 'AC'): 1}

Answer 3

在我的硬盘上发现一个片段，检查它是否对你有帮助：

from collections import Counter
from itertools import combinations
mylist = [['AB', 'AC', 'ACC'], ['AB','ACC'],['ACC'],['AC','ACC'],['ACC','BB','AC']]
d  = Counter()
for s in mylist:
if len(mylist) < 2:
continue
s.sort()
for c in combinations(s,2):
d[c] += 1
print(list(d.most_common()[0][0]))

将返回列表['AC','ACC']

Answer 4

我有一个相当简单的方法，不使用任何库
首先，对于主列表中的每个列表，我们可以计算每对字符串的哈希值。(有关字符串哈希的更多信息，请点击此处：https://cp-algorithms.com/string/string-hashing.html)。维护一个字典，该字典保存发生的每个哈希的计数。最后，我们只需要对字典进行排序，就可以得到所有对，并按照它们的出现次数进行排序。

示例：[['AB', 'AC', 'ACC', 'TR'], ['AB','ACC']]
对于列表1，即['AB', 'AC', 'ACC', 'TR']，
计算对的哈希值"AB AC"AC ACC"ACC TR"；并相应地将它们添加到字典中。对主列表中的所有列表重复相同操作。