写在前面：本博客只是非常非常粗糙的介绍以下tf-idf算法，倒排检索等信息检索知识，并借助这些知识来实现12万篇文档内容的查询，如想要深入了解请相关知识，请自行百度。
文件：en.txt 共计125298篇文档，要求为每个文件建立一个向量空间
要求：使用向量空间125298篇文档中查找相关文档，按照向量相似度进行排序模型，分别进行以上查询，取排名前20的文档doc id 和其文档内容。
在我们实现之前，我们先了解几个铺垫知识
- 倒排索引：
对于一个文档集中每个词（记作t），将其包含这个词的doc id记下。形成一张倒排记录表。
例如：
每个词后面的数字表示这个在对应编号的文档中包含了这个词。这样一来，当文本集数量极大时，想要查询一些词就可以通过倒排索引表获得包含它们的文档的编号。进而减少有关文档数量，更加便于进行具体的查询（比如and or not等）
借助倒排索引我们可以在接下来的12W篇文档的查询中减少查询量以提升速度。
2.tf-idf算法
在上面的倒排索引中，对于每个查询，我们返回的答案，它都是同一个地位的，它不存在一个评分机制，但事实是，对于每个查询，我们都希望返回的内容是排好序的，相关度高的放在上面。于是我们要给每个查询加一个权值。
我们先来看tf：tf是指单词出现的频率，称为词项频率。 称为单词t在文档d中出现的次数。但是两篇文档的相关度并不是与
成线性关系的。例：词A在文章1中出现了10次，在文章2中出现1次，你觉得它们的相关度差距真是10倍吗？肯定不是，于是我们对其进行取log运算，以降低它的权值。那么新的值的计算公式就是
这个 被称为对数词频 。
接下来我们再看以下稀有度 记为某个词在文档集中多少篇文档中出现，对于一个词，如果它在每篇文档中都出现，你说它重要吗？烂大街的N卡，肯定不重要！但是如果一个词只在那么一两篇文档中出现，你说这个词重要吗？肯定重要啊，馋哭萌新的SSR/SP卡，稀有的不得了，当然重要啊。那么还是那个问题，词A在1篇文档中出现了，词B在1000篇文档中出现了,你说它们的稀有度差距有1000倍吗，肯定不是。也是一个道理，我们还是对其进行取log运算，以降低它的权值。新的计算公式就是
注意这里的N是文档集中文档的数目。
一个词的tf-idf就是这两个词的乘积。
这里的 是tf-idf（别误会):
至此书写代码前的预备知识已经全部知道了。
思路：很明显，如果我们想平常那样把所有文章的所有词的tf-idf表做出来不仅时间消耗巨大，而且会做出一个超级多0的矩阵，这对空间的消耗也是巨大的，这肯定不是我们想看到的，那么有什么方法来优化呢？我们看到一篇文档与查询的相似度如果不为0，那么它里面一定包含了查询词，那么我们就可以借助倒排索引表，将包含查询词的文档全部返回，再在这些文档中计算相似度，这样计算的数量就大大减少了。至此代码也就可以写出来了。
import re
import math
import time
import sys
st = time.time()
'''下面是变量区'''
dict_letter = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11,
'm': 12,
'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23,
'y': 24, 'z': 25}
start_list = [] # 这个是每篇doc 的起始行
end_list = [] # 这是终止行
list_everydoc = [] # 这个是每篇文章的内容 这个肯定做好了
list_everydoc_set = [] # 存储着每篇文章中所有（不重复）单词
list_words_in_everydoc = []#每篇文章中的所有不重复单词
daopai = []#这也就开着玩玩，根本没用到，用到的是它的那种思想
set_jiao=set()#就是所有包含任一查询词的集合
list_haveword = [[] for i in range(0, 26)] # 这个是已经有了的单词，总词数是15554（这是包含了不是字母单词的）真正的总数更少。
list_index = [[] for j in range(0, 26)] # 这是对应词在倒排索引表中的位置
query=sys.argv[2]
list_query=query.split()
tot_num=len(list_query)
#下面是对查询词进行以下处理，首先要去除重复元素（用于查找），再就是计算查询词的tf-idf
set_query=set(list_query)
list_set_query=list(set_query)
list_set_query.sort()
query_vec=[list_query.count(list_set_query[i]) for i in range(0,len(list_set_query))]
print("查询词处理完毕，查询词矩阵建立完毕")
print("耗时：",time.time()-st)
#你要明白, tf-idf 里面有查询词就好了
tf = [[list_set_query[i],0] for i in range(0,len(list_set_query))]
list_ans=[]
'''变量开完了'''
pattern_start = re.compile(r'<doc id=\d+>')
pattern_end = re.compile(r'<\\\\doc>')
with open(sys.argv[1], "rb") as f:
f.seek(0)
w = f.readlines()
print("读完了")
print("耗时:", time.time() - st)
len_w = len(w) # 这个就是总行数
cnt = 0#文章编号从0开始
for i in range(0, len_w):
f=0
a = pattern_start.search(str(w[i]))
if a:
start_list.append(i)
continue
b = pattern_end.search(str(w[i]))
if b:
str_temp = str()
str_temp_split = list()
str_temp_split_temp = list()
end_list.append(i)
cnt += 1 # 文章篇数++
list_everydoc.append([])
for k in range(start_list[-1] + 1, end_list[-1]): # 当前文章的合成
str_temp += str(w[k]).strip()
str_temp.strip()
list_everydoc[-1].append(str_temp) # 把文章放入每篇文章内容中
str_temp_split_temp = str_temp.split()
for k in range(0, len(str_temp_split_temp)): # 一个憨批至极的分词
if (len(str_temp_split_temp[k].split('\\n\'b\'')) == 2):
str_temp_split.extend(str_temp_split_temp[k].split('\\n\'b\''))
elif (len(str_temp_split_temp[k].split('\\n\'b\"')) == 2):
str_temp_split.extend(str_temp_split_temp[k].split('\\n\'b\"'))
else:
str_temp_split.append(str_temp_split_temp[k])
'''这里的str_temp_split 就是本篇文章中 出现的单词'''
str_temp_split.sort()
for k in range(0,len(list_set_query)):
if(str_temp_split.count(list_set_query[k])!=0):#说明这个词在这里面出现过
set_jiao.add(cnt)
f=1
if(f):#如果这篇文章里面没有任何一个查询词，它就一点意义都没有
for k in range(0, len(list_set_query)):
if(str_temp_split.count(list_set_query[k])!=0):
tf[k].append(str_temp_split.count(list_set_query[k]))
tf[k][1]+=1
else:
tf[k].append(0)
list_everydoc_set.extend(str_temp_split)
list_words_in_everydoc.append(str_temp_split)
'''到这里，所有doc已经放入list_everydoc里面'''
#print(cnt,end=" ")
print('共有文章',cnt,"篇")
set_jiao=sorted(list(set_jiao))
# print(set_jiao)
# print(tf)
# print(query_vec)
print("已经获得交集")
print("耗时：",time.time()-st)
for i in range(0,len(set_jiao)):
list_ans.append([set_jiao[i]])
temp=0
for j in range(0,len(query_vec)):#j 对应的是词的位置
if(tf[j][i+2]!=0):
temp+=math.log10(cnt/tf[j][1])*(1+math.log10(tf[j][i+2]))*query_vec[j]
list_ans[-1].append(temp)
list_ans.sort(key=lambda x:-x[1])
print("相似度最高的",min(20,len(list_ans)),"篇文本编号是:")
for i in range(0,min(20,len(list_ans))):
print(list_ans[i][0])
print(str(list_everydoc[i-1][0]))
print("耗时:",time.time() - st,"秒")
写在最后：这个大作业应该是这个学期所有知识的一个大混合，前面的作业除了网页处理那次其他基本都是暴力的（文章篇数太少了），这次一看到12W的文档就知道肯定要优化，但真没想到这么难写。写了将近一个月，每周两节课（共计4H)一直在写。写了有四五个版本吧，都因为速度问题被淘汰了（其实就是自己傻了，非要去先算所有文档的tf-idf值，再求交集，再求相似度）。后来经过高人点拨，先求交集，直接飞起来。
不知道为什么，虽然别的同学都叫我用jieba库，但自己就是很莽撞的要自己手码，可能是因为ACM上菜的像狗(本来就是菜狗），希望有那么一点成就感吧。至此我也就完成了本学期的信息检索课的所有内容，嗯，很棒！抓紧时间，期末考试冲鸭！
京公网安备 11010502036488号