Эффективно найти все наборы S из набора наборов C, которые содержатся в наборе D

Я начинаю с набора C целевых наборов. Каждый набор содержит слова (или строки без пробелов). Перебирая предложения, я могу рассматривать предложение как наблюдаемый набор слов D . Моя проблема в том, что для каждого предложения я хочу найти все наборы S в C , такие, что D содержит S . Другими словами, я хочу найти все наборы слов в C , для которых все их слова находятся в предложении.

Например, рассмотрим следующее содержание для C :

  {fell, ate}
  {cat, snail, tiger}
  {tree, bush, jalepeno}
  {pen, paperclip, stapler}

Теперь, если я вижу предложение «Дерево упало на куст, потому что съело джалепено.», Я хотел бы вернуть после двух сетов.

  {fell, ate}
  {tree, bush, jalepeno}

Это похоже на дерево. Однако это похоже только потому, что я сопоставляю не все слова в предложении, а скорее любое их подмножество. Одна из идей заключалась в том, чтобы представить коллекцию C в виде структуры данных с Map [String, PseudoTrie] на каждом уровне и пройти по ней несколькими путями, когда я перебираю слова в предложении в отсортированном порядке.

Я понимаю, что это похоже на поисковый запрос. Однако это нормально, если мне нужно перебрать все предложения, если вычисление для каждого предложения выполняется быстро.Итерация по каждому набору в C и выполнение содержит слишком медленно.

ОБНОВЛЕНИЕ

Я подумал, что некоторые из моих результатов могут заинтересовать людей. Эти тайминги состоят из 100000 предложений, и каждый целевой набор C в D содержит около 4 или 5 слов.

1. Оригинальная заявка. Просмотрите все целевые наборы и посмотрите, содержатся ли они в предложении, где предложение представлено набором слов. 227 с

2. Фильтрация по словарю. То же, что и исходный процесс, за исключением того, что предложения представлены набором слов в этом предложении, которые также входят в некоторый целевой набор. Преимущество состоит в том, что при сравнении нам нужно учитывать только подмножество слов в предложении. 110 с

3. Строки переводятся в целочисленный ключ, начиная с 0. Это также включает фильтрацию в испытании №2 по необходимости. 86 с

4. Добавьте инвертированный индекс. 4 с

Я также пробовал BitSets с инвертированным индексом. На это ушло 20 с, поэтому я не стал их придерживаться. Я не уверен, почему замедление - возможно, я что-то сделал не так.

Кроме того, я считаю, что моя первоначальная идея прекрасна (много слоев инвертированных индексов), но она довольно сложна, и у меня уже есть довольно хорошее ускорение!