记录学习过程中的点点滴滴
google sparse hash set/map
三 19th
google开源了hashtables的包,包括两个部分:
- sparse, 比较节省空间space-efficient;
- dense, 高效的查询效率 time-efficient;
同时接口兼容SCI的hash_map和hash_set, 并且提供了序列化的功能,非常赞~
下面是其官方的性能测试数据:可以看到sparse_hash_map比stl::map和hash_map节省2/3的空间,而dense_hash_map具备较高的查询,删除, insert性能,可以根据具体的应用
来使用不同的数据结构。
下载地址:http://code.google.com/p/sparsehash/
doc : http://google-sparsehash.googlecode.com/svn/trunk/doc/
SPARSE_HASH_MAP: map_grow 665 ns map_predict/grow 303 ns map_replace 177 ns map_fetch 117 ns map_remove 192 ns memory used in map_grow 84.3956 Mbytes DENSE_HASH_MAP: map_grow 84 ns map_predict/grow 22 ns map_replace 18 ns map_fetch 13 ns map_remove 23 ns memory used in map_grow 256.0000 Mbytes STANDARD HASH_MAP: map_grow 162 ns map_predict/grow 107 ns map_replace 44 ns map_fetch 22 ns map_remove 124 ns memory used in map_grow 204.1643 Mbytes STANDARD MAP: map_grow 297 ns map_predict/grow 282 ns map_replace 113 ns map_fetch 113 ns map_remove 238 ns memory used in map_grow 236.8081 Mbytes
google早期的索引结构介绍
三 1st
最近一直在做索引压缩方面的事情,无意中看到了Jeff Dean大牛分享的google早期的索引结构,对于我们这种刚刚起步的搜索公司,还是很有启发意义的,收获还是比较大,所以就简单记录下。
1. 索引压缩常用的压缩算法
淘宝的一篇技术blog分享了一些比较常用的压缩算法:
- varint (变长压缩): 字节对齐,压缩比不高
- group varint: 变长压缩的变形,比varint的解压速率高很多,这里有它的实现
- Gamma: 对比较小的数字压缩比会比较高,将数值分为两个部分: 一元编码(num_bits)+二进制编码
- Simple9 + simple16: 对于32bit的空间进行组织,可存储多个数值
- PForDelta + NewPForDelta: 比较新的压缩算法,压缩比和解压缩比都比较高效,适合于docid_delta的压缩
关于这些算法的相关介绍可以看下www.wikipedia.org,或者搜下对应的paper.
2. Google的索引结构
可以看到,对于token的doclist是以Block的方式进行组织的,如果doclist比较长,还会使用skip table来快速查找;
Block的组织方式:
a. block header: 使用变长存储与上一个block的delta, 并存储block 实际的存储长度(可能是作为验证)
b. 第二行使用Gamma来压缩编码类型及在block中出现的docs的数目(因为这些数值都比较小)
c. 使用Rice压缩对应docld delta, 其实这里可以使用比较新的压缩算法PFDelta,更高效一些
d. 使用Gamma来压缩对应token在doc中出现的frequence, 即hit的数目
e. 使用length-limit Huffman 来存储Hit Attribute信息,这里主要是利用Attribute的重复的比例会很高,也就是说大部分hit attribute
都会是相同的,所以用到了Huffman压缩,然后对length进行了限制
f: positions用Huffman-Int 来压缩位置信息,由于position分布不确定性很多,对position的压缩一直是业界的难题,压缩比不会很高。
Huffman-Int : 类似于Gamma压缩,但是对于一元编码部分,使用了Huffman code.
优化
这里其实可以将doclist和hit 信息进行分离存储,因为只有在打分的时候才会用到hit的相关信息,访问次数会比较少,而doclist就会访问比较频繁
可以对其进行Cache,这样Cache命中率会更高一些
从 Google 代码库找到的好东西
三 2nd
Google Code托管——SVN
十二 31st
1. 进入http://code.google.com/ 用Google帐户登录(推荐使用gmail邮箱)。然后点击>Project Hosting
2. 进入>> http://code.google.com/hosting/ 然后点击>Create a new project
3. 填入信息:
写入项目名,描述,两个选择项,写入标签,点击确定。就可以了
4. 提交成功后,选择菜单的Source(其中有https上传协议路径需要拷贝一份,还有一个上传密码)。
5. 打开MyEclipse,打开需要上传的项目,点鼠标右键->team->share Project->svn,写入https路径,下一步,输入Google账号和上传密码,起个名,finish。
6.如果一切顺利,会自动生成一个项目目录,可以查看所有项目文件。然后进入搭建项目界面,点鼠标右键->team->commit。然后开始上传项目。
7,搭建完成。
8.如果想查看自己的项目,可以用浏览器登陆https的路径,输入Google账号和上传密码,如果成功就可以看到含有项目名称的目录。
近期评论