foxriver
Keep It Simple and Stupid.
posts - 12,  comments - 39,  trackbacks - 0

当QQ群聊天记录日积月累,达到一定数量级的时候,要查找某些单一文字,往往会花费10几秒甚至几分钟才有反应。除去磁盘读取的时间,是否对聊天记录做一个全局索引也是个重要的优化,这篇文章就是为了优化文本查找速度,介绍一个最简单的方法。

试着把QQ每条聊天记录看成SQL里单一记录,对单条记录做全文索引。这里用的方法是bit位快速匹配。假设一条聊天记录是"test", 转换成16进制,就是"74 65 73 74", 对单条记录,定义196位bit空间(占用24字节),定义为数组A, 然后按bit层(注意不是字节)做or操作:  (A = A or N, 把A的第N个bit设置为1)

初始状态:
A = 0;        // 【0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00】

A = A or 0x74; // 【0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x10,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00】
A = A or 0x65; // 【0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x20,0x00,0x10,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00】
A = A or 0x73; // 【0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x20,0x00,0x18,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00】
A = A or 0x74; // 【0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x20,0x00,0x18,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00】

使用时,给需要查找的字符串建立相同大小的bit索引B,对查找数据"es"做相同处理:

B = 0;
B = B or 0x65; // 【0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x20,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00】
B = B or 0x73; // 【0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x20,0x00,0x08,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00】

然后把A和B做and操作,如果结果为空(完全没有交集),则可以快速跳过这条记录,而不用去判断实际内容中是否包含了查找文本。

if (B & A)
{
  // 两者索引存在交集,有一定的可能性,处理进一步文字查找操作。
}
else
{
  // 两者不可能有包含关系,直接跳过本条记录内容,判断数据库下一条记录。
}

原理很简单,就是求两者的交集,但往往简单的索引,能带来意想不到的速度提升。实际测试中,只要输入的查找文本比较短小,大约30%~60%上下浮动的数据都能直接略过,大大节省了查找总耗时。

本人实现中,中文的查找方法相当于两个单字节的英文,为了最大效率利用空间,用算法把中文每个BYTE都压缩在196bit之内。

posted on 2011-01-14 01:22 foxriver 阅读(2047) 评论(6)  编辑 收藏 引用

FeedBack:
# re: C++ 【原创算法】实现一个最简单bit位全文查找索引。
2011-01-14 09:30 | atyuwen
你这个不就是bloom filter的山寨版么,而且hash时并没有考虑到pattern中的字母顺序,结果退化成了一个普通的字符集求交。  回复  更多评论
  
# re: C++ 实现一个最简单bit位全文查找索引。
2011-01-14 09:42 | foxriver
@atyuwen

啥,已经有人实现过了?有点杯具,去找来bloom filter研究研究。  回复  更多评论
  
# re: C++ 【山寨算法】实现一个最简单bit位全文查找索引。
2011-01-14 12:03 | waiting4you
和布隆算法还是不太一样的,有创意~~
只是有个地方没看懂,A = A or 0x74怎么运算呢?怎么得到...0x16...的?谢谢  回复  更多评论
  
# re: C++ 【山寨算法】实现一个最简单bit位全文查找索引。
2011-01-14 14:28 | foxriver
@waiting4you

杯具,测试数据写错了,是十进制的结果,被我写成了16进制,已经修正。感谢。  回复  更多评论
  
# re: C++ 【山寨算法】实现一个最简单bit位全文查找索引。
2011-01-14 21:50 | qiuxiafei
额 确实是bloomfilter....
不过还是很赞 异曲同工  回复  更多评论
  
# re: C++ 【山寨算法】实现一个最简单bit位全文查找索引。
2011-02-12 17:57 | 随便写写~~
@waiting4you
尝试做了下,还不错~~

public void or(byte[] input, byte index) {
int move = index % 8;
int fix = index / 8;
input[fix] |= (byte)(1 << move);
}

public bool and(byte[] input1, byte[] input2) {
for (int i = 0; i < input1.Length; i++) {
int x = input1[i] & input2[i];
if (x > 0)
return true;
}
return false;
}  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2022年8月>
31123456
78910111213
14151617181920
21222324252627
28293031123
45678910

常用链接

留言簿(3)

随笔档案

文章档案

相册

1

搜索

  •  

最新评论

阅读排行榜

评论排行榜