Эффективная структура данных для тегов?

Question

Представьте, что вы хотели сериализовать и десериализовать сообщения stackoverflow, включая их теги, как пространство максимально эффективно (в двоичном виде), но также и для производительности при выполнении поиска тегов. Есть ли хорошая структура данных для такого рода сценариев?

Stackoverflow имеет около 28532 различных тегов, вы можете создать таблицу со всеми тегами и назначить им целое число. Кроме того, вы можете сортировать их по частоте, чтобы самые распространенные теги имели самые низкие числа. Сохранение их просто как строка в формате «1 32 45» кажется немного неэффективным с точки зрения поиска и хранения.

Еще одна идея заключалась бы в сохранении тегов в виде переменной bitarray, которая привлекательна с точки зрения поиска и сериализации , Так как наиболее распространенные теги в первую очередь потенциально могут помещать теги в небольшой объем памяти.

Проблема была бы, конечно, в том, что необычные теги будут давать огромные битрейты. Есть ли какой-либо стандарт для «сжатия» битреймов для больших пространств 0? Или нужно использовать какую-либо другую структуру полностью?

EDIT

Я не ищу решение DB или раствор, где мне нужно держать целые таблицы в памяти, но структуру для фильтрации отдельных элементов

Answer 1

Вам нужна вторая таблица с 2 поля: tag_id question_id

Вот и все. Затем вы создаете индексы для tag_id, question_id и question_id, tag_id - которые будут охватывать индекс, поэтому все ваши запросы будут очень быстрыми.

Answer 2

Чтобы не подорвать ваш вопрос, но записи 28k действительно не так уж много. Возможно, вы преждевременно оптимизируете? Я бы сначала придерживался использования «обычных» индексов на таблице БД. Судорожные эвристики, которые они используют, как правило, очень эффективны и не тривиальны, чтобы бить (или, если вы можете, это действительно стоит усилий вовремя и являются достаточно большими?).

Также в зависимости от того, где вы действительно выполняете запрос тега, действительно ли пользователь замечает, что вы оптимизировали время 200 мс?

Первая мера затем оптимизировать :-)

EDIT

Без БД я бы, наверное, главной таблицы держит все теги вместе с идентификатором (если это возможно держать его в памяти). Храните регулярный отсортированный список идентификаторов вместе с каждым сообщением.

Не уверен, насколько поможет хранение на основе общности. Сортированный список, в котором вы можете выполнять обычный бинарный поиск, может оказаться достаточно быстрым; measure :-)

Здесь вам нужно будет перебирать все сообщения для каждого запроса тега.

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

Для меньшего стола вы можете прибегнуть к построению одного на основе хешированного значения (с дубликатами). Таким образом, вы можете использовать его, чтобы быстро перейти к меньшему списку кандидатов, который нуждается в дополнительной проверке, чтобы убедиться, что они соответствуют или нет.

Answer 3

У меня такое чувство, что вы слишком много абстрагировали свой вопрос; вы не очень много говорили о том, как вы хотите получить datastructure, что очень важно.

При этом я предлагаю подсчитать количество встречных событий для каждого тега, а затем использовать Huffman coding, чтобы получить кратчайшую кодировку, которая может использоваться для тегов. Это не совсем идеально, но я придерживаюсь этого, пока вы не продемонстрируете, что это неуместно. Затем вы можете связать коды с каждым вопросом.

Answer 4

Если вы хотите эффективно искать вопросы в определенном теге, вам понадобится какой-то индекс. Возможно, все объекты Tag могут иметь массив ссылок (ссылки, указатели, nummeric-id и т. Д.) Ко всем вопросам, помеченным этим конкретным тегом. Таким образом вам просто нужно найти объект тега, и у вас есть массив, указывающий на все вопросы этого тега.