您的位置: 首页  >  文章  >  倒排索引的实现

倒排索引的实现

分类: 文章 • 2025-01-09 14:21:58

https://blog.****.net/xn4545945/article/details/8791484

倒排索引（英语：Inverted index），也常被称为反向索引、置入档案或反向档案，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。


倒排索引分析：

以英文为例，下面是要被索引的文本：
T0 = "it is what it is" 
T1 = "what is it" 
T2 = "it is a banana" 
对相同的文字，我们得到后面这些完全反向索引，有文档数量和当前查询的单词结果组成的的成对数据。 同样，文档数量和当前查询的单词结果都从零开始。所以，"banana": {(2, 3)} 就是说 "banana"在第三个文档里(T2)，而且在第三个文档的位置是第四个单词(地址为 3)。
"a":        {(2, 2)}
"banana": {(2, 3)}
"is":       {(0, 1), (0, 4), (1, 1), (2, 1)}
"it":       {(0, 0), (0, 3), (1, 2), (2, 0)} 
"what":   {(0, 2), (1, 0)}
如果我们执行短语搜索"what is it" 我们得到这个短语的全部单词各自的结果所在文档为文档0和文档1。但是这个短语检索的连续的条件仅仅在文档1得到。


倒排索引的Python实现：

[python] view plain copy
  1. #-------------------------------------------------------------------------------  
  2. # Name:        InvertedIndex  
  3. # Purpose:     倒排索引  
  4. # Created:     02/04/2013  
  5. # Copyright:   (c) neng 2013  
  6. # Licence:     <your licence>  
  7. #-------------------------------------------------------------------------------  
  8. import re  
  9. import string  
  10. #对199801.txt进行处理, 去除词性标注以、日期及一些杂质. (保留段落结构)  
  11. #输入:199801.txt  
  12. #输出:199801_new.txt  
  13. def pre_file(filename):  
  14.     print("读取语料库文件%r....."%filename)  
  15.     src_data = open(filename).read()  
  16.     #去除词性标注、‘19980101-01-001-001’、杂质如‘[’、‘]nt’  
  17.     des_data =re.compile(r'(\/\w+)|(\d+\-\S+)|(
    )|()|(
    \S+)').sub('',src_data)  
  18.     des_filename = "199801_new.txt"  
  19.     print("正在写入文件%r....."%des_filename)  
  20.     open(des_filename,'w').writelines(des_data)  
  21.     print("处理完成!")  
  22.   
  23.   
  24. #建立倒排索引  
  25. #输入:199801_new.txt  
  26. #输出:my_index.txt  格式(从0开始): word (段落号,段落中位置) ..  
  27. def create_inverted_index(filename):  
  28.     print("读取文件%r....."%filename)  
  29.     src_data = open(filename).read()  
  30.     #变量说明  
  31.     sub_list = [] #所有词的list,  用来查找去重等  
  32.     word = []     #词表文件  
  33.     result = {}   #输出结果 {单词:index}  
  34.   
  35.     #建立词表  
  36.     sp_data = src_data.split()  
  37.     set_data = set(sp_data) #去重复  
  38.     word = list(set_data) #set转换成list, 否则不能索引  
  39.   
  40.     src_list = src_data.split("\n") #分割成单段话vv  
  41.     #建立索引  
  42.     for w in range(0,len(word)):  
  43.         index = []  #记录段落及段落位置 [(段落号,位置),(段落号,位置)...]  
  44.         for i in range(0,len(src_list)):  #遍历所有段落  
  45.             #print(src_list[i])  
  46.             sub_list = src_list[i].split()  
  47.             #print(sub_list)  
  48.             for j in range(0,len(sub_list)):  #遍历段落中所有单词  
  49.                 #print(sub_list[j])  
  50.                 if sub_list[j] == word[w]:  
  51.                     index.append((i,j))  
  52.             result[word[w]] = index  
  53.   
  54.     des_filename = "my_index.txt"  
  55.     print("正在写入文件%r....."%des_filename)  
  56.     #print(result)  
  57.     #print(word)  
  58.     #print(len(word))  
  59.     writefile = open(des_filename,'w')  
  60.     for k in result.keys():  
  61.         writefile.writelines(str(k)+str(result[k])+"\n")  
  62.     print("处理完成!")  
  63.   
  64. #主函数  
  65. def main():  
  66.     #pre_file("199801.txt") #初步处理语料库, 得到199801_new.txt  
  67.     #根据199801_new.txt建立索引, 得到myindex.txt(由于199801_new.txt太大, 建立索引时间太长, 因此只截取一部分放入199801_test.txt)  
  68.     create_inverted_index("199801_test.txt")  
  69.   
  70. #运行  
  71. if __name__ == '__main__':  
  72.     main()  


主要算法说明：

输入: 待建立索引的文件（199801_test.txt）

输出: 索引文件（my_index.txt）

建立倒排索引的算法采用全文搜索，然后记录其段落号与在段落中的位置。


199801_test.txt文件：

倒排索引的实现

my_index.txt文件：

倒排索引的实现


相关推荐