信息检索-存储

压缩:

1. variable byte
2. gamma
3. zigzag

variable byte
将一个数据拆分为多个编码单位存储, 读的时候读若干个连续的编码单元组成一个数据, 如用一个字节做编码单位, 这个字节的最高位为0表示需要继续读取数据, 另外7个bit表示真实的数据, 需要和之后读取的数据结合起来使用, 当读到的字节的最高位为1, 表示是最后一个编码单元了, 可以将之前读到的数据结合在一起. 在实际中, 也可能用1做延续位标识, 用0作结束标识.

编码单位越大, 操作次数越小, 即解压缩越快, 但是压缩率低. 以8位, 一个字节作为编码单位, 是压缩率与解压缩速度的权衡.
通过1-5个字节来压缩四个字节的数据类型, 如int, 对于数值较小的int具有较好的压缩率, 对于较大的int, 或者负数(最高位-1), 压缩率较低.
例子: 以 0 做延续位标识.

    static List<Byte> encodeNumber(int num) {
//        byte i = (byte) 0x80;
        List<Byte> bytes = new LinkedList<>();
        while (true) {
            Byte b = (byte) (num & 0x7F);  // 获取数据低位
            bytes.add(b);                 // 写入, 数据低位在索引低位
            if ((num >>>= 7) == 0) {
                break;
            }
        }
        int lastOne = bytes.size() - 1;
        Byte aByte = bytes.get(lastOne);
        Byte last = (byte) (aByte + 128);
        bytes.set(lastOne, last);
        return bytes;
    }

    static List<Byte> encodeNumbers(int... nums) {
        List<Byte> bytes = new LinkedList<>();
        for (int num : nums) {
            bytes.addAll(encodeNumber(num));
        }
        return bytes;
    }

    static int[] decodeBytes(List<Byte> bytes) {
        List<Integer> ints = new LinkedList<>();
        int v = 0;
        int count = 0;
        // 先获取的是数据低位
        for (Byte b : bytes) {
            var flag = b & 0x80; // 1000 0000
            var ans = b & 0x7F;
            ans <<= (count++)*7;
            v |= ans;
            if (flag != 0) {
                ints.add(v);
                count = 0;
                v = 0;
            } else {

            }
        }
        return ints.stream().mapToInt(Integer::intValue).toArray();
    }