我有一个集合sentences，它以字符串的形式包含英语中的句子。我想创建一个sentences的子集，sentences2，它包含仅包含20个唯一单词的句子。当然，有很多这样的子集，但我正在寻找"最好"的子集，我所说的"最好"是指所有单词在sentences2中都有最高可能表示的子集。
下面的例子，将进一步阐明我所说的"最好"的含义：
如果我要为这组单词过滤sentences：
(i,you,do,think,yes,dont,can,it,good,cant,but,am,why,where,now,no,know,here,feel,are)
我会得到以下内容：
sentences2 = set(("where are you now", "here i am", "can you do it", "yes i can", "but can i do it", "no you cant", "do you feel good", "yes i do", "why are you here", "i dont know", "i think i know why", "you dont think", "yes i do", "no you dont", "i dont think you think", "i feel good", "but i am good", "i cant do it now", "yes you can", "but i cant", "where do you think i am"))
在这里，每个单词至少被表示两次，我们可以看到，如果我们在句子中使用计数器2:
c = collections.Counter({'i': 13, 'you': 10, 'do': 6, 'think': 5, 'dont': 4, 'can': 4, 'good': 3, 'but': 3, 'am': 3, 'it': 3, 'cant': 3, 'yes': 3, 'know': 2, 'no': 2, 'here': 2, 'why': 2, 'feel': 2, 'are': 2, 'now': 2, 'where': 2})
如果每个单词至少被表示两次，我们可以说这组20个单词的得分为2。
score = min(c.values())
但是，以下集合：
(i,you,he,do,think,yes,dont,can,it,good,cant,but,am,why,where,now,no,here,she,are)
得分为5，因为如果我用它来过滤sentences，我会得到一个sentences2，其中每个单词至少表示五次。
所以我在寻找所有可能的20个单词组合的最高分数。
以下是我解决这个问题的尝试：
sentences = ... # all the sentences in my text
common_words = ... # the hundred most common words in the text
result_size = 20
highest_score = 0
for sample in itertools.combinations(common_words, result_size):
sentences2 = list(filter(lambda s: set(s).issubset(sample), sentences))
c = Counter([j for i in sentences2 for j in i])
if len(c.values()) and min(c.values()) > highest_score:
# this is the set with the highest score to date
print(c)
highest_score = min(c.values())
然而，如果我没有弄错的话，这个算法将需要很长时间才能计算出5.3598337040381E+20个组合。你能建议我如何用更快的算法来解决这个问题吗？
请注意，生成的集合可以包含少于20个单词，这是完全可以的。例如，我的算法中的c.values()不必与result_size的大小相匹配。
还要注意的是，我希望结果集中的单词位于前一百个单词中(common_words包含100个值)。这也是经过设计的。
免责声明：您没有指定数据特征，所以我的回答会假设它不太大(超过1000000句，每句最多1000句)。此外，描述有点复杂，我可能还没有完全理解这个问题。
解决方案：
与其关注不同的组合，不如为100个最常用的单词创建一个hashMap(python中的dict)，然后遍历句子数组，并为每个句子中的每个单词增加相应的值(如果它已经在dict中)
最后，只需根据每个单词(键)的出现次数(值)对hashMap进行排序，然后使用最频繁的20个。
复杂性：
快速查看算法，得出：
遍历N个句子，每个句子遍历M个单词，增加hashMap值。最后对(单词、出现次数)对的数组进行排序。可以忽略不计(hashMap大小是恒定的，100个常用单词)，并提取前20个。
时间复杂度：O(N*M)
空间复杂度：0(1)(我们不需要存储句子，我们只有hashMap)
示例代码：
这里有一个快速的伪代码：
word_occur_dict = {#initialized with frequent words as keys, and zero as value for all}
for sentence in sentences: #for each sentence
sentence_words = sentence.split(" ") #construct the word list
for word in sentence_words: #for each word
if word in word_occur_dict: #if it is a frequent word, increase value
word_occur_dict[word]++
final_result = sort_dict(word_occur_dict)[:20] #returns list of tuples
Python代码：
import operator
common_words = ["do","think","yes","dont","can","it","good","cant","but","am","why","where","now","no","know","here","feel","are","i","you","he","she"]
common_words_dict = {}
sentences = ["where are you now", "here i am", "can you do it", "yes i can", "but can i do it", "no you cant", "do you feel good", "yes i do", "why are you here", "i dont know", "i think i know why", "you dont think", "yes i do", "no you dont", "i dont think you think", "i feel good", "but i am good", "i cant do it now", "yes you can", "but i cant", "where do you think i am"]
for w in common_words: #initialize the dict
common_words_dict[w] = 0
for sentence in sentences: #for each sentence
sentence_words = sentence.split(" ") #construct the word list
for word in sentence_words: #for each word
if word in common_words_dict: #if it is a frequent word, increase value
common_words_dict[word] = common_words_dict[word]+1
sorted_word_dict = sorted(common_words_dict.items(), key=operator.itemgetter(1))
print sorted_word_dict[::-1][:20]
顺便说一句，"他"one_answers"她"没有出现在句子的任何地方，但你说下面的单词组合的得分为5
(我，你，他，做，想，是的，不，可以，它，好，不能，但是，是，为什么，在哪里，现在，不，在这里，她，在)
我误解了这个问题吗。
来源：StackOverflow：按值对Python字典进行排序
第1步应该创建一个数据结构，该结构只包含句子中出现在common_words的单词。该结构还可以有单词出现的次数和一组整数，这些整数引用单词所在的句子。
counts[..., {
word:string,
count:number,
ids:Set<number>
}, ...]
一些伪码
countsMap = Map()
For i = 0 To sentences.Size - 1
sentence = sentences[i]
For Each word in sentence
If Not countsMap.Contains(word) Then
countsMap.Add(word, {word:word, count:0, ids:Set()})
End If
value = wordMap.Get(word)
If Not value.ids.Contains(i) Then
value.Count++
value.ids.Add(i)
countsMap[word] = value
End If
Next
Next
counts = countsMap.Values
理想步骤2如果你很幸运，并且你的计数数据类型包含<40个条目你可以用一台计算机在合理的时间内对C(n，20)组合进行详尽的搜索C(38，20)~=330亿。这将涉及对组合进行迭代，并将ids集合相交在一起，最终的集合大小是您的最低分数。
一些伪码
bestScore = 0
bestCombo = null
For Each combo in Combinations(counts, 20)
score = combo.Reduce((prev, curr) => prev.ids.Intersect(curr.ids)).Size
If bestScore < score Then
bestScore = score
bestCombo = combo
End If
Next
现实步骤2在大多数情况下，计数将包含40个以上的唯一单词，在这种情况下，您必须满足于最佳猜测/近似值。我可能会做一些类似的事情，使用上面的代码，但不是选择20，而是选择2，按分数降序排列结果，取10。
一些伪码
list = []
For Each combo in Combinations(counts, 2)
score = combo[0].ids.Intersect(combo[1].ids).Size
list.Add( { score:score, words:[ combo[0].word, combo[1].word ] } )
Next
// sort descending by score
list.Sort((a, b) => b.score - a.score)
// grab the 20 best words
result = Set()
i = 0
While result.Size < 20
result.Add(list[i].words[0])
result.Add(list[i].words[1])
i = i + 1
End While
你会得到大于1的最终分数吗？从统计数据来看，这将取决于有多少独特的单词和句子，但可能不是。
编辑实施说明和更正。将单词出现的句子id集相交将得到最小分数减1(零索引)。例如，"Dog"出现在第1句和第2句中；"Cat"在第2和第3句中；"Frog"在第4句中；[1，2]/\[2,3]/\[4]=[]的交集，但最小分数为1result.Size()+1。同样，只有"Dog"one_answers"Cat"[1，2]/\[2,3]=[2]的集大小为1，但最小得分为2。
我可以建议您尝试下面的方法吗。我没有数学证据表明它会产生绝对最好的"分数"，或者其他一些"衡量好坏的标准"，但我相信这可能会帮助你，当然，除非情况需要你真正证明并找到绝对最好的。
我不会说python，但策略和随后的实现非常简单，甚至不需要伪代码来解释。不过，我会用几个词，不是因为它很复杂，而是为了清楚(我希望)。
你需要一种方法来对矩阵进行对角化，或者至少找到与最大特征值相对应的特征向量。并不是每种语言本身都提供了一种方法。在C++中，您可以使用Eigen库。在我用来测试的C#中，我连接了MathNet。在python中，我不知道。对角化/特征向量功能的要求是有限的：矩阵总是真实的、对称的，所有元素都是正的。然而，尽管对角元素在其行/列中至少与其他元素一样大，但矩阵肯定不是"对角主导"的。
你提出的问题可以抽象地用整数表示，而不是用单词表示，这使得(对我来说…)制定和实现更方便(但除此之外，这完全无关紧要)。事实上，我们只需要你的"common_words"，因此需要100个整数[0.99]，你只需将单词放在数组或列表中并使用它们的索引，就可以设置一次单词和整数之间的映射。
顺便说一句：对于您的语言应用程序，该策略可能(远)比对于一个完全通用的整数问题更合适，在这个问题中，您可能会构造"恶意"的困难输入。原因是，我们基本上会利用项目(同一句子中的单词)之间的成对相关性(如果有的话)，而三元组、四元组。。。可能会降低它的效率(但我们会为三元组做点什么)。显然，在格式良好的语言中，你会期望相关性："am"通常与"I"一起出现，尽管"have"总的来说可能比"has"更频繁，但一旦你找到"he"，你在同一句话中可能也会得到一个"has(拥有)"而不是"have(有)"。等等。
一些定义是有序的。
NCommon是您的common_words(i.c.100)中的元素数。公用字"是"整数[0.NCommon-1].
NMaxSet是你的问题限制(i.c.20)，最后是你愿意使用的最大单词数。
F是一个过滤器：你用来定义哪些句子包含在某个集合中的"单词"的集合。最后，您必须调整过滤器，使F.计数不超过NMaxSet。
M(N)是一个平方NxN矩阵；行和列索引在[0..N-1]中
S(F)是满足滤波器F的句子(来自问题输入)的集合。这里的"句子"始终是[0.NCommon-1]范围内的整数的集合，请参见上文。同一句话中的重复单词是无关的(问题描述)，这种重复从我们的整句话中删除。
我们开始吧。
I。准备
初始化矩阵MCommon=M(NCommon)。创建包含所有common_words的FCommon筛选器。
过滤输入，删除句子中的重复单词。这将生成一个句子集S0=S(FCommon)，这是您的"真实"输入：所有不相关的内容都已删除。
动态地，在S0中接受句子的同时，填充矩阵MCommon:{for(句子中的j)：for(句中的k):M(j，k)+=1}。矩阵是对称的，所以你可以只填充右上角的三角形，并在末端镜像到左下角的三角形。
完成扫描后，M[j，k]是包含j的"句子"中k次出现的次数(反之亦然：矩阵是对称的)。M[k，k]是S中所有句子中k的总数。M是(成对的)相关矩阵，告诉你{j，k}组合出现在底层句子集中的可能性。
(在处理这样的矩阵时，总是：如果最后碰巧有空列(因此有行)：删除这些列和行，同时删除位于矩阵下方的Filter中的相应条目，因为它显然没有起到任何作用。此后，我们将假设这已经完成(除非另有说明)，即矩阵中没有列/行为空。)
II。计算结果(主要方法，我们将在下面进行细化)：
计算对应于最高特征值的MCommon的特征向量E：E是具有NCommon系数的数组(向量)。
设置NTarget=NSetMax
确定哪些是E中的N目标最大系数。我们对它们的值不感兴趣，但对它们的指数感兴趣。把这些索引放在一起：它们定义了一个新的过滤器F(NTarget)。
通过新过滤器运行S0以生成STarget。计算所有单词的出现次数，找到它们的最小值：这就是你的"设置质量"值。例如，您可以通过计算关联的MTarget并扫描对角线值MTarget[k，k]来执行此操作。这似乎涉及不必要的额外工作，因为您还计算了非对角线元素，但我们会看到MTarget在后续改进中可能很方便。
III。改进。
A) 我们需要验证是否通过从过滤器F(NsetMax)中删除一个或多个项目，将其减少到比NsetMax小的一些NTarget，我们会得到更好的分值。这需要注意：删除两个(或3个，…)项目很可能会提高分数，但删除其中任何一个项目都会使分数恶化。
让我们对这个问题进行第一次(也是相当合理的)尝试。
在生成STarget的同时，您还填充了一个新的矩阵MTarget(您可以看到，它很方便…)，就像您之前对MCommon所做的那样。大小为NTarget。得到它的最大特征值特征向量。确定最小系数。从筛选器中删除相应的索引。
再次过滤(作为输入，当然，现在可以使用STarget集合)并计算分数。如果更好：标记/记住。在所有情况下(无论是否改进)都以相同的方式继续，逐个减少过滤器，直到你什么都没有了。
B) 正如简要解释的那样，人们可能会认为，进一步将过滤器降低到NSetMax以下的"谨慎"方法的原因是——一次一个——在某种程度上也适用于第一步，在第一步中，我们在一次大打击中将F(NCommon)减少为F(NTarget=NMaxSet)。
为了适应这一点，我们可能需要从NCommon逐步转到NMaxSet。为了不产生太多的计算开销，我们不会采取大小为1的步骤，但每次都要减少大约10%或类似的数量。
因此，在上面的II中，不要立即将NTarget设置为NSetMax，而是(例如)将NTarget=90。构造相应的滤波器，将滤波器应用于S0，给出S1，还产生矩阵M1，得到其特征向量(最大特征值)。重复：将NTarget设置为80、70、60，依此类推。在后期阶段，您可能会更加谨慎，将40降低到35，将30降低到28到26。。。在每一步中，您都要在前面的结果的基础上进行构建并使用，以最佳地利用大小和计算工作量的减少。
一直以来，您都想监视最大的NSetMax(算法这一部分的最终值)系数是否总是出现在相同的索引中。这将提供一些关于最终结果是否可靠的信息：预期最终滤波器相对于算法路径的稳定性
C) 考虑一下我们已经减少到NSetMax的情况，并调查是否应该以一次一次的方法进一步减少它。(在(B)的最后阶段，如果从上方接近NSetMax时，您一接近NSetMax就"一次一个"，则同样适用。)
假设在算法的这个阶段，在您的(第一个或稍后的)STarget集合中，某些"单词"对，使得从过滤器中去除这样的特定对将改善情况，而它们在特征向量中的单独系数都不是最小的。我不确定这是否可能，但让我们看看如何处理。如果(你的)测试表明它无关紧要，你可以在最终实现中从算法中删除这个功能。
假设我们有一些NTarget、相关联的滤波器FTarget和矩阵MTarget。(过滤器中项目("单词")的顺序总是等于(当然)矩阵中行和列的顺序。)
从MTarget，我们可以直接推断出一些信息，如果我们从过滤器中删除第j个项目，会发生什么。当然，矩阵中的第j行和第j列变为空(全部为零)。更有趣的是，M[j，k]表示项目k在包含项目j的所有句子中出现的次数。因此，当消除所有j(通过将其从滤波器中去除)时，我们预先知道，在得到的新矩阵MRreduced中，元素MRreduced[k，k]将精确地减小M[j，k]值。(顺便说一句，这提供了一种确定要删除哪个项目的替代方法(如果您选择只删除一个)：最小值{j:M[j，j]}是相关集合S的分数，根据M，我们可以计算出在移除特定项目j时所有对角线元素将如何变化，从而能够预计算得到的分数)
然而，在这里，我们想知道在删除项目j和k的一些PAIR后，分数会受到什么影响。我们现在需要确定M[p，p]如何对所有不是j或k的p产生影响。这不能直接从M计算：移除j会影响行k，尽管我们知道它是如何改变[k.k]和任何其他[p，p]的，但我们不知道它会如何改变[k，p]，这是计算ALSO("后续")去除k将如何改变[p，p]所需要的。顺便说一句，请注意，对于最终结果来说，无论是先删除j，然后删除k，还是反之亦然，或者同时删除两者，都必须无关紧要。
为此，我们需要某种"衍生物"。幸运的是，我们可以在没有太多计算工作量的情况下计算和处理它(考虑到NTarget已经很小了，大约20个)。
考虑与当前过滤器F相关的"简化过滤器"G(F；j)，其被简单地定义为处理F，但在其中忽略项目j。对于G，我们以与往常相同的方式计算"约简矩阵"N(G)，其中为了讨论(和实现)的方便，我们保持相同的大小(不删除空列/行)。当然，在这样的N矩阵中，第j行和第j列是空的。它的对角线元素将具有如上所述的值(我们可以直接从M计算这些值)。然而，现在我们也有所有的非对角线元素，这些元素都是由删除j.产生的
从N(G｛F；j｝)中，我们现在可以确定如果我们删除ALSO项k会发生什么，请参阅上面关于如何从当前矩阵中获得预期分数的详细说明。因此，这允许在移除对{j，k}时计算得分。
如果集合大小是20，我们必须计算20个N(G(F；j))矩阵，我想这是一个相对较小的工作量(你的句子集现在也会比原来小很多)。然后，在所有N的情况下，为20*19/2个唯一对中的每一个计算得到的对移除分数，您就可以选择要从过滤器中删除的PAIR(而不是单个元素)。你可以随时将其与"一次一个"的减少进行比较，并做出适当的选择，如何系统地减少过滤器，以获得更好的分数。这种比较有很多方法。一个相对简单的方法是：首先计算一对，然后计算一个(总共3个元素)。与先去掉一个，然后再去掉一对进行比较。从这两个步骤中选择最好的一个，但只执行第一步(单个或成对)，然后重复该过程。
注意使用这些"导出的"滤波器G、矩阵N和随后的分数预计算，你有效地引入了三重项之间的相关性：你确定了在去除j和k后，所有{j，k，p}到p的频率会发生什么。当然，这个想法可以扩展到包含四元组和更多，但(a)我认为它实际上不会有多大帮助，(b)你在这条路上走得越远，计算工作量就会增加得越快。我甚至怀疑引入这里解释的"三元组"是否相关，但我不是语言专家，除了一些额外的编程工作外，没有什么大的缺点。
D) 该策略的主干是依靠具有最大特征值的特征向量来指向相关项目，随后进行过滤。当然，可能会发生两个或多个特征值"几乎"相同的情况，并且相应的特征向量可能指向完全不同的项目集当分析它们最大的成分时。在这种情况下，"分支"是值得的，也就是说：与其中一个一起，工作到最后，然后和他们的竞争对手重做每件事，看看他们是否能取得更好的结果。如果你遇到很多分支(在通往解决方案的道路上的不同点)，就会出现问题。这种情况不太可能发生，但是如果真的发生了，实施应该有一些策略来以实际的方式处理它。我建议您首先保留任何分支，但您确实要监控"竞争性"最大特征值的出现，以便向用户输出警告。或者，您可以实现对此类分支的处理，但要严格要求程序认为"几乎相等"的内容，或者将其限制为将要调查的分支(总数)增加到分支的数量，从而减少计算时间失控的可能性。
我不得不把它留在这里(因为时间不够…)，希望我已经充分解释了这个想法，以及一些需要考虑的细节和改进。
我没有时间为自己组织相关的"真实语言"句子作为输入并进行测试。我已经在C#中编程了基本步骤，针对随机整数"语句"进行了测试，并带有一些偏差，以迫使某些"单词"比其他单词更频繁地出现，但不必担心"句子"中"单词"之间的相关性。结果对我来说似乎很合理，但我没有时间对其进行广泛分析。
考虑到我用作输入的"随机"序列中缺乏结构，而实际语言预计会表现出显著的成对相关性，该策略所利用的，我很希望这对你来说可能是一件有用的事情。
[编辑]补充说明：在上面的文章中，我偶尔会草率地谈论"j"、"k"等。对此我感到抱歉。有时"j"指的是某个东西的第j个条目(矩阵行，过滤器列表中的索引)，有时它指的是(通常)过滤器中对应的VALUE。例如，一个过滤器可能包含18个项目，编号(索引)0..17，但它们的VALUES总是指原始的Common_words列表，因此它们可以是{3，15，29，30，31，40，…}。然后，当它说"从过滤器中删除j"时，通常意味着"从过滤器删除第j个条目(该条目可以具有[0.NCommon-1]中的任何值)。对句子应用筛选器时，将筛选器中的VALUES与句子中的值进行比较。我希望，背景——再加上对推理路线的公正理解——总是能清楚地表明真正的含义。
[编辑：部分测试结果]我已经运行了我的C#实现，使用上面的算法(或多或少：描述了大多数但不是所有的改进/细节)来获得它将产生的一些印象。
作为输入，我从古腾堡项目中挑选了4本书(纯文本)。总共(只有)27k个句子，380k个单词(20k个不同)，所以这是一个相当小的样本。
根据该输入确定的常用词列表以"The"、"of"、"and"、"to"开头。。。(按总输入中出现的频率排序时)。
该算法过滤了14个单词("i"、"what"、"do"、"you"、"it"、"yes"…)，以产生8的"最优"集合质量值"(仅用这14个单词发现139个句子)。
由于我对只使用100个"常用词"的假设持怀疑态度，我事先允许使用500个常用词，而不是100个，在进入最终过滤器的单词中，有4个频率编号超过100("是"、"知道"、"说"、"想")：例如，如果你要按所有输入中的出现次数对它们进行排序，大概是"常用词"的基础。
我不确定是否有可能在不到指数的时间内找到最佳解决方案，这个问题可能没有足够的结构。但这里有一个启发性的方法来想出一个"好"的解决方案。
我认为这样做的方法是从大小为0的wordset开始，并以"聪明"的方式逐个添加单词，最大值为20。考虑到，对于给定的wordset_n，当添加一个新词时，每个单独单词的分数只能增加或保持不变。wordset_(n+1)可以具有比wordset_n更低的分数的唯一方式是如果第(n+1)个字降低最小值。因此，我们限制自己只添加能提高最低值或保持不变的单词(但请参阅下面的详细说明)。
因此，对于第一个近似值，
- 按
sentences中的频率对common_words中的单词进行排序 - 将最频繁出现的单词添加到
wordset中，直到得分为非零 - 搜索可能的
wordsets的树，该树仅通过添加增加或保持前一节点的分数的单词来构建(最大N=20)。因此，该树下的路径将是wordset_n、wordset_(n+1)、wordset_(n+2)`，每个节点由前一个节点加上一个新词组成 - 选择得分最高的叶节点
在第二个近似值上，a)您可能需要尝试步骤2的多个组合。100选3等于162000，这不是不可能的。b) 此外，对于步骤3，您可能希望向前看两个步骤，而不仅仅是一个步骤——即，如果在单词n+2的所有可能性之后，分数仍然低于wordset_n，则仅拒绝wordset中点n+1的单词。如果存在反相关性，即一个动词的短句不太可能包含另一个动词，这可能会有所帮助。最后c)如果这种方法在计算上仍然是禁止的，那么你可以通过关闭第(n+1)个没有将分数提高给定量的分支来进一步限制树的构建。
如果sentences中单词的分布相对独立，或者只表现出正相关性，那么这种方法可能会让你得到非常接近最优的结果。
我会寻找一种数据聚类的形式，以加快每20个单词的搜索速度。
重要的数据是句子中唯一的单词。
如果jaccard距离很小，则可以认为两个句子很近。jaccard距离为1-(句子中单词的交集)/(句子中词的并集)。
因为jaccard距离是度量的(满足三角形不等式)，所以可以建立m树索引，从而更快地找到句子。
在此基础上可以进行聚类(最佳结果将彼此接近)。
最后，通过迭代每个句子，找到K个最近的邻居，你可以找到一组最多20个可以使用的单词。这将为K(最好共享20个单词的句子)提供不同的值。
我可能会使用一个数据库来支持这个select union和select intersection，允许设置测试
通过CLIQUE的归约NP难(假设我们用一个参数替换20)。给定一个图，我们在其中寻找一个k集团，为每个顶点分配一个唯一的单词，使两个单词的句子对应于每个边，并尝试选择k，选择两个句子，其中每个单词包含k-1次。
需要考虑是否存在具有合理参数化复杂性的算法。