信息检索：布尔检索-建立倒排索引(2)
倒排索引
倒排索引用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。假定我们有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)本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-01-05 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。