搜索引擎及其經(jīng)典算法

摘 要 是指根據(jù)一定的策略、運(yùn)用特定的計(jì)算機(jī)程序從互聯(lián)網(wǎng)上搜集信息，在對(duì)信息進(jìn)行組織和處理后，為用戶提供檢索服務(wù)，將用戶檢索相關(guān)的信息展示給用戶的系統(tǒng)。搜索引擎包括全文索引、目錄索引、元搜索引擎、垂直搜索引擎、集合式搜索引擎等。

關(guān)鍵詞 搜索 算法

一、概述

搜索引擎是采用特定的程序（spider）完成從互聯(lián)網(wǎng)中提取信息的數(shù)據(jù)庫系統(tǒng)，它的主要功能是為用戶提供全網(wǎng)范圍的快速查詢。它將信息存儲(chǔ)為表格的形式，這就是索引（index）。在索引數(shù)據(jù)庫中，網(wǎng)頁中所有內(nèi)容，包括文本內(nèi)容以及相應(yīng)的格式、控制、關(guān)鍵詞語出現(xiàn)的位置等信息都有相應(yīng)的記錄。我們搜索關(guān)鍵字時(shí)，相關(guān)的頁面會(huì)被找出來，并按照關(guān)鍵詞相關(guān)程度、用戶歡迎程度等指標(biāo)排出順序，這就是排序算法。

搜索引擎一般分為全文搜索引擎、目錄式搜索引擎、元搜索引擎。1、全文搜索引擎：目前百度、谷歌、AltaVista、Lycos等是全文搜索引擎的代表，但其中有部分搜索引擎沒有自己的蜘蛛程序，需要租用其它搜索引擎的數(shù)據(jù)庫，但用自己的排序算法對(duì)搜索結(jié)果進(jìn)行排序。從這里可以知道，排序算法才是搜索引擎最核心的機(jī)密。搜索引擎獲取信息有兩種方式：一種是主動(dòng)定時(shí)采集，也就是用爬行器對(duì)各網(wǎng)段進(jìn)行定時(shí)檢索；第二種是由網(wǎng)站自行提交網(wǎng)址，由搜索引擎審核。

2、目錄式搜索引擎：目錄搜索引擎沒有爬蟲程序，此類搜索引擎的功能只有對(duì)提交給它的網(wǎng)站進(jìn)行分類整理。網(wǎng)站對(duì)它提交關(guān)鍵住處，引擎對(duì)他們分類，形成一個(gè)鏈接到站點(diǎn)的目錄列表。這些引擎的代表為新浪目錄、Dmoz、雅虎搜索等等。3、元搜索引擎：它們實(shí)際上只是搜索引擎與用戶之間的接口，用戶提出請(qǐng)求之后，它在眾多搜索引擎上檢索，排自己的算法進(jìn)行篩選和排序。問答聚合就是一個(gè)元搜索引擎。

二、搜索引擎組成

1、Spider/爬蟲：搜索引擎使用大量爬蟲檢索整個(gè)網(wǎng)絡(luò)，將各服務(wù)器中的數(shù)據(jù)采集到本地?cái)?shù)據(jù)庫中。爬蟲從已有數(shù)據(jù)庫開始，在網(wǎng)頁中逐級(jí)逐個(gè)查找鏈接，直到找完所有鏈接。從理論上講，爬蟲可以找到互聯(lián)網(wǎng)所有網(wǎng)頁。但有數(shù)據(jù)表明，部分網(wǎng)頁無法找到；另外，個(gè)別搜索引擎通過不正當(dāng)手段采集信息孤島。

2、索引器與索引數(shù)據(jù)庫：索引器的主要功能是將收集來數(shù)據(jù)進(jìn)行分析，提煉出其中的索引項(xiàng)，用倒排索引的方式建立數(shù)據(jù)表，按關(guān)鍵字搜索對(duì)應(yīng)的文檔。

3、 檢索器：檢索器獲得網(wǎng)頁，然后計(jì)算文內(nèi)容與查詢要求的相關(guān)程度，根據(jù)相關(guān)程度的高低來排序展現(xiàn)。因此，排序算法是評(píng)價(jià)搜索引擎優(yōu)劣重要指標(biāo)。

三、 排名引擎算法

1、 第一代排序算法： 詞頻統(tǒng)計(jì)和詞位置加權(quán)。

文檔的詞頻是指查詢關(guān)鍵詞在文檔中出現(xiàn)的頻率。查詢關(guān)鍵詞詞頻在文檔中出現(xiàn)的頻率越高，其相關(guān)度越大。但當(dāng)關(guān)鍵詞為常用詞時(shí)，使其對(duì)相關(guān)性判斷的意義非常 小。TF/IDF很好的解決了這個(gè)問題。TF/IDF算法被認(rèn)為是信息檢索中最重要的發(fā)明。TF（Term Frequency）：單文本詞匯頻率，用關(guān)鍵詞的次數(shù)除以網(wǎng)頁的總字?jǐn)?shù)，其商稱為“關(guān)鍵詞的頻率”。IDF（Inverse Document Frequency）：逆文本頻率指數(shù)，其原理是，一個(gè)關(guān)鍵詞在N個(gè)網(wǎng)頁中出現(xiàn)過，那么N越大，此關(guān)鍵詞的權(quán)重越小，反之亦然。當(dāng)關(guān)鍵詞為常用詞時(shí)，其權(quán) 重極小，從而解決詞頻統(tǒng)計(jì)的缺陷。詞位置加權(quán)是通過對(duì)檢索關(guān)鍵詞在Web頁面中不同位置和版式，給予不同的權(quán)值，從而根 據(jù)權(quán)值來確定所搜索結(jié)果與檢索關(guān)鍵詞相關(guān)程度?？梢钥紤]的版式信息有：是否是標(biāo)題，是否為關(guān)鍵詞，是否是正文，字體大小，是否加粗等等。同時(shí)，錨文本的信 息也是非常重要的，它一般能精確的描述所指向的頁面的內(nèi)容。

tf-idf模型：

2、第二代算法：鏈接分析

鏈接分析排序的思路是，網(wǎng)頁被引用的次數(shù)越多，說明該網(wǎng)頁越受歡迎，被越權(quán)威的網(wǎng)頁引用，說明該網(wǎng)頁質(zhì)量越高。下面介紹兩個(gè)經(jīng)典算法：

（1）PageRank算法

PageRank算法是Google搜索引擎采用的靜態(tài)算法。它的基本思想來源于學(xué)術(shù)文獻(xiàn)引用，論文被引用的次數(shù)越多，價(jià)值越大。若引用者的權(quán)威性高，則被引用者權(quán)威性也增加。相應(yīng)的，網(wǎng)頁重要程度也由兩個(gè)方面衡量：一、引用該頁的頁面?zhèn)€數(shù)，二、引用該頁的頁面重要程度。

d：阻尼系數(shù)。為避免鏈接沉淀問題提出的系數(shù)，常指定為0.85；

PR（Ti）：網(wǎng)頁Ti的PageRank值；

C（Ti）：網(wǎng)頁Ti鏈出的鏈出數(shù)量。

這個(gè)公式是收斂的，多次迭代后將得到穩(wěn)定的值。實(shí)驗(yàn)證明，迭代十次后值趨于穩(wěn)定。

（2）HITS算法

HITS（Hyperlink Induced Topic Search）算法，是另一個(gè)著名的超鏈分析算法。該算法將網(wǎng)頁分為hub（中心頁面）和Authority（權(quán)威頁面）。Authority頁是與用戶查詢的關(guān)鍵詞最相近的頁面，hub頁的主要內(nèi)容是大量指向Authority頁的鏈接，相當(dāng)于Authority頁的目錄。一般來說，好的Hub網(wǎng)頁指向許多好的Authority網(wǎng)頁，好的Authority網(wǎng)頁是由許多好的Hub網(wǎng)頁所指向，這便是相互加強(qiáng)模型。通過這種關(guān)系可以計(jì)算出Authority屬性較高的網(wǎng)頁，也就是重要性強(qiáng)的網(wǎng)頁。

中心值和權(quán)威值相互加強(qiáng)的公式：

，迭代以后規(guī)范化，即可得到期望結(jié)果。

四、發(fā)展趨勢(shì)

1、垂直搜索引擎，此類搜索引擎是對(duì)數(shù)據(jù)庫中數(shù)據(jù)的再次篩選，只搜索特定領(lǐng)域或行業(yè)的內(nèi)容。在某種程度上，這可能會(huì)解決搜索引擎結(jié)果太過寬泛的問題問題。

2、 個(gè)性化搜索引擎，它基于用戶習(xí)慣的詳細(xì)分析。這需要對(duì)用戶進(jìn)行長期的監(jiān)視，顯然與保護(hù)個(gè)人隱私有著不可回避的矛盾。3、知識(shí)搜索引擎，它不是單純搜索工具，而是實(shí)現(xiàn)知識(shí)管理的一種工具，通過搜索引擎技術(shù)完成知識(shí)管理。實(shí)現(xiàn)知識(shí)匯聚、知識(shí)發(fā)現(xiàn)、知識(shí)分類、知識(shí)聚類、知識(shí)門戶的構(gòu)建等。