python - 查找集合的 "best"组合

Question

我有一个集合，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"))

这里每个单词至少代表两次，如果我们在句子上使用计数器可以看到:

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 的大小。

另外请注意，我希望结果集中的单词可以在前 100 个单词中找到(common_words 包含 100 个值)。这也是设计使然。

Answer 1

免责声明:您没有指定数据特征，所以我的回答会假设它不是太大(超过1,000,000个句子，每个最多1,000个)。描述也有点复杂，我可能没有完全理解这个问题。

解决方案:
与其关注不同的组合，不如为你最常用的 100 个单词创建一个 hashMap(dict in python)，然后遍历句子数组，为每个句子中的每个单词增加它对应的值(如果它已经在字典中)。
最后就是把这个hashMap按照每个word(key)的出现次数(value)排序，然后用出现频率最高的20个。
复杂性:
快速浏览一下算法，给出:
遍历N个句子，每个用M个词遍历，增加hashMap值。最后对(单词，出现)对的数组进行排序。可以忽略不计(hashMap大小不变，100个常用词)，抽取前20个。
时间复杂度:O(N*M)
空间复杂度:O(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]

顺便说一句，'he'和'she'没有出现在句子的任何地方，但是你说下面的单词组合得了5分

(i,you,he,do,think,yes,dont,can,it,good,cant,but,am,why,where,now,no,here,she,are)

我误解了这个问题吗？

信用到期:StackOverflow: Sort a Python dictionary by value