структура данных для ускорения поиска в тегах объектов в памяти по логической функции тегов?

Question

Если у меня есть набор тегов (<100) и набор объектов (~ 25000), где у каждого объекта есть некоторый поднабор тегов, знаете ли вы о существующей структуре данных, которая позволяла быбыстрый поиск тех объектов, которые удовлетворяют некоторой логической функции тегов? </p>

Добавление / удаление тегов и объектов не должно быть особенно быстрым, но выбор этих объектов с тегами, которые удовлетворяют булевой функции, должен быть.

Теперь, когда я записал свой вопрос, похоже, что я описываю базу данных в памяти, но первоначально я думал о некоторой бинарной древовидной структуре для объектов, где для каждой ветви выбирается леваяВетвь / right будет эквивалентна выбору тега have / have-not.Но что не позволило бы безразличные теги?я спрашиваю, как я задавался вопросом, было ли это сделано раньше, и мне трудно гуглить для структур данных.

• Заранее спасибо - Пэдди.

Answer 1

Вот предложение: используйте битовый массив для каждого тега с таким количеством элементов, сколько имеется объектов; каждый индекс которого представляет один объект. Значение в каждом индексе равно 1, если этот объект имеет этот тег.

Булевы функции над тегами - это быстрые операции над этим битовым массивом. И полученный битовый массив дает вам документы, которые удовлетворяют критериям.

Это не очень эффективно, если теги или объекты постоянно меняются, но, возможно, применимо для вас.

Answer 2

Как быстро вам понадобится? Насколько сложна ваша логическая функция, т. Е. Сколько тегов используется в одной типичной функции?

Как насчет использования некоторых в памяти базы данных SQL? Затем вы можете выразить логическую функцию простым запросом SELECT.