Поиск надмножества
Вы не определили свою операционную систему, таким образом, на это трудно ответить. При использовании системы на основе гну libc Вы могли бы быть в состоянии использовать функцию libc backtrace().
GCC также имеет два builtins, которые могут помочь Вам, но которые могут или не могут быть реализованы полностью на Вашей архитектуре, и те __builtin_frame_address и __builtin_return_address. Оба из которых хотят непосредственный целочисленный уровень (непосредственным, я имею в виду, это не может быть переменная). Если __builtin_frame_address для данного уровня является ненулевым, должно быть безопасно захватить обратный адрес того же уровня.
3 ответа
Префиксное дерево звучит так, как будто я бы попробовал, если бы наборы были разреженными по сравнению с общим словарным запасом. Не забывайте, что если набор суффиксов двух разных префиксов одинаков, вы можете поделиться подграфом, представляющим набор суффиксов (это может быть достигнуто путем хеширования, а не произвольной минимизации DFA), давая DAG, а не дерево. Попробуйте сначала расположить свои слова как можно реже или чаще всего (держу пари, что одно из них лучше, чем какой-либо случайный или алфавитный порядок).
В качестве варианта вашей первой стратегии, где вы представляете каждый набор очень большим целым числом (битовым вектором), используйте разреженный упорядоченный набор / карту целых чисел (дерево из последовательности битов, которое пропускает серию последовательных нулей) - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452 (реализовано в http://www.scala-lang.org/docu/ files / api / scala / collection / immutable / IntMap.html ).
Если ваш эталонный набор (наборов) является фиксированным, и вы хотите найти для многих из этих наборов, какие из них содержат другие, я бы вычислить отношение непосредственного включения (ориентированный ациклический граф с путем из a-> b, если b содержится в a, и без избыточных дуг a-> c, где a-> b и b-> c). Фактор ветвления - не больше, чем количество элементов в наборе.
Сначала я бы построил 2 структуры данных, S и E.
S - это массив наборов (набор S имеет N подмножеств).
S[0] = set(element1, element2, ...)
S[1] = set(element1, element2, ...)
...
S[N] = set(element1, element2, ...)
E - это карта (хэш элемента для индекса) списков. Каждый список содержит S-индексы, в которых появляется элемент.
// O( S_total_elements ) = O(n) operation
E[element1] = list(S1, S6, ...)
E[element2] = list(S3, S4, S8, ...)
...
Теперь 2 новых структуры, набор L и массив C.
Я сохраняю все элементы D, существующие в E, в операции L. (O (n))
C - массив (S-индексы) счетчиков.
// count subset's elements that are in E
foreach e in L:
foreach idx in E[e]:
C[idx] = C[idx] + 1
Наконец,
for i in C:
if C[i] == S[i].Count()
// S[i] subset exists in D
Можете ли вы создать индекс для ваших документов? т.е. отображение каждого слова на документы, содержащие это слово. Как только вы это построите, поиск должен быть довольно быстрым, и вы можете просто установить пересечение, чтобы найти документы, соответствующие всем словам.
Вот Wiki о полнотекстовом поиске .
РЕДАКТИРОВАТЬ: Хорошо, Я получил это в обратном порядке.
Вы можете преобразовать свой документ в набор (если ваш язык имеет установленный тип данных), сделайте то же самое с вашими поисками. Затем становится простым вопросом проверки, является ли одно подмножеством другого.
За кулисами это фактически та же идея: она, вероятно, будет включать создание хеш-таблицы для документа, хеширование запросов и проверку каждого из них. слово в запросе по очереди.