Lucene

2024-04-07

https://blog.51cto.com/sbp810050504/category6.html

https://www.cnblogs.com/forfuture1978/archive/2010/06/13/1757479.html

https://www.cnblogs.com/forfuture1978/p/3945755.html

https://juejin.cn/post/7166059264942243876

Lucene单值压缩

https://juejin.cn/post/7163560186823573517 lucene中所有的对单值（int,long,float.double)的压缩算法，可以一种类型针对不同场景有多种压缩算法，不过是什么类型的数值，在计算机中存储都是二进制存储，对其进行压缩或者编码，其实就是只保留有效信息，什么是有效信息，就是哪些bit位上面是1，所以所有的压缩编码都是设计一种策略，只保留有效信息，并且能够解码或者解压缩

vint编码： vint是对int类型进行压缩编码，vint中的v指的是variant（可变的），也就是vint编码的int存储空间的大小是以字节为单位的变长大小，vint编码结果中的每个字节分为两个部分：（1）第一位：标记位，如果是1，表示后面的字节也属于当前value的Vint编码结果，如果是0，则表示当前value的vint编码结果结束（2）剩下的7位：数据位，vint中所有的字节的低7位合起来就是完整的value的值 int 1314: 00000000 00000000 00000101 00100010 vint 1314: 10100010 00001010 vint编码只对正数有压缩作用 -10 编码： 11111111 11111111 11111111 11110110 11110110 11111111 11111111 11111111 00001111。 -10的vint编码需要5个字节。

public final void writeVInt(int i) throws IOException {
  // 如果i的最低7位置0后i非0  
  while ((i & ~0x7F) != 0) {
    // i & 0x7F：取最低7位
    // | 0x80 为flag为置1
    writeByte((byte) ((i & 0x7F) | 0x80));
    // i 右移7位
    i >>>= 7;
  }
  // 剩下不足7位的  
  writeByte((byte) i);
}

解码：

public int readVInt() throws IOException {
  byte b = readByte();
  // 如果 b >= 0, 说明flag位是0，当前要读的值只有一个字节。  
  if (b >= 0) return b;
  int i = b & 0x7F;
  b = readByte();
  i |= (b & 0x7F) << 7;
  if (b >= 0) return i;
  b = readByte();
  i |= (b & 0x7F) << 14;
  if (b >= 0) return i;
  b = readByte();
  i |= (b & 0x7F) << 21;
  if (b >= 0) return i;
  b = readByte();
  // 最后一个字节最多只有4位是有效的
  i |= (b & 0x0F) << 28;
  // 如果最后一个字节只有低四位有效，则说明格式正确  
  if ((b & 0xF0) == 0) return i;
  throw new IOException("Invalid vInt detected (too many bits)");
}

vlong 类型的变长编码原理同vint

ZigZag编码

zigzag是一种编码方式，可以用于int和long，原理一模一样编码

public static int zigZagEncode(int i) {
  // (i >> 31)：处理符号位，把所有的位都设置为符号位，等待和0（数据位左移1位空出来的0）做异或，就能保留符号位在最后一位
  // (i << 1)：处理数据位，数据为左移1位，把最后一位用来存符号位，其他数据为都和符号位做异或编码
  return (i >> 31) ^ (i << 1);
}

解码

public static int zigZagDecode(int i) {
  // (i >>> 1)：还原数据位，最后和符号位做异或解码
  // -(i & 1)：还原符号位，i的最后一位是符号位，该表达式把每一位都设置为符号位 
  return ((i >>> 1) ^ -(i & 1));
}

Lucene多值编码压缩算法

在lucene中，涉及到索引文件生成的时候，会看到比较多的PackedInts.Encoder,PackedWriter,DirectWriter,DirectMonotonicWriter等等对多个Long进行压缩编码解码的使用，下面主要是Lucene中对正整数（int或Long）数组压缩编码和解码的方式虽然限制了只对正整数有用，但是其它数值可以通过一些转化，先转化成正整数，然后再使用本文介绍的压缩编码，比如，负整数可以通过zigzag先做一次编码，float或者double可以通过把二进制int或者long来解析进行预处理