如何高效压缩存储仅含1、0、-1值的超大规模时间序列？

Hey there, this is a really solid problem to tackle—optimizing storage for ultra-large-scale time series with only three possible values. Your intuition about using group state IDs (assigning unique numbers to permutations of value blocks) is exactly the right direction, as it beats the basic 2-bit-per-sample approach by a wide margin. Let’s dive into the details:

First, Let’s Quantify the Baseline Bottleneck #

Each sample has 3 possible states, so the naive approach uses 2 bits per sample (since 2²=4 ≥ 3). For a single 40k-minute sequence, that’s:
40000 * 2 bits = 80000 bits = ~9.76 KB
Multiply by 1 billion sequences, and you’re looking at ~9.16 PB of storage—way too bulky for practical use. We need a smarter encoding scheme.

Core Logic of Group State ID Encoding #

Your idea boils down to mapping blocks of samples to unique integer IDs, leveraging the fact that the total number of unique states for a block of length k is 3ᵏ. Instead of storing k*2 bits for the block, we only need ⌈log₂(3ᵏ)⌉ bits to store the ID.

Example: k=16 (16-minute blocks) #

• Naive block storage: 16*2 = 32 bits
• Total unique states: 3¹⁶ = 43,046,721
• Bits needed for ID: ⌈log₂(43046721)⌉ = 26 bits (since 2²⁵ < 43M < 2²⁶)
• Per-block savings: 6 bits, which translates to 40000/16 *26 = 65000 bits = ~7.98 KB per sequence—20% smaller than the baseline.

Example: k=20 #

• Total states: 3²⁰ = 3,486,784,401
• Bits needed: 32 bits (fits in a 4-byte integer)
• Naive storage per block: 20*2=40 bits
• Per-sequence storage: 40000/20 *32 = 64000 bits = ~7.81 KB—even more efficient, but with a tradeoff (see next section).

Choosing the Optimal Block Length k #

You need to balance two factors:

• Encoding Efficiency: The larger k is, the closer the average bits per sample gets to the theoretical entropy limit of log₂(3) ≈1.585 bits (way better than 2 bits).
• Lookup Table Overhead: The number of unique states grows exponentially with k. For k=16, the lookup table (mapping blocks to IDs) is ~165MB (43M entries *4 bytes each)—manageable. For k=20, it jumps to ~13GB (3.4B entries *4 bytes), which might strain memory in large systems.

Recommended Sweet Spots:

• k=16: Balances efficiency and memory usage, perfect for most large-scale storage systems.
• k=12: If memory is tight—3¹²=531,441 states, lookup table is only ~2MB, and average bits per sample is 19/12≈1.583 (almost hitting the entropy limit).

Practical Implementation Details #

1. Block ↔ ID Mapping #

Convert each block to a base-3 number, then to a decimal ID (and vice versa for decoding):

• Map -1→0, 0→1, 1→2 (turns your sequence into a base-3 digit sequence)
• Convert the base-3 sequence to a decimal integer (this is your unique ID)

Here’s a quick Python example for k=16:

# Precompute powers of 3 for fast encoding
power_of_3 = [3**i for i in range(16)]

def encode_block(block):
    """Encode a 16-element {-1,0,1} block to an integer ID"""
    id_num = 0
    for idx, val in enumerate(block):
        mapped_val = val + 1  # Shift values to 0,1,2
        id_num += mapped_val * power_of_3[15 - idx]
    return id_num

def decode_block(id_num, k=16):
    """Decode an integer ID back to a {-1,0,1} block"""
    block = []
    remaining = id_num
    for _ in range(k):
        remainder = remaining % 3
        block.append(remainder - 1)  # Shift back to -1,0,1
        remaining = remaining // 3
    return block[::-1]  # Reverse to restore original order

2. Handling Non-Integer Block Lengths #

40k minutes is exactly divisible by 16 (40000/16=2500), so no leftover samples. For other k values (like k=12, 40000=12*3333+4), handle the final partial block with either:

• Basic 2-bit encoding for the leftover 4 samples (8 bits)
• A smaller block size (like k=4, which needs ⌈log₂(3⁴)⌉=7 bits—saves an extra bit)

3. Batch Storage Optimization #

If your sequences have repeated block states across many sequences, you can aggregate sequences by block IDs: store each unique ID once, plus a list of sequence IDs that contain that block. This can drastically reduce storage if there’s high redundancy across sequences.

4. Performance Considerations #

The encoding/decoding logic runs in O(k) time per block, which is blazingly fast even for 1B sequences. Precomputing the power-of-3 table avoids redundant calculations and keeps operations snappy.

Bonus Optimization Ideas #

• Entropy Coding: If your data has skewed distribution (e.g., most samples are 0), run Huffman or LZ77 encoding on top of the block IDs. Note that block coding already gets very close to the entropy limit, so gains will be small—but every bit counts for 1B sequences.
• Differential Coding (Conditional): If adjacent samples rarely change (e.g., long runs of 0), store the difference between consecutive samples instead of raw values. But be careful: differences can be {-2,-1,0,1,2} (5 states), which has higher entropy (log₂(5)≈2.32 bits) than raw values—only use this if your data has extremely low volatility.

内容的提问来源于stack exchange，提问作者PaeneInsula