高效的标签数据结构？

Question

想象一下，您想要尽可能空间高效地（以二进制形式）序列化和反序列化stackoverflow帖子，包括它们的标签，同时在执行标签查找时保持性能。有没有适用于这种情况的良好数据结构？

Stackoverflow有大约28532个不同的标签，您可以创建一个包含所有标签并为它们分配整数的表格。此外，您可以按频率对它们进行排序，使得最常见的标签具有最低的数字。但是，将它们简单地存储为格式为“1 32 45”的字符串似乎有点低效，无论是从搜索还是存储的角度。

另一个想法是将标签保存为可变位数组，这从查找和序列化的角度很有吸引力。由于最常见的标签首先出现，因此您可能可以将标签适合小量的内存中。

问题当然是不常见的标签会产生巨大的位数组。是否有任何标准用于压缩大量0的位数组？或者应该完全使用其他结构？

编辑

我不是在寻找数据库解决方案或需要将整个表保存在内存中的解决方案，而是在寻找过滤单个项目的结构。

- Homde

Answer 1

并不是贬低你的问题，但28000条记录并不算多。您是否过早地进行了优化？建议首先在数据库表上使用“常规”索引。它们使用的哈希启发式通常非常高效，而且很难超越（如果您可以超越，那么真的值得花费时间和精力吗？收益是否足够大？）

此外，取决于您实际进行标记查询的位置，用户是否真正注意到您为其优化了200毫秒的时间？

首先测量，然后优化 :-)

编辑

如果没有数据库，我可能会有一个主表，其中包含所有标记以及ID（尽可能在内存中保存它）。将每个帖子的普通排序列表与其一起保留。

不确定基于共同点的存储可以提供多少帮助。在其中可以执行常规二进制搜索的排序列表可能足够快；测量 :-)

这里，您需要为每个标记查询迭代所有帖子。

如果这最终变得太慢，您可以采用为每个标签存储帖子标识符的方法。虽然这种数据结构可能变得相当大，并且可能需要寻找和读取文件。

对于较小的表，您可以采用基于散列值的构建方法（包含重复记录）。这样，您可以将其用于快速缩小需要进一步检查是否匹配的帖子候选列表。

- user45886

---

这种情况下没有数据库，而且问题是关于结构的，假设这种情况是有保证的。 - Homde

Answer 2

你需要第二张表，包含2个字段：tag_id和question_id。

就这样。然后你需要在tag_id、question_id和question_id、tag_id上创建索引 - 这将是覆盖索引，因此所有查询都会非常快。

- BarsMonster

Answer 3

我感觉你把问题抽象化了，没有说太多关于你想要如何访问数据结构的信息，这是非常重要的。

话虽如此，我建议计算每个标签的出现次数，然后使用Huffman编码来得到可以用于标签的最短编码。这并不完美，但我会坚持使用它，直到你证明它不合适为止。然后你可以将代码与每个问题相关联。

- Frerich Raabe

Answer 4

如果您想在特定标签内高效地查找问题，您需要一些索引。也许，所有的标签对象都可以有一个指向所有带有该特定标签的问题的引用数组（引用、指针、数字ID等）。这样，您只需要找到标签对象，就可以得到指向该标签下所有问题的数组。

- Mathieu Pagé