搜索引擎原理將會(huì)寫兩篇博文，第一篇將介紹最基本的組成和原理，以及如何用python搭建一個(gè)最簡(jiǎn)陋的原型。第二篇將介紹如果要將這個(gè)簡(jiǎn)陋的原型進(jìn)行應(yīng)用，還需要考慮哪些問題，添加哪些組建（但只做原理上的介紹）。想要了解在大型商用引擎需要注意的問題，可以參看本文附件。

總的來說，搜索引擎包括3個(gè)部分：1.網(wǎng)絡(luò)爬蟲（自動(dòng)下載成千上萬個(gè)網(wǎng)頁）。2.建立索引（將下載的網(wǎng)頁歸檔并且建立查詢目錄）。3.網(wǎng)頁排名（將用戶最可能需要的網(wǎng)頁排在前面）。

網(wǎng)絡(luò)爬蟲呢，簡(jiǎn)單的說網(wǎng)絡(luò)爬蟲就是一只會(huì)嗅著url(鏈接)爬過成千上萬網(wǎng)頁，并把網(wǎng)頁內(nèi)容搬到你電腦上供你使用的苦力蟲子。如圖1所示：你給定爬蟲的出發(fā)頁面A的url，它就從起始頁A出發(fā)，讀取A的所有內(nèi)容，并從中找到3個(gè)url，分別指向頁面B、C、D，然后它就順著鏈接依次抓取B、C、D頁面的內(nèi)容，并從中發(fā)現(xiàn)新的鏈接，然后沿著鏈接繼續(xù)爬到新的頁面-->抓取內(nèi)容-->分析鏈接-->爬到新的頁面.......直到找不到新的鏈接或者滿足了人為設(shè)定的停止條件為止。你可以對(duì)爬蟲帶回來的網(wǎng)頁內(nèi)容繼續(xù)進(jìn)行分析、處理，以滿足你的需求。

至于這只蟲子前進(jìn)的方式，則分為廣度優(yōu)先搜索（BFS）和深度優(yōu)先搜索(DFS)。在這張圖中BFS的搜索順序是A-B-C-D-E-F-G-H-I，而深度優(yōu)先搜索的順序是A-B-E-I-C-F-D-G-H。

索引就像圖書館每個(gè)書架上的小牌子，你要找某一本書，譬如一本學(xué)習(xí)python語言的書，你就先搜索“信息與計(jì)算機(jī)分部”，然后搜索“編程語言”，這樣就可以在相應(yīng)的架子上找到你想找的書了。搜索引擎的索引與此類似，所不同的是它會(huì)為所有網(wǎng)頁的每個(gè)詞語都建立索引，當(dāng)你輸入一串搜索字符串，程序會(huì)先進(jìn)行分詞，然后再依照每個(gè)詞的索引找到相應(yīng)網(wǎng)頁。比如在搜索框中輸入“從前有座山山里有座廟 小和尚”，搜索引擎首先會(huì)對(duì)字符串進(jìn)行分詞處理“從前/有/座山/山里/有/座廟/小和尚”，然后按照一定規(guī)則對(duì)詞做布爾運(yùn)算，比如每個(gè)詞之間做“與”運(yùn)算，然后在索引里搜索“同時(shí)”包含這些詞的頁面。當(dāng)然在本篇中的這個(gè)簡(jiǎn)陋的引擎的索引功能也非常簡(jiǎn)陋，首先它是一個(gè)英文的搜索引擎分詞相對(duì)簡(jiǎn)單（中日韓文的分詞就比較復(fù)雜，例如“北京大學(xué)生”，怎么才能識(shí)別并分成"北京/大學(xué)生"，而不是"北京大學(xué)/生"），其次它每次只能提交一個(gè)詞來做查詢?cè)~，包含多詞的字符串輸入就查不到頁面了。。。（當(dāng)然讀者可以自己加上多詞查詢，如果不考慮太復(fù)雜的邏輯運(yùn)算規(guī)則，讓所有詞做“與”運(yùn)算，這個(gè)功能還是很容易實(shí)現(xiàn)的）

這個(gè)以谷歌創(chuàng)始人Larry Page命名的算法大概是互聯(lián)網(wǎng)最著名的算法了，當(dāng)年這個(gè)算法，幫助谷歌在搜索質(zhì)量上一舉打敗了當(dāng)時(shí)最流行的Yahoo,AltaVista等引擎，為谷歌崛起成為世界上最了不起的科技巨頭立下了汗馬功勞。

page rank是用來衡量網(wǎng)頁質(zhì)量如何的，索引找到的網(wǎng)頁會(huì)用pagerank算法計(jì)算出一個(gè)PR值，這個(gè)得分在呈現(xiàn)結(jié)果排序中占一定權(quán)重，得分高的網(wǎng)頁將被排在前面顯示給用戶。那么它是怎么實(shí)現(xiàn)的呢？它基于這樣一種假設(shè)，越多的網(wǎng)頁鏈接到這個(gè)網(wǎng)頁，說明這個(gè)網(wǎng)頁的在整個(gè)網(wǎng)絡(luò)中受認(rèn)可的程度越高，也即這個(gè)網(wǎng)頁質(zhì)量越好——這等同于互聯(lián)網(wǎng)上其他所有網(wǎng)頁給它投票，有一個(gè)鏈到它的鏈接說明給它投了一票，票數(shù)越高越好。但是是不是所有的票數(shù)權(quán)重都一樣呢？顯然不是的，鏈接到這個(gè)網(wǎng)頁的網(wǎng)頁本身PR值越高，則其投票的權(quán)重應(yīng)該越大，這就好像董事會(huì)投票大股東的一票比小股東的一票更有份量。但這就存在一個(gè)問題了，你要知道一個(gè)頁面的PR值就需要知道鏈接到它的頁面的PR值，而鏈接到它的頁面的PR值又需要依賴于其他頁面的PR值，如此一直追究下去就變成了雞生蛋蛋生雞的問題了?，F(xiàn)假設(shè)初始條件，互聯(lián)網(wǎng)所有頁面PR值的初始值為1/N，N是整個(gè)網(wǎng)絡(luò)頁面的總數(shù)，那么用  公式進(jìn)行迭代，其中p(j)代表鏈接到p(i)的網(wǎng)頁，Lp(j)代表這個(gè)頁面中鏈接的數(shù)目，之所以要除以頁面鏈接數(shù)量，這是很好理解的，當(dāng)一個(gè)頁面鏈接數(shù)量很多時(shí)，它每個(gè)鏈接投票的份量就相應(yīng)地被分散了?？梢宰C明，按照這個(gè)公式求取每個(gè)頁面i的值，并進(jìn)行迭代，當(dāng)?shù)芏噍啎r(shí)，PRp(i)的值會(huì)趨于一個(gè)穩(wěn)定值，在應(yīng)用中迭代次數(shù)一般取10次，超過10次以后PRp(i)的值變化就很小了。

現(xiàn)在還是存在一個(gè)問題，如果一個(gè)頁面沒有任何外部頁面鏈接到它，那么它的PR值就是0了呢？為了使PRp(i)函數(shù)能夠更平滑，我們?cè)诠嚼镌鎏硪粋€(gè)阻尼系數(shù)d,在這里我們不妨取0.8,公式變成如下形式：

這樣的話即使某個(gè)頁面孤立存在，它的PR值也不至于變?yōu)榱?，而是一個(gè)很小的值。我們也可以從另一個(gè)角度理解阻尼系數(shù)，PR值衡量的其實(shí)是某個(gè)頁面被訪問的可能性的大小，鏈接到它的網(wǎng)頁越多，通過這些鏈接點(diǎn)開它的可能性當(dāng)然就越大，但在沒有任何外部鏈接的情況下，一個(gè)網(wǎng)頁是不是就不可能被訪問呢？當(dāng)然不是，因?yàn)檫€可以從地址框直接鍵入url訪問，而且也會(huì)有人希望通過搜索引擎找到這個(gè)頁面，所以我們?cè)诠嚼锛恿俗枘嵯禂?shù)，當(dāng)然這里給1-d取一個(gè)比較小的數(shù)才可以。

當(dāng)然了，網(wǎng)頁P(yáng)R值也不是唯一一個(gè)決定網(wǎng)頁排名的因素，頁面和用戶搜索詞(query)的相關(guān)程度也是重要的衡量因素，與搜索詞相關(guān)度越高的頁面應(yīng)該放在越前面顯示給用戶。關(guān)于相關(guān)程度的算法，以及網(wǎng)頁排名的其他注意事項(xiàng)，將在下一篇博文中介紹。

首先，我們要明白，這是一篇菜鳥給菜鳥寫的新手科普文，也是菜鳥自己剛剛上完搜索udacity引擎這門課以后給自己寫的一個(gè)課程總結(jié)筆記。我覺得Python應(yīng)該是菜鳥最好的一門入門語言了，鑒于它簡(jiǎn)明的語法、動(dòng)態(tài)語言都有的垃圾自動(dòng)回收機(jī)制、豐富方便的內(nèi)置數(shù)據(jù)結(jié)構(gòu)和方法、網(wǎng)絡(luò)上豐富的開源庫和開源框架，這門語言幾乎什么都能干，而且干什么都很方便。雖然從性能上講，這種解釋型語言都是渣渣，雖然從編程思想上講，它不像Lisp這種東西是實(shí)現(xiàn)滿版都是括號(hào)遞歸的——但是，我們是菜鳥新手，我們的層次還沒太多機(jī)會(huì)去接觸這些問題呢！而和大學(xué)標(biāo)配入門語言C和C++比起來，python真是簡(jiǎn)單到不知道哪里去了（我真懷疑，就大學(xué)那點(diǎn)c的學(xué)習(xí)，如果沒有額外的用功，能用c寫點(diǎn)什么出來呢？隨便寫點(diǎn)什么都要被亂七八糟的指針和老也分配不對(duì)的內(nèi)存搞死啊。）另外，在接下來的代碼里頭，你會(huì)看到python的內(nèi)置結(jié)構(gòu)和方法是多么適合寫這類文本處理的東西啊。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:///cs101x/urank/index.html')
ranks = compute_ranks(graph)
print ordered_search(index, ranks, 'Hummus')
#>>> ['http:///cs101x/urank/kathleen.html',
#    'http:///cs101x/urank/nickel.html',
#    'http:///cs101x/urank/arsenic.html',
#    'http:///cs101x/urank/hummus.html',
#    'http:///cs101x/urank/index.html']

#print ordered_search(index, ranks, 'the')
#>>> ['http:///cs101x/urank/nickel.html',
#    'http:///cs101x/urank/arsenic.html',
#    'http:///cs101x/urank/hummus.html',
#    'http:///cs101x/urank/index.html']


#print ordered_search(index, ranks, 'babaganoush')
#>>> None

本文章出自http://073palmer./2012/06/python.html 

對(duì)于初步了解搜索引擎的朋友啟發(fā)很大，以上代碼在ide 中測(cè)試過了，性能有待提升；有興趣的朋友歡迎留言討論。