当前位置： 代码迷 >> 综合 >> weak-and算法原理演示（wand）
  详细解决方案

weak-and算法原理演示（wand）

热度：14   发布时间：2024-01-12 07:56:47.0

weak-and算法原理演示（wand）

分类： 算法 2013-01-14 11:38 2147人阅读 评论(2) 收藏 举报
wand 信息检索 weak-and
推荐一个在信息检索中用到的weak-and算法，这个算法在广告系统中有成熟的应用。
 
简单来说，一般我们在计算文本相关性的时候，会通过倒排索引的方式进行查询，通过倒排索引已经要比全量遍历节约大量时间，但是有时候仍然很慢。
原因是很多时候我们其实只是想要top n个结果，一些结果明显较差的也进行了复杂的相关性计算，而weak-and算法通过计算每个词的贡献上限来估计文档的相关性上限，从而建立一个阈值对倒排中的结果进行减枝，从而得到提速的效果。
 
从我实际测试的结果看，对于短文本的效果不如长文本的明显，但是在视频的电影数据上面看，仍然减少了50%的耗时（top 100），并且该算法可以通过牺牲精度来进一步提升速度，非常不错。
 
以下代码是一个算法原理演示，实现了主要的算法逻辑以验证算法的有效性，供大家参考，该实现优化了原始算法的一些逻辑尽量减少了无谓的循环

[python] view plain copy
  1. #!/usr/bin/python  
  2. #wangben updated 20130108  
  3.   
  4. class WAND:  
  5.     '''''implement wand algorithm'''  
  6.     def __init__(self, InvertIndex, last_docid):  
  7.         self.invert_index = InvertIndex #InvertIndex: term -> docid1, docid2, docid3 ...  
  8.         self.current_doc = 0  
  9.         self.current_invert_index = {}  
  10.         self.query_terms = []  
  11.         self.threshold = 2  
  12.   
  13.         self.sort_terms = []  
  14.         self.LastID = 2000000000 #big num  
  15.         self.debug_count = 0  
  16.         self.last_docid = last_docid  
  17.   
  18.     def __InitQuery(self, query_terms):  
  19.         '''''check terms len > 0'''  
  20.         self.current_doc = -1  
  21.         self.current_invert_index.clear()  
  22.         self.query_terms = query_terms  
  23.         self.sort_terms[:] = []  
  24.         self.debug_count = 0  
  25.   
  26.         for term in query_terms:  
  27.             #initial start pos from the first position of term's invert_index  
  28.             self.current_invert_index[term] = [ self.invert_index[term][0], 0 ] #[ docid, index ]  
  29.       
  30.     def __SortTerms(self):  
  31.         if len(self.sort_terms) == 0:  
  32.             for term in self.query_terms:  
  33.                 if term in self.current_invert_index:  
  34.                     doc_id = self.current_invert_index[term][0]  
  35.                     self.sort_terms.append([ int(doc_id), term ])  
  36.         self.sort_terms.sort()  
  37.               
  38.   
  39.     def __PickTerm(self, pivot_index):  
  40.         return 0  
  41.   
  42.     def __FindPivotTerm(self):  
  43.         score = 0  
  44.         for i in range(0, len(self.sort_terms)):  
  45.             score += 1  
  46.             if score >= self.threshold:  
  47.                 return [ self.sort_terms[i][1], i]  
  48.   
  49.         return [ None, len(self.sort_terms) ]  
  50.   
  51.     def __IteratorInvertIndex(self, change_term, docid, pos):  
  52.         '''''move to doc id > docid'''  
  53.         doc_list = self.invert_index[change_term]  
  54.         i = 0  
  55.         for i in range(pos, len(doc_list)):  
  56.             if doc_list[i] >= docid:  
  57.                 pos = i  
  58.                 docid = doc_list[i]  
  59.                 break  
  60.   
  61.         return [ docid, pos ]  
  62.   
  63.     def __AdvanceTerm(self, change_index, docid ):  
  64.         change_term = self.sort_terms[change_index][1]  
  65.         pos = self.current_invert_index[change_term][1]  
  66.         (new_doc, new_pos) = \  
  67.             self.__IteratorInvertIndex(change_term, docid, pos)  
  68.           
  69.         self.current_invert_index[change_term] = \  
  70.             [ new_doc , new_pos ]  
  71.         self.sort_terms[change_index][0] = new_doc  
  72.           
  73.           
  74.     def __Next(self):  
  75.         if self.last_docid == self.current_doc:  
  76.             return None  
  77.               
  78.         while True:  
  79.             self.debug_count += 1  
  80.             #sort terms by doc id  
  81.             self.__SortTerms()  
  82.               
  83.             #find pivot term > threshold  
  84.             (pivot_term, pivot_index) = self.__FindPivotTerm()  
  85.             if pivot_term == None:  
  86.                 #no more candidate  
  87.                 return None  
  88.               
  89.             #debug_info:  
  90.             for i in range(0, pivot_index + 1):  
  91.                 print self.sort_terms[i][0],self.sort_terms[i][1],"|",  
  92.             print ""  
  93.                   
  94.   
  95.             pivot_doc_id = self.current_invert_index[pivot_term][0]  
  96.             if pivot_doc_id == self.LastID: #!!  
  97.                 return None  
  98.   
  99.             if pivot_doc_id <= self.current_doc:  
  100.                 change_index = self.__PickTerm(pivot_index)  
  101.                 self.__AdvanceTerm( change_index, self.current_doc + 1 )  
  102.             else:  
  103.                 first_docid = self.sort_terms[0][0]  
  104.                 if pivot_doc_id == first_docid:  
  105.                     self.current_doc = pivot_doc_id  
  106.                     return self.current_doc  
  107.                 else:  
  108.                     #pick all preceding term  
  109.                     for i in range(0, pivot_index):  
  110.                         change_index = i  
  111.                         self.__AdvanceTerm( change_index, pivot_doc_id )  
  112.       
  113.     def DoQuery(self, query_terms):  
  114.         self.__InitQuery(query_terms)  
  115.           
  116.         while True:  
  117.             candidate_docid = self.__Next()  
  118.             if candidate_docid == None:  
  119.                 break  
  120.             print "candidate_docid:",candidate_docid  
  121.             #insert candidate_docid to heap  
  122.             #update threshold  
  123.         print "debug_count:",self.debug_count  
  124.           
  125.   
  126. if __name__ == "__main__":  
  127.     testIndex = {}  
  128.     testIndex["t1"] = [ 0, 1, 2, 3, 6 , 2000000000]  
  129.     testIndex["t2"] = [ 3, 4, 5, 6, 2000000000 ]  
  130.     testIndex["t3"] = [ 2, 5, 2000000000 ]  
  131.     testIndex["t4"] = [ 4, 6, 2000000000 ]  
  132.   
  133.     w = WAND(testIndex, 6)  
  134.     w.DoQuery(["t1", "t2", "t3", "t4"])  

输出结果中会展示next中循环的次数，以及最后被选为candidate的docid
这里省略了建立堆的过程，使用了一个默认阈值2作为doc的删选条件，候选doc和query doc采用重复词的个数计算UB，这里只是一个算法演示，实际使用的时候需要根据自己的相关性公式进行调整（关于Upper Bound需要注意的是，需要在预处理阶段，把每个词可能会共现的最大相关性的分值计算出来作为该词的UB）

输出结果如下，展示了docid的相关变化过程，以及最后的循环次数14次

[html] view plain copy
  1. 0 t1 | 2 t3 |   
  2. 2 t1 | 2 t3 |   
  3. candidate_docid: 2  
  4. 2 t1 | 2 t3 |   
  5. 2 t3 | 3 t1 |   
  6. 3 t1 | 3 t2 |   
  7. candidate_docid: 3  
  8. 3 t1 | 3 t2 |   
  9. 3 t2 | 4 t4 |   
  10. 4 t2 | 4 t4 |   
  11. candidate_docid: 4  
  12. 4 t2 | 4 t4 |   
  13. 4 t4 | 5 t2 |   
  14. 5 t2 | 5 t3 |   
  15. candidate_docid: 5  
  16. 5 t2 | 5 t3 |   
  17. 5 t3 | 6 t1 |   
  18. 6 t1 | 6 t2 |   
  19. candidate_docid: 6  
  20. debug_count: 14  

  相关解决方案

代码迷 - 您身边的软件异常，代码异常，编程异常助手（发现，解决，分享）
Copyright © 2009-2013 DAIMAMI.COM. All rights reserved.