當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 閱讀(2237)
評論(6) 編輯 收藏 引用