FOR压缩算法

一、倒排索引的数据结构

FOR压缩算法

 

 

 倒排表的压缩算法:FOR、RBM

词项索引的检索原理:FST

二、FOR压缩算法

FOR压缩算法

 

如上图,假设倒排表中最理想的一行id为1,2,3......100 W个连续数字

 图Ⅰ:若没有使用FOR压缩算法,则有100W个int类型的数字,1数字=4字节,则有400W字节,约占4M存储空间。1字节=8bit,则1int需要32bit,即3200Wbit

   若使用了FOR压缩算法,1-100W个连续数字,前后两个数字取差值,得到最终结果1,1,1.....1。100W个1,每个1需要2的0次方=1bit存储即可。最终结果为100Wbit,空间节省32倍

图Ⅱ:倒排表中id几乎不可能为连续数字,以73,300,302,332,343,372为例。6个int类型数字,不使用FOR压缩算法需要24byte

   若使用FOR压缩算法,先取差值得到73,227,2,30,11,29。这时得出最大差值为227,227在2的8次方范围内,这样就只需要每个分配2的8次方的空间

   在上面的基础上,我们发现有一个差值是2,这时FOR算法会根据一定原则自动分组,从而再次降低需要分配的存储空间

 

上一篇:转载:Windows Phone 8.1 投影我的屏幕使用教程


下一篇:云原生监控系统Prometheus——Prometheus Query Language