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

Question

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

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

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

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

EDIT

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

Answer 1

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

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

Сначала измерьте, затем оптимизируйте: -)

EDIT

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

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

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

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

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

Answer 2

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

Answer 3

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

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

Answer 4

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