搜索引擎原理（用python动手写一个简陋的原型）

相信看到这篇文章的人里不可能有人没使用过搜索引擎，它改变了人们获取信息的方式，可以说是上个十年互联网最伟大的发明。那么怎么写出一个搜索引擎呢？当我们想象自己要凭空写一个谷歌这样的庞然大物，多数人都觉得是个不可能完成的任务。事实上，写出一个谷歌这样处理海量数据的通用搜索引擎确实不是个人或者几个人能够完成的（附1），但搜索引擎的基本原理并不复杂，我们完全有能力写出一个简陋的搜索引擎，并把它应用到你需要的地方——据说安卓管理软件豌豆荚上的搜索框就是他们一个工程师花了一两周的时间独力写出来的。

搜索引擎原理将会写两篇博文，第一篇将介绍最基本的组成和原理，以及如何用python搭建一个最简陋的原型。第二篇将介绍如果要将这个简陋的原型进行应用，还需要考虑哪些问题，添加哪些组建（但只做原理上的介绍）。想要了解在大型商用引擎需要注意的问题，可以参看本文附件。

1.搜索引擎的原理

总的来说，搜索引擎包括3个部分：1.网络爬虫（自动下载成千上万个网页）。2.建立索引（将下载的网页归档并且建立查询目录）。3.网页排名（将用户最可能需要的网页排在前面）。

网络爬虫：

网络爬虫呢，简单的说网络爬虫就是一只会嗅着url(链接)爬过成千上万网页，并把网页内容搬到你电脑上供你使用的苦力虫子。如图1所示：你给定爬虫的出发页面A的url，它就从起始页A出发，读取A的所有内容，并从中找到3个url，分别指向页面B、C、D，然后它就顺着链接依次抓取B、C、D页面的内容，并从中发现新的链接，然后沿着链接继续爬到新的页面-->抓取内容-->分析链接-->爬到新的页面.......直到找不到新的链接或者满足了人为设定的停止条件为止。你可以对爬虫带回来的网页内容继续进行分析、处理，以满足你的需求。

至于这只虫子前进的方式，则分为广度优先搜索（BFS）和深度优先搜索(DFS)。在这张图中BFS的搜索顺序是A-B-C-D-E-F-G-H-I，而深度优先搜索的顺序是A-B-E-I-C-F-D-G-H，两种搜索方式在实际使用中如何选择，请阅读这个主题的第二篇博文：

建立索引：

索引就像图书馆每个书架上的小牌子，你要找某一本书，譬如一本学习python语言的书，你就先搜索“信息与计算机分部”，然后搜索“编程语言”，这样就可以在相应的架子上找到你想找的书了。搜索引擎的索引与此类似，所不同的是它会为所有网页的每个词语都建立索引，当你输入一串搜索字符串，程序会先进行分词，然后再依照每个词的索引找到相应网页。比如在搜索框中输入“从前有座山山里有座庙 小和尚”，搜索引擎首先会对字符串进行分词处理“从前/有/座山/山里/有/座庙/小和尚”，然后按照一定规则对词做布尔运算，比如每个词之间做“与”运算，然后在索引里搜索“同时”包含这些词的页面。当然在本篇中的这个简陋的引擎的索引功能也非常简陋，首先它是一个英文的搜索引擎分词相对简单（中日韩文的分词就比较复杂，例如“北京大学生”，怎么才能识别并分成"北京/大学生"，而不是"北京大学/生"），其次它每次只能提交一个词来做查询词，包含多词的字符串输入就查不到页面了。。。（当然读者可以自己加上多词查询，如果不考虑太复杂的逻辑运算规则，让所有词做“与”运算，这个功能还是很容易实现的）

网页排名（page rank）:

这个以谷歌创始人Larry Page命名的算法大概是互联网最著名的算法了，当年这个算法，帮助谷歌在搜索质量上一举打败了当时最流行的Yahoo,AltaVista等引擎，为谷歌崛起成为世界上最了不起的科技巨头立下了汗马功劳。

page rank是用来衡量网页质量如何的，索引找到的网页会用pagerank算法计算出一个PR值，这个得分在呈现结果排序中占一定权重，得分高的网页将被排在前面显示给用户。那么它是怎么实现的呢？它基于这样一种假设，越多的网页链接到这个网页，说明这个网页的在整个网络中受认可的程度越高，也即这个网页质量越好——这等同于互联网上其他所有网页给它投票，有一个链到它的链接说明给它投了一票，票数越高越好。但是是不是所有的票数权重都一样呢？显然不是的，链接到这个网页的网页本身PR值越高，则其投票的权重应该越大，这就好像董事会投票大股东的一票比小股东的一票更有份量。但这就存在一个问题了，你要知道一个页面的PR值就需要知道链接到它的页面的PR值，而链接到它的页面的PR值又需要依赖于其他页面的PR值，如此一直追究下去就变成了鸡生蛋蛋生鸡的问题了。现假设初始条件，互联网所有页面PR值的初始值为1/N，N是整个网络页面的总数，那么用  公式进行迭代，其中p(j)代表链接到p(i)的网页，Lp(j)代表这个页面中链接的数目，之所以要除以页面链接数量，这是很好理解的，当一个页面链接数量很多时，它每个链接投票的份量就相应地被分散了。可以证明，按照这个公式求取每个页面i的值，并进行迭代，当迭代很多轮时，PRp(i)的值会趋于一个稳定值，在应用中迭代次数一般取10次，超过10次以后PRp(i)的值变化就很小了。

现在还是存在一个问题，如果一个页面没有任何外部页面链接到它，那么它的PR值就是0了呢？为了使PRp(i)函数能够更平滑，我们在公式里增添一个阻尼系数d,在这里我们不妨取0.8,公式变成如下形式：

这样的话即使某个页面孤立存在，它的PR值也不至于变为零，而是一个很小的值。我们也可以从另一个角度理解阻尼系数，PR值衡量的其实是某个页面被访问的可能性的大小，链接到它的网页越多，通过这些链接点开它的可能性当然就越大，但在没有任何外部链接的情况下，一个网页是不是就不可能被访问呢？当然不是，因为还可以从地址框直接键入url访问，而且也会有人希望通过搜索引擎找到这个页面，所以我们在公式里加了阻尼系数，当然这里给1-d取一个比较小的数才可以。

当然了，网页PR值也不是唯一一个决定网页排名的因素，页面和用户搜索词(query)的相关程度也是重要的衡量因素，与搜索词相关度越高的页面应该放在越前面显示给用户。关于相关程度的算法，以及网页排名的其他注意事项，将在下一篇博文中介绍。

2.用python实现一个搜索引擎的原型

为什么是 Python:

首先，我们要明白，这是一篇菜鸟给菜鸟写的新手科普文，也是菜鸟自己刚刚上完搜索udacity引擎这门课以后给自己写的一个课程总结笔记。我觉得Python应该是菜鸟最好的一门入门语言了，鉴于它简明的语法、动态语言都有的垃圾自动回收机制、丰富方便的内置数据结构和方法、网络上丰富的开源库和开源框架，这门语言几乎什么都能干，而且干什么都很方便。虽然从性能上讲，这种解释型语言都是渣渣，虽然从编程思想上讲，它不像Lisp这种东西是实现满版都是括号递归的——但是，我们是菜鸟新手，我们的层次还没太多机会去接触这些问题呢！而和大学标配入门语言C和C++比起来，python真是简单到不知道哪里去了（我真怀疑，就大学那点c的学习，如果没有额外的用功，能用c写点什么出来呢？随便写点什么都要被乱七八糟的指针和老也分配不对的内存搞死啊。）另外，在接下来的代码里头，你会看到python的内置结构和方法是多么适合写这类文本处理的东西啊。OK，talk is cheap,show you my code!Hey we go!


#the search engine is divided into 3 modules:web crawl,build and use of index,page rank #----------------------------web_crawl-------------------------------- def get_page(url): try: import urllib return urllib.urlopen(url).read() except: return "" def get_next_target(page): start_link = page.find('<a href=') if start_link == -1: return None, 0 start_quote = page.find('"', start_link) end_quote = page.find('"', start_quote + 1) url = page[start_quote + 1:end_quote] return url, end_quote def get_all_links(page): links = [] while True: url, endpos = get_next_target(page) if url: links.append(url) page = page[endpos:] else: break return links def union(a, b): for e in b: if e not in a: a.append(e) def crawl_web(seed): # returns index, graph of inlinks tocrawl = [seed] crawled = [] graph = {} # <url>, [list of pages it links to] index = {} while tocrawl: page = tocrawl.pop() if page not in crawled: content = get_page(page) add_page_to_index(index, page, content) outlinks = get_all_links(content) graph[page] = outlinks union(tocrawl, outlinks) crawled.append(page) return index, graph #--------------------------------build_index----------------------------------- def add_page_to_index(index, url, content): words = content.split() for word in words: add_to_index(index, word, url) def add_to_index(index, keyword, url): if keyword in index: index[keyword].append(url) else: index[keyword] = [url] def lookup(index, keyword): if keyword in index: return index[keyword] else: return None #---------------------------------page_rank--------------------------------- def compute_ranks(graph): d = 0.8 # damping factor numloops = 10 ranks = {} npages = len(graph) for page in graph: ranks[page] = 1.0 / npages for i in range(0, numloops): newranks = {} for page in graph: newrank = (1 - d) / npages for node in graph: if page in graph[node]: newrank = newrank + d * (ranks[node] / len(graph[node])) newranks[page] = newrank ranks = newranks return ranks def quick_sort(url_lst,ranks): url_sorted_worse=[] url_sorted_better=[] if len(url_lst)<=1: return url_lst pivot=url_lst[0] for url in url_lst[1:]: if ranks[url]<=ranks[pivot]: url_sorted_worse.append(url) else: url_sorted_better.append(url) return quick_sort(url_sorted_better,ranks)+[pivot]+quick_sort(url_sorted_worse,ranks) def ordered_search(index, ranks, keyword): if keyword in index: all_urls=index[keyword] else: return None return quick_sort(all_urls,ranks) #---------------------------------test----------------------------------- index, graph = crawl_web('http://udacity.com/cs101x/urank/index.html') ranks = compute_ranks(graph) print ordered_search(index, ranks, 'Hummus') #>>> ['http://udacity.com/cs101x/urank/kathleen.html', # 'http://udacity.com/cs101x/urank/nickel.html', # 'http://udacity.com/cs101x/urank/arsenic.html', # 'http://udacity.com/cs101x/urank/hummus.html', # 'http://udacity.com/cs101x/urank/index.html'] #print ordered_search(index, ranks, 'the') #>>> ['http://udacity.com/cs101x/urank/nickel.html', # 'http://udacity.com/cs101x/urank/arsenic.html', # 'http://udacity.com/cs101x/urank/hummus.html', # 'http://udacity.com/cs101x/urank/index.html'] #print ordered_search(index, ranks, 'babaganoush') #>>> None