第 8 章:布爾代數(shù)和搜索引擎
搜索引擎:
- 自動下載盡可能多的網(wǎng)頁——下載
- 建立快速有效的索引——索引
- 根據(jù)相關(guān)性對網(wǎng)頁進行公平準確的排序——排序
1、布爾代數(shù)
2岔乔、索引
如何向你的奶奶解釋搜索引擎洼专?
每個網(wǎng)站就像圖書館里的一本書商佛,我們不可能在圖書館書架上一本本地找愁茁,而是要通過搜索卡片找到它的位置严望,然后直接去書架上拿摆尝。
第 9 章:圖輪和網(wǎng)絡(luò)爬蟲
如何自動下載互聯(lián)網(wǎng)所有的網(wǎng)頁呢温艇?——圖論中的遍歷算法。
- 廣度優(yōu)先搜索
- 深度優(yōu)先搜索
面試:如何構(gòu)建一個網(wǎng)絡(luò)爬蟲堕汞? - 用 BFS 還是 DFS:“如何在有限的時間里最多地爬下最重要的網(wǎng)頁”勺爱,顯然 BFS 明顯優(yōu)于 DFS。調(diào)度系統(tǒng)讯检,由它決定當一個網(wǎng)頁下載完成后琐鲁,接下來下載哪一個。
- 頁面的分析和 URL 的提取
- 記錄哪些網(wǎng)頁已經(jīng)下載過的小本本—— URL 表人灼。
第 10 章 PageRank Google 的民主表決式網(wǎng)頁排名技術(shù)
搜索結(jié)果的排名取決于兩組信息:關(guān)于網(wǎng)頁的質(zhì)量信息围段,以及這個查詢與每個網(wǎng)頁的相關(guān)性信息。
PageRank
如果一個網(wǎng)頁被很多其他網(wǎng)頁所鏈接投放,說明它受到普遍的承認和信賴奈泪,那么它的排名就高,這就是 PageRank 的核心思想灸芳±晕Γ考慮權(quán)重因此,即網(wǎng)頁排名高的網(wǎng)站貢獻的鏈接權(quán)重大烙样。
image.png
先假定所有網(wǎng)頁的排名是相同的苹支,并且根據(jù)這個初始值,算出各個網(wǎng)頁的第一次迭代排名误阻,然后再根據(jù)第一次迭代排名算出第二次的排名。從理論上證明了不論初始值如何選取,這種算法都能保證網(wǎng)頁排名的估計值收斂到排名的真實值究反,這種算法不需要任何人工干預寻定。
第 11 章 如何確定網(wǎng)頁和查詢的相關(guān)性
對搜索相關(guān)性貢獻最大是根據(jù)用戶對常見搜索點擊網(wǎng)頁的結(jié)果得到的概率模型,除了用戶的點擊數(shù)據(jù)之外精耐,歸納成下面四大類:
- 完備的索引
- 對網(wǎng)頁質(zhì)量的度量狼速,如 PageRank
- 用戶偏好
- 確定一個網(wǎng)頁和某個查詢相關(guān)性的方法
如何度量網(wǎng)頁和查詢的相關(guān)性
搜索關(guān)鍵詞權(quán)重的科學度量 TF-IDF
- 一個詞預測主題的能力越強,權(quán)重越大卦停,反之向胡,權(quán)重越小。
- 停止詞的權(quán)重為零惊完。
第 12 章:有限狀態(tài)機和動態(tài)規(guī)劃——地圖與本地搜索的核心技術(shù)
智能手機的定位和導航功能僵芹,其實只有三項關(guān)鍵技術(shù):
- 利用衛(wèi)星定位,這一點傳統(tǒng)的導航儀都能做到
- 地址的識別
- 用戶輸入的起點和終點小槐,在地圖上規(guī)劃最短路線或者最快路線
地址分析和有限狀態(tài)機
有限狀態(tài)機是一個特殊的有向圖拇派,它包括一些狀態(tài)(節(jié)點)和連接這些狀態(tài)的有向弧。
image.png
每一個有限狀態(tài)機都有一個開始狀態(tài)和一個終止狀態(tài)凿跳,以及若干中間狀態(tài)件豌。每一條弧上帶有從一個狀態(tài)進入下一個狀態(tài)的條件。
使用有限狀態(tài)機識別地址控嗜,關(guān)鍵要解決兩個問題:
- 通過一些有效地址建立狀態(tài)機
- 給定一個有限狀態(tài)機后茧彤,地址字串的匹配算法
2、全球?qū)Ш胶蛣討B(tài)規(guī)劃
第 18 章:談?wù)勊阉饕娣醋鞅讍栴}和搜索結(jié)果的權(quán)威性問題
搜索引擎的反作弊
在通信中解決噪音干擾問題的基本思路有兩條:
- 從信息源出發(fā)疆栏,加強通信(編碼)自身的抗干擾能力
- 從傳輸來看曾掂,過濾掉噪音,還原信息承边。