信息检索与数据挖掘 2019/3/16 1 信息检索与数据挖掘 第5章向量模型及检索系统 一一第一讲向量模型
信息检索与数据挖掘 2019/3/16 1 信息检索与数据挖掘 第5章 向量模型及检索系统 ——第一讲 向量模型
信息检索与数据挖掘 2019/3/16 3 本讲提纲 回顾 排序式检索 词项频率 tf-idf权重计算 向量空间模型
信息检索与数据挖掘 2019/3/16 3 本讲提纲 ❶ 回顾 ❷ 排序式检索 ❸ 词项频率 ❹ tf-idf权重计算 ❺ 向量空间模型
信息检索与数据挖掘 2019/3/16 4 本讲提纲 ①回顾 2 排序式检索 3 词项频率 tf-idf权重计算 ⑤向量空间模型
信息检索与数据挖掘 2019/3/16 4 ❶ 回顾 ❷ 排序式检索 ❸ 词项频率 ❹ tf-idf权重计算 ❺ 向量空间模型 本讲提纲
信息检索与数据挖掘 2019/3/16 5 回顾：布尔检索 ·文档表示 ·一个文档被表示为关键词的集合 ·查询表示 。 查询式(Queries)被表示为关键词的布尔组合，用“与、 或、非”连接起来（主析取范式D丽 ) ·相关度计算 ·一个文档当且仅当它能够满足布尔查询式时，才将其检 索出来 ·检索策略是二值匹配
信息检索与数据挖掘 2019/3/16 5 回顾：布尔检索 • 文档表示 • 一个文档被表示为关键词的集合 • 查询表示 • 查询式(Queries)被表示为关键词的布尔组合，用“与、 或、非”连接起来（主析取范式DNF ） • 相关度计算 • 一个文档当且仅当它能够满足布尔查询式时，才将其检 索出来 • 检索策略是二值匹配
信息检索与数据挖掘 2019/3/16 6 回顾：倒排索引 倒排记录 Brutus 1 2 4 11 31 45173 174 Caesar 2 4 56 1657 132 Calpurnia 2 31 54 101 词项词典 倒排记录表 Dictionary Postings List
信息检索与数据挖掘 2019/3/16 6 回顾：倒排索引 词项词典 倒排记录表 倒排记录 Brutus Calpurnia Caesar 1 2 4 5 6 16 57 132 1 2 4 11 31 45 173 2 31 174 54 101 Dictionary Postings List
信息检索与数据挖掘 2019/3/16 7 回顾：词典的建立及扩展的倒排索 引 ●如何建立词项词典？ ●文档解析：格式？语言？编码方式？ ●词条化：词条(Tokens)/词项（Terms) ●停用词：停用词表？查表法or基于文档频率 ●词项归一化：等价类←→同义词扩展表 ●词形归并：am,are,is→be ●词千还原：去除单词两端词缀、Porter算法 ●如何实现倒排记录表？ ·跳表：跳表指针（位置、个数、更新问题） ·短语查询 ·二元词索引→扩展的二元词索引：词性标注 ·位置信息索引→邻近查询 ·混合索引机制
信息检索与数据挖掘 2019/3/16 7 回顾：词典的建立及扩展的倒排索 引 如何建立词项词典？ 文档解析：格式？语言？编码方式？ 词条化：词条（Tokens）/词项（Terms） 停用词：停用词表？查表法 or 基于文档频率 词项归一化：等价类同义词扩展表 词形归并：am, are, is be 词干还原：去除单词两端词缀、Porter算法 如何实现倒排记录表？ • 跳表:跳表指针(位置、个数、更新问题） • 短语查询 • 二元词索引扩展的二元词索引：词性标注 • 位置信息索引邻近查询 • 混合索引机制
信息检索与数据挖掘 2019/3/16 8 回顾：索引构建 ·基于排序的索引构建算法 。它是一种最原始的在内存中进行倒排的方法 ·基于块的排序索引算法 ·合并排序操作对于基于磁盘的排序来说很高效（避免寻道） ·内存式单遍扫描索引构建算法 ·没有全局的词典 ·对每个块都生成单独的词典 ·不对倒排记录进行排序 。有新的倒排记录出现时，直接在倒排记录表中增加一项 ·采用MapReduce的分布式索引构建算法 ·动态索引构建算法：多个索引，对数合并
信息检索与数据挖掘 2019/3/16 8 回顾：索引构建 • 基于排序的索引构建算法 • 它是一种最原始的在内存中进行倒排的方法 • 基于块的排序索引算法 • 合并排序操作对于基于磁盘的排序来说很高效(避免寻道) • 内存式单遍扫描索引构建算法 • 没有全局的词典 • 对每个块都生成单独的词典 • 不对倒排记录进行排序 • 有新的倒排记录出现时，直接在倒排记录表中增加一项 • 采用MapReduce的分布式索引构建算法 • 动态索引构建算法：多个索引，对数合并
信息检索与数据挖掘 2019/3/16 9 回顾：索引压缩 。 词项的统计特性：Heaps定律和Zipf定律 ·词典压缩 ·将词典看成单一字符串、按块存储、前端编码 。倒排记录表压缩 ·可变字节编码和Y编码 文档集（文本、XML标签等） 3,600.0 MB 文档集（文本）》 960.0 词项关联矩阵 40,000.0 倒排记录表，未压缩（32位字) 400.0 倒排记录表，未压缩(20位) 250.0 倒排记录表，可变字节码 116.0 倒排记录表，V编码 101.0
信息检索与数据挖掘 2019/3/16 9 回顾：索引压缩 • 词项的统计特性：Heaps定律和Zipf定律 • 词典压缩 • 将词典看成单一字符串、按块存储、前端编码 • 倒排记录表压缩 • 可变字节编码和γ编码 文档集（文本、XML标签等） 3,600.0 文档集（文本） 960.0 词项关联矩阵 40,000.0 倒排记录表，未压缩（32位字） 400.0 倒排记录表，未压缩（20位） 250.0 倒排记录表，可变字节码 116.0 倒排记录表，γ编码 101.0 MB
信息检索与数据挖掘 2019/3/16 10 回顾：索引压缩 将整部词典看成单一字符串 ..systilesyzygeticsyzygialsyzygyszaibelyiteszecinszono... 文档频率 倒排记录表指针 词项指针 92 5 71 12 4B 4B 3B
信息检索与数据挖掘 2019/3/16 10 将整部词典看成单一字符串 回顾：索引压缩
信息检索与数据挖掘 2019/3/16 11 回顾：索引压缩 单一字符串方式下按块存储 ..7systile9syzygetic8syzygial6syzygyl1szaibelyite6szecin... 文档频率 倒排记录表指针 词项指针 9 92 → 5 → 71 12
信息检索与数据挖掘 2019/3/16 11 单一字符串方式下按块存储 回顾：索引压缩