信息检索：布尔检索-建立倒排索引(2)
- 2019 年 11 月 21 日
- 笔记
倒排索引
倒排索引用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。假定我们有3个文档：
doc1 = ["1", "hello", "word", "i", "love", "dazhu"] doc2 = ["2", "hi", "i", "can", "speak", "love"] doc3 = ["3", "can", "i", "say", "hello", "make", "dazhu", "hi"]
将文档中的单词做为index，出现的文档号做为内容。比如：
hello -> [1,3]
代表hello出现在文档 1,3之中。 为每个单词都进行类似处理，最终获得的结果，就叫倒排索引。左边的所有单词项，称之为词典，而每个词典项（如'hello'），指向一个倒排记录表（如[1,3]）
建立过程
通过以下的步骤，可以为文档集建立倒排索引
获取每个文档的单词表（代码 give_word_list）
以doc1为例，经过处理，获得了如下单词表：
['dazhu', '1'] ['hello', '1'] ['i', '1'] ['love', '1'] ['word', '1']
后面的数字代表文档编号。例如['dazhu', '1']代表doc1包含dazhu这个词汇。
合并单词表并排序(代码 give_index)
同理，处理doc2和doc3,合并所有结果并排序，可得一个如下的列表：
['can', '2'] ['can', '3'] ['dazhu', '1'] ['dazhu', '3'] ['hello', '1'] ......
合并重复词典项（代码 merge_index）
由上可见，很多单词同时出现在不同的文档，所以这个列表的词典项有重复。因为已经进行排序，可以用简单的算法将相同词典项合并。 最终得到结果如下：
['can', ['2', '3']] ['dazhu', ['1', '3']] ['hello', ['1', '3']] ['hi', ['2', '3']] ['i', ['1', '2', '3']] ......
倒排索引至此已完全建立。
搜索
依照前文，我们已经可以求两个集合的交集并集，有了倒排索引，就能进行布尔查询。 例如，要求文档集中包含"i"和"can"的文档号。可进行如下操作： 1. 取出 i 的倒排记录表：['1', '2', '3'] 2. 取出 can 的倒排记录表：['2', '3'] 3. 对这两个集合求交集 4. 得返回值[2,3]
参考代码
import and_or def give_word_list(doc): result = [] for word_index in range(1,len(doc)): result.append([doc[word_index], doc[0]]) result.sort() return result def give_index(*docs): result = [] for doc in docs: word_list = give_word_list(doc) result += word_list result.sort(key=lambda x:x[0]) return result def merge_index(index_unmerge): result = [] temp_key = "" for item in index_unmerge: if item[0] != temp_key: result.append([item[0], [item[1]]]) temp_key = item[0] else: ## merge last item last_item = result[len(result) - 1] last_item[1].append(item[1]) return result def get_doclist_form_index(word, index): for item in index: if item[0] == word: return item[1] return [] doc1 = ["1", "hello", "word", "i", "love", "dazhu"] doc2 = ["2", "hi", "i", "can", "speak", "love"] doc3 = ["3", "can", "i", "say", "hello", "make", "dazhu", "hi"] index_unmerge = give_index(doc1, doc2, doc3) final_map = merge_index(index_unmerge) ## search doc include "i" "can" doclist_1 = get_doclist_form_index("i", final_map) doclist_2 = get_doclist_form_index("can", final_map) result = and_or.arr_and(doclist_1, doclist_2) print(result)
