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

Question

Я начинаю с коллекции 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 и выполнение содержимого выполняется слишком медленно.

UPDATE

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

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

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

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

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

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

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

Answer 1

Начнем с набора предложений, по которым вы хотите выполнить поиск:

val corpus = Seq(
  Set("fell", "ate"),
  Set("cat", "snail", "tiger"),
  Set("tree", "bush", "jalapeno"),
  Set("pen", "paperclip", "stapler")
)

Один довольно эффективный способ представить это в виде таблицы битов с типами словаря в виде столбцов и предложений в виде строк. Мы определим пару функций для преобразования в это представление:

import scala.collection.immutable.BitSet

def vocabulary(c: Seq[Set[String]]) = c.reduce(_ union _).zipWithIndex.toMap

def convert(s: Set[String], v: Map[String, Int]) = (BitSet.empty /: s) {
  (b, w) => v.get(w).map(b + _).getOrElse(b)
}

И функция для поиска в корпусе c для всех предложений, содержащихся в данном предложении s:

def search(s: BitSet, c: Seq[BitSet]) = c.filter(x => (x & s) == x)

Это будет чертовски быстро, так как это просто побитовое «и» и сравнение равенства для каждого предложения в корпусе. Мы можем проверить:

val vocab = vocabulary(corpus)
val table = corpus.map(convert(_, vocab))

val sentence = convert(
  "The tree fell over on the bush because it ate a jalapeno".split(" ").toSet,
  vocab
)

val result = search(sentence, table)

Что дает нам List(BitSet(2, 6), BitSet(5, 7, 10)). Чтобы подтвердить, что это то, что мы хотели:

val bacov = vocab.map(_.swap).toMap
result.map(_.map(bacov(_)))

Это List(Set(fell, ate), Set(jalapeno, tree, bush)), по желанию.

Answer 2

Инвертированный индекс может быть весьма полезным для решения подобных проблем. В качестве отправной точки рассмотрим создание сопоставления из слов в C со списком всех наборов, содержащих это слово, таким образом, имеющих тип Map[String, List[Set[String]]]; это перевернутый индекс.

Используя инвертированный индекс, вы можете найти множества, содержащиеся в D, даже не проверяя те множества, которые имеют пустое пересечение с D. Просто переберите список наборов для каждого отдельного слова в D, отслеживая, сколько раз встречался каждый набор. Сравните количество с длинами наборов; набор S является подмножеством D тогда и только тогда, когда счет для S равен количеству элементов в S.

Этот подход ускоряет поиск, устраняя проверки тех множеств, которые вообще не пересекаются D. Вы можете расширить идею устранения еще большего количества проверок, используя индекс из наборов из двух слов в списки наборов, содержащих оба слова. Теперь наборы, у которых есть только одно общее слово с D, проверяться не будут (поэтому наборы, содержащие только одно слово, должны обрабатываться отдельно!). Становится необходимым выполнить итерацию по всем двухэлементным подмножествам D, сравнивая количество с количеством двухэлементных подмножеств каждого набора S, но в остальном это то же самое.

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

Answer 3

Часто можно ускорить базовые сравнения, создав словарь, в котором каждому слову присваивается номер, а затем переключается с сравнения строк на сравнение между числами.

Один из простых способов - выбрать одно слово случайным образом.из каждого набора, а затем создайте словарь, отображающий каждое слово в список наборов, из которых оно было выбрано.Затем, по предложению, найдите каждое слово в нем в словаре и посмотрите, содержится ли в предложении какой-либо из списков наборов.

Вы можете обнаружить, что набор не является подмножествомпредложение быстро.Создайте разреженный 64-разрядный битовый шаблон для каждого слова и представляйте каждый набор как или из битовых шаблонов каждого слова в нем.Представлять предложение как или из всех его слов.Тогда, если установлено & ~ предложение! = 0, множество не содержится в предложении.Если набор не проходит этот тест, он не является подмножеством.К сожалению, если он пройдет его, он все еще не будет подмножеством, и вам придется использовать более медленный тест, чтобы подтвердить это, но если при первом препятствии произойдет сбой достаточного количества наборов, вы можете сэкономить время.Как правило, я бы сделал так, чтобы в каждом 64-битном шаблоне было установлено k случайно выбранных битов, выбрав k таким образом, чтобы в 64-битных шаблонах, представляющих предложения, была установлена ​​примерно половина их битов - но вы, вероятно, сможете найти лучшую цель назадняя часть конверта с небольшой мыслью.Если вы дойдете до этого теста только после нахождения определенного слова в предложении, вы, конечно, не сможете включить это слово в создаваемые вами наборы, принимая его как должное.

Предположим, что каждый бит в нашем наборе слов64-битное растровое изображение независимо и не может установить его с вероятностью х.Тогда в предложении из n слов бит не устанавливается в растровом изображении для этого предложения с вероятностью x ^ n.Для набора с k словами мы можем отбросить на основе этого бита, если он задан предложением, а не словом, что происходит с вероятностью (1-x ^ k) x ^ n.Если я дифференцирую это, я получу максимум при x = (n / (n + k)) ^ (1 / k).Если я установлю n = 20 k = 4, то я хочу, чтобы x = 0,9554, и биты очищаются в предложении примерно в 40% случаев, а один бит отбрасывает в 7% случаев.Но у нас есть 64 бита, которые в значительной степени независимы от этой модели, поэтому мы отбрасываем полные несовпадения в 98% случаев.