algorithm - 字符串和整数范围集合的散列方法

Question

我有一个数据，例如:

我需要将内容与为内容和范围字段提供的输入相匹配，以返回匹配的行。如您所见，Content 字段是字符串的集合，而 Range 字段是两个数字之间的范围。我正在查看散列数据，用于与散列输入匹配。正在考虑迭代单个字符串哈希码的集合并将其存储在内容字段中。对于 Range 字段，我正在考虑使用区间树。但是接下来的挑战是，当我对内容输入和范围输入进行哈希处理时，我将如何找到该哈希码是否存在于为内容字段中的字符串集合生成的哈希码中以及范围字段中是否存在该哈希码。

如果有任何其他替代方法可以实现这一点，请告诉我。谢谢。

Answer 1

您的问题有一个简单的解决方案:倒排索引。

对于内容中的每个项目，创建将“Content”映射到“RowID”的倒排索引，即创建另一个 2 列的表，即。内容(字符串)，RowIDs(逗号分隔的字符串)。

对于第一行，在该表中添加条目 {Azd, 1}、{Zax, 1}、{Gfd, 1}...、{Mni, 1}。对于第二行，为新内容字符串添加条目。对于第一行中已存在的内容字符串(例如“Gfd”)，只需将新行 ID 附加到您为第一行创建的条目即可。所以，Gfd 的行看起来像 {Gfd, 1,2}。

处理完成后，您将得到一个表，其中“内容”字符串映射到存在此内容字符串的所有行。

---

为将“Range”映射到“RowID”执行相同的倒排索引，并创建另一个 Range(int)、RowIDs(逗号分隔的字符串)表。

现在，您将有一个表，其行将告诉哪些行 ID 中存在哪个范围。

---

最后，对于您必须处理的每个查询，从倒排索引表中获取相应的 Content 和 Range 行，并对这些逗号分隔列表进行交集。你会得到你的答案。