如何压缩只有 1、0 和 -1 值的时间序列
How to compress a time series where the only values are 1, 0, and -1
我正在尝试有效地存储大量（> 10 亿）时间序列。每个值只能为 1、0 或 -1，该值每分钟记录一次，共 40,000 分钟。
我意识到每分钟的值可以存储在 2 位中，但我认为有一个更简单的方法：任何时间段的排列数量有限，所以我可以为每个排列分配一个数字而不是记录所有的位。
例如，如果我要花 16 分钟时间：记录这些值需要 (16 x 2 位) = 32 位 = 4 字节。但据推测，如果我简单地为 16 种可能的排列中的每一种分配一个数字，我可以将这个数字减半（或更多）。
我的问题：确定16个值的排列数的公式是什么？如果值可以是任何数字，我知道如何计算它，但是当只有 3 个值时我不知道如何计算。
例如，您可以压缩文件，您将获得仅 3 个符号的出色压缩级别。
如果你想努力工作，你可以做基本的 zip 算法：
您有 3 个值 -1、0 和 1。
然后你可以像这样定义一个事务树：
bit sequence - symbol
0 - 0
10 - 1
110 - -1
1110 - End of data
因此，如果你读到一个零，你就知道它是一个 0 符号，如果你读到一个 1，你必须读下一位才能知道它是否是 1，或者你必须再读一位才能知道它是否这是一个-1。
因此，如果您有一个系列 1,1,0,-1,0，它将翻译为：
101001100
如果这是您看到的所有数据，那么您有 9 位，因此您需要完成某些操作才能达到 16。
然后只需放置数据标记的结尾，然后再放置任何东西。
10100110 01110000
为此，您需要使用位运算符。
如果您知道其中任何符号的出现率高于其余符号，请使用位数较少的符号（例如 0 应代表最常用的符号）。
如果 -1、0 和 1 的可能性均等，则 n 个样本所需的位数公式为 ceiling(n log 23)。对于一个样本，正如您所指出的那样，您得到了两位，实际上浪费了一种状态，每个样本浪费了 0.4 多位。
事实证明，五个样本非常适合八位，其中 35 = 243，每个符号仅浪费大约 0.015 位。
您可以将额外的状态用作流结束符号。例如，您可以使用剩余 13 个状态中的五个来表示流结束，表示剩余 0、1、2、3 或 4 个样本。然后，如果它是 1、2、3 或 4，则这些样本还有一个字节。更好的做法是对 1 种情况使用三种状态，在该字节中提供样本。然后使用 13 种状态中的 7 种，需要一个字节来结束 0 和 1 情况下的流，以及两个字节来结束剩余 2、3 或 4 情况下的流。
如果 -1、0 和 1 的概率明显不同，则您可以对样本使用霍夫曼编码，以比上述 "flat" 情况更少的位数表示结果。然而，三个符号中的一个样本只有一个霍夫曼代码，这通常不会提供良好的性能。所以你会再次想要组合样本以获得更好的霍夫曼编码性能。 （或使用算术编码，但在这种情况下，这可能比必要的复杂得多。）因此，您可以再次将五个样本分组为 0..242 范围内的一个整数，然后霍夫曼编码这些样本，以及流的结尾只出现一次的符号（称为 243）。
我正在尝试有效地存储大量（> 10 亿）时间序列。每个值只能为 1、0 或 -1，该值每分钟记录一次，共 40,000 分钟。
我意识到每分钟的值可以存储在 2 位中，但我认为有一个更简单的方法：任何时间段的排列数量有限，所以我可以为每个排列分配一个数字而不是记录所有的位。
例如，如果我要花 16 分钟时间：记录这些值需要 (16 x 2 位) = 32 位 = 4 字节。但据推测，如果我简单地为 16 种可能的排列中的每一种分配一个数字，我可以将这个数字减半（或更多）。
我的问题：确定16个值的排列数的公式是什么？如果值可以是任何数字，我知道如何计算它，但是当只有 3 个值时我不知道如何计算。
例如，您可以压缩文件，您将获得仅 3 个符号的出色压缩级别。
如果你想努力工作，你可以做基本的 zip 算法：
您有 3 个值 -1、0 和 1。
然后你可以像这样定义一个事务树：
bit sequence - symbol
0 - 0
10 - 1
110 - -1
1110 - End of data
因此，如果你读到一个零，你就知道它是一个 0 符号，如果你读到一个 1，你必须读下一位才能知道它是否是 1，或者你必须再读一位才能知道它是否这是一个-1。
因此，如果您有一个系列 1,1,0,-1,0，它将翻译为：
101001100
如果这是您看到的所有数据，那么您有 9 位，因此您需要完成某些操作才能达到 16。
然后只需放置数据标记的结尾，然后再放置任何东西。
10100110 01110000
为此，您需要使用位运算符。
如果您知道其中任何符号的出现率高于其余符号，请使用位数较少的符号（例如 0 应代表最常用的符号）。
如果 -1、0 和 1 的可能性均等，则 n 个样本所需的位数公式为 ceiling(n log 23)。对于一个样本，正如您所指出的那样，您得到了两位，实际上浪费了一种状态，每个样本浪费了 0.4 多位。
事实证明，五个样本非常适合八位，其中 35 = 243，每个符号仅浪费大约 0.015 位。
您可以将额外的状态用作流结束符号。例如，您可以使用剩余 13 个状态中的五个来表示流结束，表示剩余 0、1、2、3 或 4 个样本。然后，如果它是 1、2、3 或 4，则这些样本还有一个字节。更好的做法是对 1 种情况使用三种状态，在该字节中提供样本。然后使用 13 种状态中的 7 种，需要一个字节来结束 0 和 1 情况下的流，以及两个字节来结束剩余 2、3 或 4 情况下的流。
如果 -1、0 和 1 的概率明显不同，则您可以对样本使用霍夫曼编码，以比上述 "flat" 情况更少的位数表示结果。然而，三个符号中的一个样本只有一个霍夫曼代码，这通常不会提供良好的性能。所以你会再次想要组合样本以获得更好的霍夫曼编码性能。 （或使用算术编码，但在这种情况下，这可能比必要的复杂得多。）因此，您可以再次将五个样本分组为 0..242 范围内的一个整数，然后霍夫曼编码这些样本，以及流的结尾只出现一次的符号（称为 243）。