У меня есть набор 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, я получаю a 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 значений). Это также по дизайну.
