新闻资讯

跟随 在Python中实现具有排名的搜索引擎

2017-06-11 14:02:58 Ipbrother.zmz

这可能只是我,但我每次使用Quora的时候,我最终看到这样至少一个问题这一个:有人质疑谷歌是如何工作的,以及在搜索它们如何“打败”谷歌。大多数问题不像这个问题那样粗暴或误导,但他们都表达了类似的观点,在这样做的时候,他们背叛了对搜索引擎如何工作的重大误解。

但是尽管Google的复杂性非常高,但是搜索引擎的基本概念完全是通过与文本查询的相关性进行匹配和排名的结果并不是特别困难的,任何具有基本编程经验的人都可以理解。我不认为在这一点上可以超越Google搜索,但是制作搜索引擎是一个非常可以达到的目标,实际上是一个很有启发性的练习,我建议尝试。

这就是我在这篇博客文章中将要描述的内容:如何为能够处理标准查询的本地文本文件制作搜索引擎(文档中至少有一个单词出现在文档中)和短语查询(整个短语出现在文本中)并且可以使用基本的tf-idf方案进行排序。

开发这两个主要阶段:构建索引,然后使用索引来回答查询。然后,我们可以添加结果排名(tf-idf,PageRank等),查询/文档分类,也可以添加一些机器学习来跟踪用户过去的查询和选择的结果,以提高搜索引擎的性能。

所以不用多说,让我们开始吧!

建立指数

因此,构建文本搜索引擎的第一步是组装一个反向索引。让我解释一下究竟是什么。反向索引是将令牌映射到他们出现的文档的数据结构。在这种情况下,我们可以将一个令牌简单地视为一个单词,所以最基本的倒排索引只是一个单词,并返回给我们显示的文件列表。

首先,我们必须解析和标记(分词)我们的文档语料库。我们将按照如下方式执行此操作:对于我们要添加到索引中的每个文档,我们将删除所有标点符号并将其分割为空格,并创建一个临时散列表,将文件名映射到其令牌列表。我们会反复转换这个哈希表,直到我们达到上述最后的倒排索引(还有一个额外的复杂性,但我会解释一下)。以下是执行初始文本过滤的代码:

def process_files(filenames):
	file_to_terms = {}
	for file in filenames:
		pattern = re.compile('[\W_]+')
		file_to_terms[file] = open(file, 'r').read().lower();
		file_to_terms[file] = pattern.sub(' ',file_to_terms[file])
		re.sub(r'[\W_]+','', file_to_terms[file])
		file_to_terms[file] = file_to_terms[file].split()
	return file_to_terms

我没有在这里做的两件事,但我建议做的是删除所有的禁用词(像“the”,“and”“a”等等,不会增加文档的相关性),并阻止所有使用外部库(这样会减慢速度),这个词(所以运行,运行,运行都变得运行)。

现在我知道我说我们的倒排索引会将单词映射到文档名称,但是我们也想支持短语查询:不仅查询单词,而且可以查询特定序列中的单词。为此,我们需要知道每个单词在每个文档中的位置,因此我们可以检查订单。我使用标记化列表中的每个单词的索引作为该文档中单词的位置,因此我们最终的反向索引将如下所示:

{word: {documentID: [pos1, pos2, ...]}, ...}, ...}

而不是这样:

{word: [documentID, ...], ...}

所以我们的第一个任务就是创建一个单词到每个文档的位置的映射,然后结合起来创建我们完整的倒排索引。这就是这样的:

#input = [word1, word2, ...]
#output = {word1: [pos1, pos2], word2: [pos2, pos434], ...}
def index_one_file(termlist):
	fileIndex = {}
	for index, word in enumerate(termlist):
		if word in fileIndex.keys():
			fileIndex[word].append(index)
		else:
			fileIndex[word] = [index]
	return fileIndex

这段代码是非常自明的:它将文档中的术语中的空白分隔列表(其中的单词按照原始排序),并将每个添加到哈希表中,其中值是该单词的位置列表。我们通过列表来迭代地构建这个列表,直到我们经历了所有的话,留下了一个由字符串键入的表,并映射到这些字符串的位置列表。

现在,我们需要组合这些哈希表。我通过创建一个格式的中间索引来启动它

{documentID: {word: [pos1, pos2, ...]}, ...}

然后我们将转换到我们的最终索引。在这里完成了

#input = {filename: [word1, word2, ...], ...}
#res = {filename: {word: [pos1, pos2, ...]}, ...}
def make_indices(termlists):
	total = {}
	for filename in termlists.keys():
		total[filename] = index_one_file(termlists[filename])
	return total

这个代码非常简单:它只需要file_to_terms函数的结果,并创建一个由文件名键入的新哈希表,并使用作为上一个函数的结果的值作为嵌套散列表。

那么我们可以建立我们的倒排索引。以下是代码:

#input = {filename: {word: [pos1, pos2, ...], ... }}
#res = {word: {filename: [pos1, pos2]}, ...}, ...}
def fullIndex(regdex):
	total_index = {}
	for filename in regdex.keys():
		for word in regdex[filename].keys():
			if word in total_index.keys():
				if filename in total_index[word].keys():
					total_index[word][filename].extend(regdex[filename][word][:])
				else:
					total_index[word][filename] = regdex[filename][word]
			else:
				total_index[word] = {filename: regdex[filename][word]}
	return total_index

所以,让我们来看看这个。首先,我们使用一个空的哈希表(python dictionary),并且我们使用两个嵌套for循环遍历输入哈希中的每个单词。然后,我们首先检查该字是否作为输出哈希表中的键。如果没有,那么我们添加它,将其设置为另一个散列表,将文档(在这种情况下被标识为变量filename)映射到该单词的位置列表。

如果是密钥,那么我们再做一个检查:如果当前文档在每个单词的哈希表中(将文件名映射到单词位置的那个)。如果是,我们使用这个职位列表来扩展当前的职位列表(请注意,这种情况仅在于完整性:它永远不会被打,因为每个单词每个文件名只能有一个位置列表)。如果不是,那么我们设置的位置等于这个文件名的位置列表。

现在,我们有我们的索引。我们可以输入一个单词,并返回其出现的文档的列表,以及这些文档中显示的位置列表。现在,我们将学习如何查询此索引。

查询索引

好的,所以我们要处理两种查询类型:标准查询,查询中至少有一个单词出现在文档中,以及短语查询,查询中的所有单词都出现在文档中订购。

然而,在开始之前,我建议对查询进行清理,就像我们通过排除所有单词,小写字母和删除标点符号来构建索引来清理文档一样。我不会这样做,因为它是微不足道的,但应该在执行查询之前完成。

[注意:在下面的所有代码示例中,每个函数将接收一个名为“invertedIndex”的变量,它是根据上一节生成的)。

我们要先执行标准查询。一个简单的方法来实现这些是将查询分解成单词(如上所述的令牌),为每个单词获取一个列表,显示哪些文档,然后将所有这些列表合并。以下是我们如何查询一个字:

def one_word_query(word, invertedIndex):
	pattern = re.compile('[\W_]+')
	word = pattern.sub(' ',word)
	if word in invertedIndex.keys():
		return [filename for filename in invertedIndex[word].keys()]
	else:
		return []

这段代码很基本。我们这里正在做的是使用正则表达式对输入进行消毒,然后在索引中返回该单词的散列表中所有键的列表(这只是该字出现的所有文件名)。

那么一个标准的查询是一个非常简单的扩展,除此之外:我们只是聚合列表并联合它们,如下所示:

def free_text_query(string):
	pattern = re.compile('[\W_]+')
	string = pattern.sub(' ',string)
	result = []
	for word in string.split():
		result += one_word_query(word)
	return list(set(result))

如果您想实现一个查询,确保查询中的每个单词都显示在最终结果列表中,那么您应该只使用一个交集而不是联合来汇总单个单词查询的结果。这是相当微不足道的,我会把它作为一个练习留给读者。

查询的最终类型是短语查询,这有点更多的涉及,因为我们必须确保文档中单词的正确排序。这是这个查询的代码(我会解释后):

def phrase_query(string, invertedIndex):
	pattern = re.compile('[\W_]+')
	string = pattern.sub(' ',string)
	listOfLists, result = [],[]
	for word in string.split():
		listOfLists.append(one_word_query(word))
	setted = set(listOfLists[0]).intersection(*listOfLists)
	for filename in setted:
		temp = []
		for word in string.split():
			temp.append(invertedIndex[word][filename][:])
		for i in range(len(temp)):
			for ind in range(len(temp[i])):
				temp[i][ind] -= i
		if set(temp[0]).intersection(*temp):
			result.append(filename)
	return rankResults(result, string)

再次,我们首先从输入查询的消毒开始。然后,我们对输入中的每个单词运行单字查询,并将这些结果列表中的每一个添加到我们的总列表中。然后,我们创建一个名为setted的集合,它将第一个列表与所有其他列表(基本上是所有列表的交集)相交,并留下我们的中间结果集:包含所有列表的所有文档查询中的单词。

然后,我们必须检查订购。因此,对于中间结果中的每个列表,我们首先列出输入查询中每个单词的位置的列表。然后(请注意这里!)我们使用两个嵌套for循环遍历列表列表。对于每个列表中的每个位置,我们减去一个数字i,当我们浏览列表时,它会增加。当我们通过列表列表时,我增加1。现在,请记住,python列表保存顺序,因此列表列表按原始查询中的单词顺序包含原始查询中每个单词的位置列表。那么,如果这些字是正确的顺序,并且我们从每个位置列表中的每个位置减去一个整数i,

让我举个例子:

让我们说我们正在查询的短语是“蛋糕是谎言”。然后,对于一个特定的文件名,假设这些是每个单词的位置:

the : [23, 34, 15]
cake: [19, 35, 12]
is: [179, 36, 197]
a: [221, 37, 912]
lie: [188, 6, 38]

然后,我们的清单是:

[[23, 34, 15], [19, 35, 12], [179, 36, 197], [221, 37, 912], [188, 6, 38]]

现在,我们减去我从在每个列表中的每个元素,其中,我是0的第一列表,1所述的第二列表,2用于第三列表等

[[23, 34, 15], [18, 34, 11], [177, 34, 195], [218, 34, 909], [184, 2, 34]]

然后,我们采取所有这些列表的交集,这将留下我们一个元素34.这将表明短语“蛋糕是谎言”在文件中的顺序。这是真的:如果我们看原始清单,我们看到序列34,35,36,37,38给了我们这个词。

您可以支持更多的查询选项(请查看Google的高级搜索灵感)。您可以尝试自行实施其中的一些。

我们最后一步是实现一个查询解析器,这将使我们能够组合不同类型的查询来获得一个单一的结果集(比如你可以在Google中输入“蛋糕”这样一个谎言“标准查询(整个事情)和短语查询(“是谎言”),这也很简单:只需使用分隔符(如引号)来指定某种类型的查询,分别运行每个较小的查询,然后将所有这些结果集相交以得到文档的最终列表。

排名结果

构建搜索引擎的最后一步是创建一个系统,按照与查询的相关性对文档进行排名。这是最具挑战性的部分,因为它没有直接的技术解决方案:它需要一些创造力,并检查你自己的用例。对于这篇文章,我们将实施tf-idf排名(术语频率 - 逆文档频率)来排序我们的文档,这是更简单的排名方法之一。这部分不会有任何代码:一旦了解tf-idf的理论,实现它就相当简单,在创建索引时大部分工作都完成了。

那么什么是期限频率,我们的排名计划的第一部分?那么这听起来就像这样:每个单词在特定文档中显示的次数。术语频率作为度量不考虑顺序:它假定文档只是令牌的秩序矛盾集合,并且可以通过枚举出现每个令牌的次数来获得它的精确表示。这不是一个完全准确的假设,而是在文件分类领域被广泛使用。它更正式地被称为“一袋话”模型。

单词模型的一个简单表示是使用文档向量:即,我们将每个文档分解成长度为N的向量,其中N是该文档中唯一项的总数,并且每个条目是次数该具体术语出现在该文件中。对于多个文档,定义N的更方便的方法是搜索空间中所有文档中的唯一字数。这允许我们将每个文档表示为向量,并且使所有这些向量具有相等的维度。

可是等等!我们的模型目前存在很大的缺陷。考虑这两个文件:“让他们吃蛋糕”和“让他们吃蛋糕让他们吃蛋糕”。这些是完全一样的,除了第二个只是第一个重复,但它们的向量表示将是非常不同的:[1,1,1,1]与[2,2,2,2]相比。为了解决这个问题,我们将每个矢量转换成一个单位向量,除以其幅度(通过将每个条目的平方和的平方根乘以向量计算),“归一化”。这将使我们以前的矢量变成[1/2,1/2,1/2,1/2]和[1/2,1/2,1/2,1/2],使它们完全相同,其中是我们打算的

然而,这还不够。期限频率的致命缺陷(它的hamartia,任何希腊悲剧阅读)是它认为每学期为代表的文件同样重要。但是这不是真的:“和”这个词比“莎士比亚”或“衣原体”这个词比我说的少得多。但是,文字中的“和”这个词比“衣原体”更显着(或至少它在我读的东西中),这将在文档之间产生错误的相似性(因为它们都具有高出现的单词“和”)。

为了减轻这个问题,我们必须为我们的词频分级系统添加一些内容:逆文档频率。让我们定义文档频率ð 牛逼的一些长期牛逼是的次数ŧ在整个搜索空间显示出来(也就是所有我们索引文件)。然后,如果我们收集了K个文档,则相同项t的逆文档频率(I t)只是K / D t:文档的总数除以术语t出现的文档数量。

这里有一个最后的警告:它更强烈地纠正。如果我们有10个文件(K = 10),一个单词在集合中显示一次,另一个单词在集合中显示十次,则第二个单词被认为比第一个文本重要十倍。该函数的线性行为过于激进,通过过度校正将人为地减少相似度。为了解决这个问题,我们只是在前面添加了一个自然的日志功能,这样可以使我们的功能变得更加平坦,从而使其更正更加平缓。那么,最后的函数看起来像这样:在K个文档的集合中,对于一些术语t,I t= ln(K / D t)

(实施说明:您可能已经注意到,这些数量都不取决于查询,并且可以(并且应该)预先计算每个术语和文档)。

现在,为了将术语频率和逆文档频率合并为一个度量,我们可以将每个术语的值进行乘法运算。也就是说,我们收集中的任何给定术语的权重(我们的文档向量中的条目的值)只是T t * I t:术语频率乘以逆文档频率。

那么,如果我们有一个包含K个文档的集合 ,并且所有这些文档都有N个唯一的术语。然后,我们的文档将被表示为长度为N的向量,其中每个条目的值(对应于一个术语)是该文档中该术语的项的频率乘以该集合中该术语的逆文档频率。每个向量对于本文档中没有出现的术语只有0个(请记住,我们的向量表示集合中的所有唯一字词。反文档频率永远不会为0,因为它是一个集合级别度量。

然后,我们将对查询执行相同操作:我们将在N维空间中将其表示为向量,就像文档一样,并计算查询中每个项的tf-idf分数。这显然比文件本身要稀疏得多。

现在,剩下的唯一一个步骤是计算查询和其结果集之间的相似性得分,并且通过此分数对结果集中的文档进行排名。这里有许多不同的方法,但是我将在这里使用的东西称为余弦相似度,其基本上只是将查询的点积和每个文档向量在结果集中,并将其除以这两个向量返回这些向量之间角度的余弦(请阅读此 StackOverflow问题以进行澄清)。这是一个特别有用的指标,因为当您计算相似度(与欧几里德距离相反)时,不考虑两个向量的大小,当您有一个非常稀疏的向量(我们的查询)时,这是相当重要的,

所以,为了对结果进行排名,这是我们要做的:

  1. 首先,我们为每个术语预先计算tf和idf分数,并且我们使用每个项的tf * idf作为条目来构建每个文档的N长度向量。

  2. 然后,我们计算查询,并获得匹配文档的结果集(使用以前描述的技术)。

  3. 之后,我们计算查询的向量,也是长度为N,并且使用tf * idf作为其每个条目。

  4. 然后,我们计算结果集中查询和每个文档之间的相似度(使用余弦相似度),并获得每个文档的分数。

  5. 我们按照这个分数对文件进行排序,并按顺序返回。

和繁荣,我们完成了!

结论

使搜索引擎缩小到Google的大小是非常困难的。但是,制作一个简单的用于个人使用(或甚至作为概念证明)并不是那么难。实际上,搜索引擎构建索引,排名和查询文档的方式是直观的,构建一个是值得做的一个运动。

我们在这里使用的这个单词的模特儿到处都有。另一个伟大的应用是作为一个电子邮件垃圾邮件过滤器(我也已经制作,并将最终发布),或作为文档分类器,文章推荐器或任何数量的东西。这是一个非常酷的概念,值得考虑的是如何使用它来实现上述任何一种(或更冷)。

无论如何,这一切都来自我今天。如果您有任何反馈或问题,或者您只想对标题中的引用发表评论,请发表评论或向我发送电子邮件/ Facebook消息/您孩子们现在使用的任何其他新兴的社交网络。