[技术]求助关于int[]数组压缩

开心延年 发布于 2014/01/29 15:34
阅读 742
收藏 1

有这样一组数据,他有行和列之分。

1.行号用docid来代替,且值是连续的,从1到最后一条记录。

2.列我们称为term,已经经过预处理,将数据进行了排重,并且从大到小进行编号 编成了term Num。

现在需要保存docid与term Num的关系。

将来会给出一些docid列表[大部分是所有的docid],查询到他们对应的termNum.

如何存储占用的空间能小点呢?

ps:数据特点

1.列(term)的值是有重复值的

2.docid与termNum 都是正整数,且都是连续的。

3.docid的范围为1000万到2000万

4.termNum的范文是1~2000万(看数据的重复情况)

5.查询的时候我事先是能够得到docid 列表的,所以存储只需要能根据docid得到termNum就行,docid本身的是否是有损存储不重要。

目前我的存储是采用倒排+PForDelta压缩的。实现参考的这里

过年这几天有闲暇时间,想改进一下这个的 索引,因为跟很多其他全内存有区别,数据是存储在文件里面的,如何快速的扫描文件对查询速度起决定性的作用,所以这个地方需要跳出之前的思维模式,【比如 说可以考虑有损压缩+校验补偿的方式 先取出个近似值,然后在根据结果重新获取真实值(返回的结果相比原始值会少很多)】。

之前还有一个思路是 将docid与termNum组合在一起,按照hash的方式存储到bitset里。这样1000万的数据占用空间很小

然后查询的时候根据给定的docid与每一个termNum进行组合,到bitset里进行匹配,如果匹配到了,则说明termNum就是对应的docid,但是这种情况适合termNum数量很小的情况,否则计算次数太多。


加载中
0
开心延年
开心延年
骑龙女(51999689)  16:01:33
不是 看不懂
我是说 一堆 term 可以用 一个数 表示了 
开心延年<myn@163.com>  16:02:22
现在已经是这样了啊 
骑龙女(51999689)  16:02:22
如果 给 term 用 质数 编码 的话
开心延年<myn@163.com>  16:02:58
现在已经对 term进行了排重 并且 按照 从小到大 进行了编码 
骑龙女(51999689)  16:03:09
不是 从小到大
1到n
1 3 5 7 9 都是 质数
开心延年<myn@163.com>  16:03:42

有什么用呢?
骑龙女(51999689)  16:03:41
只用这种 数 给 编码

开心延年<myn@163.com>  16:03:56
然后干啥呀 
骑龙女(51999689)  16:04:14
他们的加和 是唯一可以拆解的
然后 就用 质数的和 表示 一堆 term num 了
4 唯一 拆解为 1 + 3 
存储的时候 就存 4 不是 1 ,3
本本-新公民(306388406)  16:05:04
9是质数?
骑龙女(51999689)  16:05:04
然后 地方就少了
我说错了
9 不是

开心延年<myn@163.com>  16:05:40

我错了  刚才我不应该 那么态度不好 骑龙女 
骑龙女(51999689)  16:06:01
但是第 2000W 个 质数 估计 特别大了
我看也是
开心延年<myn@163.com>  16:06:21
好像是一个思路  不过我还没有想明白
骑龙女(51999689)  16:06:35
我觉得 不靠谱
呵呵
开心延年<myn@163.com>  16:06:56
那 2000W的时候这个数能特别大 
骑龙女(51999689)  16:07:08
是 啊
开心延年<myn@163.com>  16:07:32
我先吧你的聊天记录保留了  我在想想 
不过termNum不是唯一的 很烦人 
但是docid倒是唯一的 
骑龙女(51999689)  16:08:22
那应该也可以
这个得问问学数学得了

0
梁山伯喵
梁山伯喵

首先不是很理解你的查询要求。

不管docid还是termid的范围多大,实际上估计一个doc估计的term不会太多,应该是很稀疏的,如果平均100个 那么 总的元组量在10亿;不论正排还是倒排,一边肯定不用算了,直接用数组下标代替,另一边按照一个id 4个字节来算需要4G+ 这样,内存撑得住的。平均200个,用点压缩小伎俩 8G-。

如果量非常大得放磁盘,一定要避免多次随机查找;按照你的要求应该是根据docid[]数组来查出所有的termid列表,应该是用正排才对吧。如果输入的docid[] 范围太散 还是必须随机到全部索引块,相当于每次查询磁盘都要进行大量交换,按照普通机械磁盘100M每秒的极限速度基本不可行。

不太理解你的要求,只能这么回复了

0
八风不动
八风不动

设计一个算法,让docid有序的情况下,termnum尽量有序或分段有序。

然后对termnum做游程编码。

返回顶部
顶部