?加介次掌
碩士學位論文
暴
論文題目垂直搜索引擎若干關鍵技術的研究
作者姓名王曉偉
指導教師林懷忠副教授
學科(專業)計算機應用技術
所在學院計算機科學與技術學院
提交日期二00七年五月ADissertationsubmittedtoZhejiang
    UniversityfortheDegreeof
  MasterofEngineering
    ResearchonKeyTechniquesof
  VerticalSearchEngine
Author:
SuPervisor:
Major:
 WangXiaowei
  Assoc.Prof.LinHuaizhong
ComPuterAPPlieation
College
  ZhejiangUniversity，
  ofComPuterScienee
Hangzhou， P.R.China，  310027
May，2007浙江大學碩士學位論文摘要
摘要
隨著Intemet的飛速發展，W七b的信息量越來越大，通用搜索引擎將面臨信
息采集、存儲等方面更大的挑戰。此外，由于通用搜索引擎面向所有的用戶，力
爭在返回結果上做到面面俱到，包羅萬象的結果顯然不能滿足用戶精確搜索的需
求。因此，面向專業領域的搜索引擎即垂直搜索引擎應運而生。
與通用搜索引擎不同，垂直搜索引擎的網絡蜘蛛只采集Web中的部分信息。
通過對網頁的主題相關度進行預測和判斷，專業網絡蜘蛛在爬行(Crawling)時
避開了大量主題無關的區域。由于只采集主題相關的網頁，垂直搜索引擎在查詢
的準確率和效率上都有顯著的提高。目前，垂直搜索引擎的中文分詞和主題預測
有待進一步提高精度，網絡蜘蛛的搜索策略也有待進一步改進以提高搜索引擎的
覆蓋率和效率。
本文提出了基于主題的自適應的分詞技術，使用候選詞典和專業詞庫來指導
分詞和歧義消除，能有效地提高專業領域中分詞的查全率和查準率。
本文還提出了基于父網頁的主題相關度預測算法(CPAP)、基于鏈入網頁的
主題相關度預測算法(CPAH)和TPR主題預測算法。C隊P利用了錨文本和父
網頁的主題相關度等信息進行預測;CPAH在預測主題相關度時綜合考慮了鏈接
的數量和質量;TPR算法則將網頁的主題相關性和權威性相結合，從而有效地防
止了“主題漂流”現象。
為了解決普通隧道技術隨著探索半徑的增大，主題無關網頁呈指數級增加的
問題，本文提出了稀疏隧道技術，稀疏隧道技術使專業網絡蜘蛛在整個W七b中拉
網式地探索未知網頁，從而實現“疏而不漏”地挖掘新的WebC。~unity。
最后是系統的設計與實現，在上述理論分析的基礎上提出了系統的設計思
想，并介紹了系統的體系結構和具體實現技術。
關鍵詞垂直搜索引擎，中文分詞，網絡蜘蛛，隧道技術，主題相關度預測
2浙江大學碩士學位論文AbstraCt
AbstraCt
          TheraPidgrowthoftheInternetPosesunPreeedentedsealingehallengesfor
general一   Purposesearehengines.Inaddition，general一   PurposesearchenginesProvide
   serviceforallusers，        50theresultsfromthemaretooexhaustive.Thousandsof
        irrelativeresultsobviouslydonotmeetPreeisesearchneeds.Therefore，Vertical
         SearehEnginewhiehProvidesservieeinasinglefieldemerged.
      Ratherthaneolleetingandindexingallaeeessiblew七     bdoetunentstobeableto
   answerallPossiblequeries，         afoeusederawleranalyzesitscrawlboundarytofindthe
          linksthatarelikelytobemostrelevantforthecra、vl，    andavoidsirrelevantregionsof
thew七     b.AsonlyrelatedPagesarecrawled，     aeeuracyandeffieieneyofvertiealsearch
   engineshaveimProvedremarkably.Currently，    aeeuraeyofChineseWbrd
        SeglnentationandCorrelationPredictionarestilltobeimProved，  searehstrategyof
             FocusedCrawlerhasyettobefurtherimProvedtoenhancesearehengineeoverageand
effieieney.
   InChineseW6rdSegmentation，     thisPaperPresentsnewalgorithxnnamed
         AdaptiveChineseWbrdSegmentationbasedonThemewhiehuseCandidate
        dictionaryandProfessionaldietionarytoguideseglnentationandambiguity
           elimination.ItProvedtobeeffeetiveinraisingPrecisionoftheProfessionalword
segmentation.
   InCorrelationPredietionAlgorithm，      threemodelsarePresentedinthisPager:
     CorrelationPredictionAlgorithmBasedonFather(CPAP)， CorrelationPredietion
       AlgorithmBasedonHyPerlink(CPAH)andTPRCorrelationPredictionAlgorithm.
             TheanchortextandCorrelationofFatherPagesareinvolvedintheCPAPmodel:
          CPAHmodelealeulateseorrelationbythequantityandqualityofPages:TPR
       algorithmeombinestheeorrelationandauthorityofPages，  therebyiteffectively
Prevent’ .themedrift，，Phenomenon.
 Inthew七  bSearchStrategy，        thisPaperPresentsasParsetunnelingtechnology.it
        effeetivelyaddressedtheexPoneniialinereasingProblemwithoriginaltunneling
     teehnology.SParsetunnelingteehnologyexPloretheentire節  /ebsParsely， therebyit
       greatlyimProvedtheProbabilityofdiscoveringnewwebconununities.
          FinallythedesignandtherealiZationofthesystemareintrodueed， includingthe
   systemstructureandmethod.
   KeywordsVertiealSearehEngine，Chinese認  /OrdSegmentation， FoeusedCrawler，
Tunneling， CorrelationPredietion
窮浙江大學碩士學位論文目錄
目錄
摘要.........................................................................................................................……i
Abstract.............................................................................……，.............................……11
第1章緒論.....................................................……，..............................................……l
1.1背景..................................……，................................……，.....................……，....……1
1.2通用搜索引擎................................................................................................……1
1.2.1搜索引擎的發展歷史..…，..........……，......................................................……1
1.2.2搜索引擎的分類.....................................................................................……2
1.2.3搜索引擎組成及工作原理.....................................................................……3
 1.2.4現有的通用搜索引擎的局限性.............................................................……4
1.2.5搜索引擎的發展趨勢.............................................................................……5
1.3垂直搜索引擎................................................................................................……6
1.3.1垂直搜索引擎的優勢.............................................................................……6
1.3.2專業網絡蜘蛛.........................................................................................……6
1.3.3研究現狀.......……，...................................................................................……7
1.4本文的工作和組織........................................................................................……8
第2章相關技術的研究現狀............................................................................……10
2.1中文分詞技術.…，.........................................................................................……10
2.1.1基于字符串匹配的分詞方法.......................……，....……，......................……10
 2.1.2基于統計的分詞方法...........................................................................……12
2.1.3基于理解的分詞方法...........................................................................……14
2.2主題判別的研究現狀..................................................................................……14
2.2.1布爾模型..…，.......……‘.......……，................……，......................................……14
2.2.2向量空間模型.......................................................................................……巧
2.3基于鏈接的分析技術....................................……，.......................................……16
 2.3.1PageRank算法................……，.……，........................................................……16
 2.3.2HITS算法..............................................................................................……19
 2.3.3PageRank和HITS算法比較................................................................……20
2.4本章小節......................................................................................................……20
第3章中文分詞和主題預測算法....................................................................……21
3.1基于主題的自適應的分詞方法..................................................................……21
3.1.1候選詞典.............……，......................................................……，........……，..…21
3.1.2Aging技術.............................................................................................……22
必浙江大學碩士學位論文目錄
3.1.3基于主題的自適應分詞算法...............................................................……23
3.2基于 WebCommunity的URL主題相關度預測.......................................……24
3.2.1基于父網頁的主題相關度預測......................................……，，.............……25
3.2.2基于鏈入網頁的主題相關度預測.......................................................……27
 3.2.3TPR主題相關度預測算法................................................……，.............……28
3.3本章小結......................................................................................................……33
第4章基于稀疏隧道技術的專業網絡蜘蛛....................................................……35
4.1專業網絡蜘蛛................................……，.....................................................·.……35
4，1.1專業網絡蜘蛛的工作原理...................................................................……35
4.1.2專業網絡蜘蛛存在的問題...................……，.........................................……36
4.2隧道技術..........……，..........................……，....................................................……38
4.2.1隧道技術分析...........................................................................·......·····……38
4.2.2隧道技術的優點...................................................··...···························……39
4.3稀疏隧道技術.................................................................................······..·····……39
  4.3.1webCO~unity黑名單.....................................................................·..……40
4.3.2稀疏探索...............................................................................................……41
4.3.3稀疏隧道技術的流程...........................................................................……41
4.3.4策略的比較...........................................................................··.·············……42
第5章系統設計與實現....................................................................................……45
5.1設計思想......................................................................................................……45
5.2體系結構...................................................................................................……，二45
5.2.lu砒服務器..........................................................................……，.....·····……46
5.2.2網絡蜘蛛...............................................................................................……46
5.2.3主題判別器................................................................................·····...···……47
5.2.4U甩提取器...........................................................................................……48
5.2.5主題預測器...........................................................................................……49
第6章總結與展望...............................................................................·············……50
6.1總結..............................................................................................................……50
6.2展望..............................................................................................................……50
參考文獻..............................................................................................................……51
致謝......................................................................................................................……54
言浙江大學碩士學位論文第l章緒論
第1章緒論
1.1背景
隨著玩temet的飛速發展，Web的信息量越來越大，人們往往需要借助搜索
引擎來幫助他們尋找特定領域的資料，然而現有的搜索引擎如Google、百度等，
都不是專門為搜索特定領域資料而設計的，這些搜索引擎面向所有的用戶，力爭
在返回結果上做到面面俱到。因此，真正需要的資料往往淹沒在大量的無用的信
息中，在這種情況之下，面向特定專業的搜索引擎，即垂直搜索引擎應運而生。
垂直搜索引擎也叫專業搜索引擎，是相對通用搜索引擎的覆蓋率過低、查詢不準
確、更新不及時等缺點提出來的新的搜索引擎服務模式，它通過針對某一特定領
域、某一特定人群或某一特定需求而提供有一定價值的信息和相關服務，其特點
是“專、精、深”，且具有行業色彩。
目前因特網上的可索引到的網頁數量已超過110億頁【l]，還有相當大的一部
分網頁無法被搜索引擎索引到，即使是世界上最大的搜索引擎Google也只能索引
到整個Web的30一40%，更新這些索引的時間從幾周到幾個月不等。這種挑戰不
是來自互聯網本身，而是來自一個簡單的哲學道理:我們沒有辦法讓一臺機器存
儲整個互聯網的信息，垂直搜索引擎是在這樣的背景下提出來的一種順應歷史潮
流的解決方案。
本文在這種背景下，結合近年來比較熱門的FocusedC~ling[2]的研究成果，
對垂直搜索引擎中的中文分詞和精確爬行(C~ling)技術提出了新的思路和解決