当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 阅读(2172)
评论(6) 编辑 收藏 引用