前言 第一章引论.................................................................................................................1 第一节 搜索引擎的概念................................................................................................2 第二节 搜索引擎的发展历史........................................................................................3 第三节 一些著名的搜索引擎........................................................................................7 上篇 WEB搜索引擎基本原理和技术....................................................................16 第二章 WEB搜索引擎工作原理和体系结构..........................................................17 第一节 基本要求..........................................................................................................17 第二节 网页搜集..........................................................................................................18 第三节 预处理..............................................................................................................20 第四节 查询服务..........................................................................................................22 第五节 体系结构..........................................................................................................25 第三章 WEB信息的搜集..........................................................................................29 第一节 引言..................................................................................................................29 一、 超文本传输协议..............................................................................................29 二、 一个小型搜索引擎系统..................................................................................31 第二节 网页搜集..........................................................................................................33 一、 定义URL类和Page类......................................................................................34 二、 与服务器建立连接..........................................................................................39 三、 发送请求和接收数据......................................................................................41 四、 网页信息存储的天网格式..............................................................................42 第三节 多道搜集程序并行工作..................................................................................45 一、 多线程并发工作..............................................................................................46 二、 控制对一个站点并发搜集线程的数目..........................................................47 第四节 如何避免网页的重复搜集..............................................................................47 一、 记录未访问、已访问URL和网页内容摘要信息..........................................47 二、 域名与IP的对应问题......................................................................................48 第五节 如何首先搜集重要的网页..............................................................................49 第六节 搜集信息的类型..............................................................................................52 第七节本章小结..........................................................................................................54 iii 第四章对搜集信息的预处理...................................................................................55 第一节 信息预处理的系统结构..................................................................................55 第二节 索引网页库......................................................................................................56 第三节 中文自动分词..................................................................................................58 第四节分析网页和建立倒排文件..............................................................................64 第五节本章小结..........................................................................................................66 第五章信息查询服务...............................................................................................67 第一节 查询服务的系统结构......................................................................................67 第二节 检索的定义......................................................................................................68 第三节 查询服务的实现..............................................................................................69 一、 结果集合的形成..............................................................................................69 二、 查询结果显示.................................................................................................70 第四节 本章小结..........................................................................................................72 中篇 对质量和性能的追求.....................................................................................73 第六章可扩展搜集子系统.......................................................................................75 第一节 天网系统概述和集中式搜集系统结构...........................................................75 一、 天网系统结构.................................................................................................75 二、 集中式搜集系统..............................................................................................76 第二节 利用并行处理技术高效搜集网页的一种方案...............................................82 一、 节点间URL的划分策略..................................................................................83 二、 关于性能的讨论..............................................................................................86 三、 性能测试和评价..............................................................................................88 四、 系统的动态可配置性设计..............................................................................91 第三节 本章小结..........................................................................................................93 第七章网页净化与消重...........................................................................................95 第一节 网页净化与元数据提取..................................................................................95 一、 引言.................................................................................................................95 二、 DocView模型..................................................................................................98 三、 网页的表示.....................................................................................................99 四、 提取DocView模型要素的方法.....................................................................103 五、 模型应用及实验研究....................................................................................108 第二节 网页消重算法................................................................................................112 一、 消重算法.......................................................................................................112 iv 二、 算法评测.......................................................................................................115 第八章高性能检索子系统.....................................................................................120 第一节 检索系统基本技术........................................................................................121 一、 系统设计与结构............................................................................................121 二、 索引创建.......................................................................................................124 三、 检索过程.......................................................................................................126 第二节 倒排文件性能模型........................................................................................127 一、 引言...............................................................................................................128 二、 倒排文件的概念............................................................................................129 三、 倒排文件的一种性能模型............................................................................131 四、 结合计算机性能指标的考虑........................................................................136 第三节 混合索引技术................................................................................................138 一、 引言...............................................................................................................138 二、 混合索引原理...............................................................................................139 三、 混合索引实现...............................................................................................141 第四节 倒排文件缓存机制........................................................................................144 一、 引言...............................................................................................................144 二、 倒排文件缓存...............................................................................................145 三、 负载特性.......................................................................................................147 四、 缓存策略的选择............................................................................................149 第五节 本章小结........................................................................................................149 第九章用户行为的特征及缓存的应用.................................................................151 第一节 用户查询与点击日志....................................................................................152 第二节 用户行为特征的统计分析............................................................................154 一、 用户查询词的分布情况................................................................................154 二、 雷同查询词的衰减统计................................................................................155 三、 相邻N项查询词的偏差分析.........................................................................156 四、 用户在输出结果中的翻页情况统计............................................................158 五、 用户点击URL的分布情况............................................................................159 六、 考虑与不考虑查询项时点击URL分布的对比分析....................................160 七、 查询过程的自相似性....................................................................................161 第三节 查询缓存的使用............................................................................................164 一、 基于用户行为的启示....................................................................................164 二、 缓存替换策略研究........................................................................................165 v 第四节 用户行为与WEB信息的分布特征.................................................................167 一、 基本术语.......................................................................................................167 二、 海量Web信息的特征分析.............................................................................168 第十章相关排序与系统质量评估.........................................................................173 第一节 传统IR的相关排序技术................................................................................173 第二节 链接分析与相关排序....................................................................................176 一、 链接分析.......................................................................................................176 二、 Web查询模式下的新信息............................................................................178 第三节 相关排序的一种实现方案............................................................................182 一、 形成网页中词项的基本权重........................................................................183 二、 利用链接的结构............................................................................................185 三、 收集用户反馈信息........................................................................................187 四、 计算最终的权重............................................................................................189 第四节 搜索引擎系统质量评估................................................................................191 一、 引言...............................................................................................................191 二、 查询类别分析与查询集的构建....................................................................192 三、 评估实验的建立与分析................................................................................193 下篇 面向主题和个性化的WEB信息服务..........................................................196 第十一章中文网页自动分类技术.........................................................................197 第一节 引言................................................................................................................197 第二节 文档自动分类算法的类型............................................................................197 第三节 实现中文网页自动分类的一般过程.............................................................199 第四节 影响分类器性能的关键因素分析.................................................................201 一、 实验设置.......................................................................................................201 二、 训练样本.......................................................................................................202 三、 特征选取.......................................................................................................207 四、 分类算法.......................................................................................................210 五、 截尾算法.......................................................................................................216 六、 一个中文网页分类器的设计方案................................................................218 第五节 天网目录导航服务........................................................................................219 一、 问题的提出...................................................................................................219 二、 天网目录导航服务的体系结构....................................................................220 三、 天网目录的运行实例....................................................................................221 第六节 本章小结........................................................................................................221 vi 第十二章搜索引擎个性化查询服务.....................................................................223 第一节 基于WEB挖掘的个性化技术.........................................................................223 一、 Web挖掘技术................................................................................................224 二、 典型个性化Web服务系统的比较.................................................................225 三、 基于Web挖掘的个性化技术的发展.............................................................226 第二节 天网知名度系统............................................................................................227 一、 系统结构.......................................................................................................227 二、 网页与命名实体的相关度评价....................................................................231 第十三章面向主题的信息搜集与应用.................................................................235 第一节 主题信息的搜集............................................................................................235 一、 主题信息分布的局部性................................................................................235 二、 一种主题信息搜集系统................................................................................236 第二节 主题信息的一种搜集与处理模型及其应用.................................................238 一、 模型设计.......................................................................................................238 二、 应用实验:以“十六大”为主题................................................................242 三、 总结与讨论...................................................................................................244 参考文献...................................................................................................................245 附录. 术语................................................................................................................256 后记...........................................................................................................................264 vii 图示 图1-1 2003年8月20日在天网上检索“伊拉克战争”的结果................3 图1-2 2003年8月20日在搜狐上检索“伊拉克战争”的结果................5 图2-1 搜索引擎示意图................................................................................17 图2-2 搜索引擎三段式工作流程................................................................18 图2-3 搜索引擎的体系结构........................................................................26 图3-1 TSE搜索引擎界面..............................................................................31 图3-2 TSE查询结果页面..............................................................................32 图3-3 TSE网页快照页面..............................................................................32 图3-4 TSE系统结构.....................................................................................33 图3-5 Web信息的搜集.................................................................................34 图3-6 Sockets和端口....................................................................................39 图3-7 通过Socket建立连接.........................................................................40 图3-8 Web象个海洋.....................................................................................51 图4-1 网页预处理系统结构........................................................................55 图4-2 原始网页库中的记录格式................................................................56 图4-3 索引网页库算法................................................................................57 图4-4 正向减字最大匹配算法流程............................................................61 图4-5 切词算法流程....................................................................................62 图4-6分析网页与建立倒排文件流程.........................................................64 图4-7 过滤网页中非正文信息算法............................................................64 图4-8 正向索引表记录格式........................................................................65 图4-9 由正向索引建立反向索引................................................................65 图5-1 信息查询的系统结构........................................................................67 图5-2 基本检索算法....................................................................................69 图5-3 动态摘要算法....................................................................................71 图5-4 用户查询日志的记录格式................................................................71 图6-1 天网系统概貌....................................................................................76 图6-2 搜集系统的主控结构........................................................................78 图6-3 协调进程工作算法............................................................................85 图6-4 分布式Web搜集系统结构.................................................................86 图6-5 负载方差...........................................................................................89 图6-6 n个节点并行搜集系统及集中式系统性能随时间的变化...............90 图6-7 分布式系统效率................................................................................91 viii 图6-8 URL两阶段映射.................................................................................92 图7-1 用DocView模型提取的网页要素.....................................................99 图7-2 净化后的网页....................................................................................99 图7-3 HTML Tree 结构.............................................................................101 图7-4 内容块权值传递过程......................................................................102 图7-5 有主题网页DocView模型生成过程...............................................105 图7-6 计算网页特征项权值的算法..........................................................105 图7-7 正文段落识别过程..........................................................................106 图7-8 基于anchor text的超链选取算法....................................................107 图7-9 网页净化前后分类效果对比..........................................................109 图7-10 查全率随选取关键词个数的变化................................................117 图8-1 检索系统集成框架结构..................................................................122 图8-2 天网WWW检索分布式系统构架...................................................123 图8-3 倒排文件结构示意图......................................................................130 图8-4 英语单词和汉语字符的ITF分布....................................................136 图8-5 扩展词典树结构示例......................................................................143 图8-6 扩展词典匹配查找算法..................................................................144 图8-7 搜索引擎检索系统缓存结构..........................................................145 图8-8 文档数据访问对象大小分布..........................................................148 图8-9 I/O与PAGE序列序号-频度分布......................................................148 图8-10 I/O与PAGE序列时间间隔分布.....................................................149 图8-11 I/O和PAGE序列中唯一模式串......................................................149 图9-1 查询词的分布情况..........................................................................154 图9-2 查询词分布函数及其拟合函数......................................................155 图9-3 雷同查询词的衰减..........................................................................156 图9-4 相邻1000项查询词的频率的差的平方和....................................157 图9-5用户翻页情况统计...........................................................................158 图9-6 用户点击URL的分布情况..............................................................159 图9-7 考虑查询项与否的URL分布情况..................................................160 图9-8 相邻500项中不同查询项的分布..................................................162 图9-9 相邻1000项中不同查询项的分布................................................162 图9-10 相邻2000项中不同查询项的分布..............................................163 图9-11 查询项分布的自相似性特征........................................................163 图9-12 FIFO、LRU和带衰减的LFU的缓存命中率比较.........................166 图9-13 3种替换策略的局部比较..............................................................166 图9-14 网页的被访问次数........................................................................169 ix 图9-15 用户点击url对应网页的入度.......................................................170 图9-16 用户点击url对应网页的镜像度...................................................170 图9-17 用户点击url对应网页的目录深度...............................................171 图9-18 站内网页的树状结构....................................................................171 图10-1 Inktomi提供的几种搜索引擎技术的比较....................................179 图10-2 词典在系统中的地位....................................................................180 图10-3 新词学习.......................................................................................181 图10-4 网页的互联结构示意....................................................................185 图11-1 自动文档分类算法的分类............................................................199 图11-2 中文网页自动分类的一般过程....................................................200 图11-3 中文网页分类器的工作原理图....................................................200 图11-4 WebSmart —一个网页实例集搜集和整理工具...........................204 图11-5 一种中文网页的分类体系............................................................205 图11-6 Macro-F1值随样本数的变化..........................................................206 图11-7 Micro-F1值随样本数的变化..........................................................206 图11-8 CHI、IG、DF、MI的比较(Macro-F1).....................................209 图11-9 CHI、IG、DF、MI的比较(Micro-F1).....................................210 图11-10 kNN与NB分类结果的比较..........................................................213 图11-11 k的取值对分类器质量的影响(Marco-F1)..............................214 图11-12 k的取值对分类器质量的影响(Micro-F1)...............................214 图11-13 兰式距离法与欧式距离法对12个不同类别的分类情况........215 图11-14 基于层次模型的kNN与基本kNN的比较...................................216 图11-15 RCut和SCut截尾算法的比较.......................................................218 图11-16 天网目录的体系结构..................................................................220 图11-17 天网目录导航服务......................................................................221 图12-1 Web个性化的实质.........................................................................224 图12-2 Web挖掘的分类.............................................................................224 图12-3 网页与实体相关度的建立............................................................228 图12-4 个性化知名度示意图....................................................................228 图12-5 “天网知名度”系统结构............................................................230 图13-1 页面对的平均相关性....................................................................236 图13-2 Foused Crawler的系统结构...........................................................237 图13-3 用于表达网上主题新闻强度指标的立方体................................240 图13-4 十六大网页数量在10月22至11月24期间的变化情况........244 x 表格 表4-1 网页索引文件.......................................................................................................58 表4-2 URL索引文件........................................................................................................58 表6-1 Soif数据描述..........................................................................................................78 表6-2 Soif具体语法..........................................................................................................80 表6-3 参照序列,假设节点数为2...............................................................................89 表7-1 类别编号对照表.................................................................................................110 表7-2 消重实验结果.....................................................................................................111 表7-3 当N=10、δ=0.01时5种算法的查全率和准确率.....................................116 表7-4 考察δ的取值对算法3和4的影响..............................................................117 表7-5 分段签名算法的时间复杂度及性能..............................................................118 表7-6 基于关键词的各算法的时间复杂度及性能 (N=10, δ=0.01)..................118 表8-1 英汉词频统计排序对照...................................................................................134 表8-2 一些典型磁盘的性能数据...............................................................................136 表8-3 数据集基本统计信息.......................................................................................146 表9-1 用户在前5页的翻页情况统计......................................................................158 表9-2 调整后的LFU与LRU命中率的比较..............................................................166 表9-3 各网页参数的分布............................................................................................169 表10-1新词学习对检索准确率的影响.....................................................................182 表10-2 影响权值的HTML标签.................................................................................184 表10-3 补偿因子定义表..............................................................................................188 表10-4 用户查询信息类别..........................................................................................193 表11-1 样本集中类别及实例数量的分布情况表...................................................203 表11-2 kNN和NB算法的分类质量和分类效率比较..............................................213 表11-3 欧式距离与兰式距离的比较........................................................................215 表11-4 基于层次模型的kNN与基本kNN的比较...................................................216 表11-5 RCut和SCut截尾算法的比较.........................................................................217 表11-6 一个分类器的设计方案.................................................................................218 表12-1 典型Web个性化系统的比较.........................................................................225 表12-2 天网知名度系统与其他检索系统的横向比较结果.................................232 表12-3 天网知名度系统的纵向比较结果................................................................234
- 粉丝: 7
- 资源: 7
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助