压缩整数列表以进行搜索访问
Compressing a list of integers for search access
我有一个前缀到行的映射，看起来像这样：
{
"x": [9],
"far": [1,2,3,4,5],
"car": [1,4,5]
}
键是索引搜索词，数组是匹配行的排序列表。很简单，一个基本的倒排索引。对于这个问题，我们假设 a-z0-9 个最大长度为三个的字符
字符（上限或 36+(36^2)+(36^3)=47,988 种组合，尽管在实践中可能少得多，比如大约 10k 种组合）。
但是，棘手的部分是我可能有大约 1000 万行，而低基数项目可能有一个包含所有 1000 万行的（无意义的）列表。在我的计算中，一个 10M 行的数组本身在未压缩的情况下达到 88.9MB。
压缩这些经常重复的数组的建议方法是什么？看来这在搜索中一定很常见，我想更多地了解处理大型和重复前缀映射的最佳方法，例如上面的方法。
我建议使用像 Roaring Bitmaps 这样的东西（在这个 paper 中有描述）。 Python、Java、C 中都有实现，它们会自动在 3 种不同格式之间切换以获得最佳存储密度。如果你想自己实现类似的东西，它本质上结合了：
- 数组（默认）
- 位集（适合更密集的集合）
- 运行-长度编码（存储每一个"run"连续数的开始和那个运行的长度）
这个概念适用于 32 位无符号整数，它可以轻松地包含 1000 万行的信息，而无需任何额外的工作来自定义您自己的解决方案。
我有一个前缀到行的映射，看起来像这样：
{
"x": [9],
"far": [1,2,3,4,5],
"car": [1,4,5]
}
键是索引搜索词，数组是匹配行的排序列表。很简单，一个基本的倒排索引。对于这个问题，我们假设 a-z0-9 个最大长度为三个的字符
字符（上限或 36+(36^2)+(36^3)=47,988 种组合，尽管在实践中可能少得多，比如大约 10k 种组合）。
但是，棘手的部分是我可能有大约 1000 万行，而低基数项目可能有一个包含所有 1000 万行的（无意义的）列表。在我的计算中，一个 10M 行的数组本身在未压缩的情况下达到 88.9MB。
压缩这些经常重复的数组的建议方法是什么？看来这在搜索中一定很常见，我想更多地了解处理大型和重复前缀映射的最佳方法，例如上面的方法。
我建议使用像 Roaring Bitmaps 这样的东西（在这个 paper 中有描述）。 Python、Java、C 中都有实现，它们会自动在 3 种不同格式之间切换以获得最佳存储密度。如果你想自己实现类似的东西，它本质上结合了：
- 数组（默认）
- 位集（适合更密集的集合）
- 运行-长度编码（存储每一个"run"连续数的开始和那个运行的长度）
这个概念适用于 32 位无符号整数，它可以轻松地包含 1000 万行的信息，而无需任何额外的工作来自定义您自己的解决方案。