用go构建个简单的搜索（四）哥伦布Golomb编解码实现

用go构建个简单的搜索（一）

用go构建个简单的搜索（二）最简单的索引文件

用go构建个简单的搜索（三）对上篇索引文件优化

上篇做的差值是以第一个为准，可以以上个数据为差值可以进一步压缩

Golomb编码

主要是压缩索引的,这里实现个demo，使用应用下篇再写文件解析

算法介绍

将数据x分为商q和余数r  x=m*q+r
          q进行unary编码（1的个数表示值结尾用0 例如：10=11111111110）
          r这里有个参照值 b=log2(m) 向上取值 
                         t=2^b-m
                         
                         0 <= r < t 宽度为b-1的二进制 r
                         t <= r < m 宽度为b的二进制   r+t

编码和解码例子

声明一组数：[15,22,25,42]

m取中位数 m=（15+22+25+42）/4=26 -》b=5=2^5=32 t=32-26=6

x	q	r	t	结果
15	0	15	>6	010101
22	0	22	>6	011100
25	0	25	>6	011111
42	1	16	>6	1010110

如何解码，上面的数字合起来就是 01010101 11000111 11101011 0

• 010101

• 首先查找第一个(unary解码)为0的计算前N-1个1取数商值
• 然后b是知道的 再取b-1个数 1010=11>6 再取一位10101=21-6=15
• 第一个值就是0*26+15=15

• 01 11000

• 第二个(unary解码) 商 0
• 余数 1110=13>6 再取一位11100=28-6=22
• 第二个数就是0*26+22=22

剩下的一次取数

编解码实现

前面用的uint16数据短，长度目前改用的是int操作的

效果

实现

/*
 *b=log2(m) 向上取值
 *t=2^b-m
 */
func getBT(number int) (int, int) {
	b := int(math.Ceil(math.Log2(float64(number))))
	t := int(math.Pow(2, float64(b))) - number
	return b, t
}

/*
 * 前面是bit 1 以 0结尾
 * uint16 最多表示15
 * 15*65535=983025
 */
func getUnary(number int) int {
	num := 0
	for i := 0; i < int(number); i++ {
		num = num | 1<<i
	}
	return num
}

/**
 *余数处理
 *0 <= r < t 宽度为b-1的二进制 r
 *t <= r < m 宽度为b的二进制   r+t
 */
func getGolombEncode(quotient int, remainder int, b int, t int) int {
	quotientU := getUnary(quotient)
	if remainder >= t {
		remainder += t
	} else {
		b -= 1
	}
	return quotientU | (remainder << (int(quotient + 1)))
}

/**
 * 反解析
 */
func getGolombDecode(num int, b int, t int, m int) int {
	temp := 0
	i := 0
	for ; i < 32; i++ {
		if (num & (1 << i)) > 0 {
			temp++
		} else {
			break
		}
	}
	remainder := int(num) >> (i + 2) & (1<<(b-1) - 1)
	//fmt.Printf("%d\n", remainder)
	if remainder >= t {
		remainder = int(num)>>(i+1)&(1<<(b)-1) - t
	}
	fmt.Printf("商：%d,余数：%d\n", temp, remainder)
	return temp*m + remainder
}