algorithm - 用于排序的成对数组(整数，字节)的紧凑数据结构？

Question

我有一个非常具体的数据集，我需要以最紧凑的方式将其存储为字节数组。它是一个不断增加的实时整数流，通常是一个，但并不总是一个。每个整数值都有一个字节值标记。可能存在具有相同值和标签的值，但我只需要存储不同的值。仅支持的操作是添加新元素、删除和检查元素是否存在 - 我保留此数据集以检查最近是否“看到”了某些对。

一些示例数据:

# | value | tag |
1 | 1000  | 0   |
2 | 1000  | 1   |
3 | 1000  | 2   |
4 | 1001  | 0   |
5 | 1002  | 2   |
6 | 1004  | 1   |
7 | 1004  | 2   |
8 | 1005  | 0   |

正如我所说，这是一个直播，但我只能容忍存储最后几千个。目标是使其在存储(和 RAM)中尽可能高效，操作可能会花费很多。

如果我没有标签，我可以存储范围或值，(1000-1002)、(1002-1005) 等，通常连续有大约 5-6 个值，没有间隙。但是标签把这一切都搞砸了。

我目前的方法是用几个字节对每个值 + 标记对进行编码 - 一个字节用于标记，1 个或多个字节用于与先前值的“delta”。这样我需要存储第一个值，在上述情况下为 1000，然后存储增量 - #1 为 0，#2 为 1，#4 为 1，#5 为 1，#6 为 2 等。

大多数增量很小，为 1-10，所以我只能将其存储在一个字节中 - 如果值足够小以适合 7 位，则第一位是标志，否则 - 接下来的 7 位存储一个值的字节数delta占用。

也许有更好、更紧凑的方法？

Answer 1

由于您只有 127 个不同的标签值，因此您可以维护 127 个不同的表，每个表对应一个标签，从而使您不必存储标签。在每个表中，您仍然可以对增量使用漂亮的技巧。