1. 文档
    1. 文档频率(document frequency),出现某词项的文档的数目
    2. 索引粒度(indexing granularity)
      1. 索引粒度太小
        1. 由于词项散布在多个细粒度文档中,可能错过重要的段落,正确率高而召回率低
      2. 索引粒度太大
        1. 可能找到很多不相关的匹配结果,即正确率低而召回率高 可以通过采用显式或隐式的邻近搜索方法来缓解
  2. 布尔检索
    1. 由布尔值构成的词项-文档关联矩阵
      1. 稀疏矩阵
    2. 一个普遍问题就是采用 AND 操作符产生的结果正确率虽高但是召回率偏低,而采用 OR 操作符召回率高但是正确率低
    3. 接受布尔表达式查询,AND,OR,NOT
    4. 额外的运算方式:词项邻近(term proximity)
  3. 排序检索模型(ranked retrieval model)
    1. 往往是采用一个或者多个词来构成自由文本查询(free text query)
  4. 容错式检索
    1. 词典搜索的数据结构
      1. 哈希表
        1. 由于查询词项稍有变化后哈希函数会生成截然不同的结果, 哈希表方式难以处理查询词项存在轻微变形的情况
      2. 搜索树
        1. 二叉搜索树
          1. 支持前缀式查询
          2. 二叉树的平衡性是实现高效搜索的关键
    2. 通配符查询
      1. 通配符出现在尾部
        1. 基于搜索树的词典结构很方便
      2. 通配符出现在头部
        1. 反向 B-树(reverse B-tree)结构
      3. 单通配符出现在中间
        1. 正向和反向的交集
      4. 一般的通配符查询
        1. 轮排索引
          1. 在字符集中引入一个新的符号$,标识词项结束。 构建一个轮排索引,每个旋转结果都指向原始词项。
          2. 轮排词汇表
        2. k-gram 索引
          1. 采用k-gram索引会导致非预期的结果, 需要引入一个后过滤(postfiltering)步骤
    3. 拼写校正
      1. 基本原则
        1. 选择距离“ 最近” 的那个
        2. 选择更常见的那个
      2. 校正方法
        1. 在词项独立的校正方法
          1. 编辑距离方法
          2. 动态规划算法
          3. 推广开来:不同的编辑操作可以具有不同权重
          4. 穷举的计算编辑距离的开销很大
          5. 启发式方法:利用轮排索引。通过遍历B-树来访问轮排索引。返回旋转结果中以某个旋转开头的词项。
          6. k-gram 重合度方法
          7. 一旦返回这些词项之后,利用k-gram 索引, 就能从中找出与q 具有最小编辑距离的词
        2. 上下文敏感(context-sensitive)的校正方法
          1. 对每个单词找到拼写正确词,对短语中的每个词进行替换
          2. 对每个替换后的短语,搜索引擎进行查找并确定返回数目
          3. 穷举过程的开销会非常大,可以只保留文档集合或查询日志中的高频组合结果
        3. 基于发音的校正方法
          1. 进行语音哈希操作,发音相似的词项被映射为同一值
  5. 文档评分
    1. 参数化索引
      1. 大多数文档都具有额外的结构信息
      2. 词典常常来自固定的词汇表(比如语言种类的集合、日期的集合等)
    2. 域索引
      1. 词典中应该收集来自域中自由文本的所有词汇
      2. 通常可以把文档的标题和摘要看作域
      3. 可以通过对域进行编码来减少上述索引中词典的规模
        1. 能支持域加权评分(weighted zone scoring)技术的使用
          1. 权重学习
          2. 最优权重g 的计算
    3. 词项频率(term frequencey)
      1. t 在文档中的出现次数
      2. 词袋模型(bag of words model)
        1. 词项在文档中的出现次序被忽略,但是出现的次数非常重要
      3. 问题:所有的词项都被认为是同等重要的
    4. 逆文档频率 idf inverse document frequency
      1. 文档集频率(collection frequency)
        1. 词项在文档集中出现的次数,高的词项赋予低的权重
      2. 文档频率(document frequency)
        1. 表示的是出现 t 的所有文档的数目
      3. df 本身较大,需要将它映射到一个较小的取值范围中
        1. 公式
      4. tf-idf 权重计算
        1. 公式
        2. 权重赋予方式
          1. 当 t 只在少数几篇文档中多次出现时,权重取值最大 (此时能够对这些文档提供最强的区分能力)
          2. 当 t 在一篇文档中出现次数很少,或者在很多文档中出现,权重取值次之(此时对最后的相关度计算作用不大)
          3. 如果 t 在所有文档中都出现,那么权重取值最小
        3. 其他方法,替换原有的 tf
          1. tf 的亚线性尺度变换方法
          2. 基于最大值的tf 归一化
      5. 为什么采用df 而不是cf
        1. 文档评分的目的是区分文档,最好采用基于文档粒度的统计量
    5. 向量空间模型(vector space model,简称VSM)
      1. 其中每个分量代表词项在文档中的相对重要性
      2. 也可以将查询表示成向量
        1. 可以通过计算给定的查询向量和每个文档向量的相似度来对所有文档进行排名
    6. 文档长度的回转归一化
  6. 检索系统中的评分
    1. 利用倒排记录表
      1. 对于词典中的每个词,我们都保存其idf 值
      2. 每条倒排记录中都会保存词项在当前文档中的tf 值
    2. 非精确返回前 K 篇文档
      1. 显著降低输出前K 篇文档所需要的计算复杂度
      2. 方法
        1. 索引去除技术
          1. 只考虑那些词项的 idf 值超过一定阈值的文档
          2. 只考虑包含多个查询词项(特例:包含全部查询词项)的文档
        2. 胜者表
          1. 对于词典中的每个词项 t,预先计算出 r 个最高权重的文档
          2. 对查询中所有词项的胜者表求并集,并可以生成集合 A
          3. 只有 A 中的文档才可以参加最后的余弦相似度运算
        3. 静态得分和排序
          1. 每篇文档 d 往往都有一个与查询无关的静态得分 g(d)
          2. 文档的最后得分就可以定义为g(d)和某个与查询相关的得分
          3. 倒排记录表按照 g(d) 的大小进行统一排序
          4. 维持两个无交集的倒排文件表
          5. 高端表,由 m 篇具有最高 tf 值的文档组成
          6. 低端表,则由剩下的包含 t 的文档组成
          7. 首先对词项的高端表进行扫描,计算在所有或超过给定数目的查询词项的高端表中的每篇文档的最后得分值。如果该过程能够产生前K 篇得分最高的文档,则处理结束。否则,需要继续扫描低端表并计算其中文档的得分。
        4. 影响度排序
          1. 将词项 t 对应的所有文档 d 按照 tft, d 值降序排列
        5. 簇剪枝方法
          1. 我们先对文档向量聚类来进行预处理操作,然后在查询时,我们只考虑利用少数几个簇中的文档进行余弦相似度计算。
    3. 查询词项的邻近性
      1. 希望返回的文档中大部分或者全部查询词项之间的距离比较近
      2. 返回的文档中包含所有查询词项的最小窗口大小为 ω, ω 的值越小,文档d和查询匹配程度更高
      3. 接近“ 软合取” (soft conjunctive)语义
    4. 搜索系统中自由文本查询的传递路径
    5. 利用向量空间模型实现查询操作
      1. 布尔查询
        1. 数学上实际上存在一种称为 p 范式(p-norm)的方法来融合布尔和向量空间查询
      2. 通配符查询
        1. 把查询中的通配符解释成向量空间模型中的一系列查询词项
      3. 短语查询
        1. 由于词项的次序信息在文档转换成向量的过程中被丢失,所以将文档表示成向量在理论上存在着明显的损失。
  7. 效果评价
    1. 黄金标准(gold standard)或绝对真理(ground truth)
      1. 对于用户信息需求,将测试集中的每篇文档的相关性判定看成一个二类分类问题进行处理,并给出判定结果:相关或不相关
    2. 无序检索结果集合的评价
      1. 正确率(Precision)
        1. 返回的结果中真正和信息需求相关的文档所占的百分比
      2. 召回率(Recall)
        1. 所有和信息需求真正相关的文档中被检索系统返回的百分
      3. 一个融合了正确率和召回率的指标是F 值(F measure)
        1. 默认正确率和召回率的权重相等,即 α = 1/2 或 β = 1
    3. 有序检索结果的评价方法
      1. MAP(mean average precision,平均正确率均值)
        1. MAP 是所有单个信息需求上的平均正确率的均值。即使有些查询的相关文档数目较多而有些却很少,但是在最终的MAP 指示报告中每个信息需求的作用却是相等的。
        2. 实际是在所有的召回率水平上计算正确率
      2. 前 k 个结果的正确率(precision at k,可简写成P@k)
        1. 对于Web 搜索,用户看重的是在第1 页或前3 页有多少好结果
        2. 需要在固定的较少数目(如10 或者30 篇文档)的结果文档中计算正确率
        3. 优点是不需要计算相关文档集合的数目
        4. 缺点就是它在通常所用的指标中是最不稳定的, 这是因为相关文档的总数会对P@k 有非常强的影响
      3. R-precision
      4. ROC(receiver operating characteristics)
      5. CG (cumulative gain,累积增益)
        1. NDCG(normalized discounted cumulative gain,归一化折损累积增益)
    4. 相关性判定
      1. 给定信息需求集及文档集,需要给出它们之间的相关性判定情况,这是一项需要人工参与的费时费力的工作
    5. 系统质量及用户效用
      1. 点击日志分析(clickthrough log analysis)
      2. 点击流挖掘(clickstream mining)
    6. 结果片段(snippet)
      1. 提供结果的一个短摘要,能够帮助用户确定结果的相关性
        1. 静态(static)摘要
          1. 不随查询变化而变化
        2. 动态(dynamic)摘要
          1. 根据查询所推导出的信息需求来进行个性化生成
  8. 链接分析
    1. PageRank
  9. 层次聚类
  10. 扁平聚类
    1. 聚类是无监督学习(unsupervised learning)的一种最普遍的形式
    2. 分类是监督学习的一种形式,其目标是对人类赋予数据的类别差异进行学习或复制
    3. 而在以聚类为重要代表的无监督学习当中,并没有这样的人来对类别的差异进行引导
    4. 聚类假设:在考虑文档和信息需求之间的相关性时,同一簇中的文档表现互相类似。
    5. 搜索结果聚类可以将相似的文档放在一起呈现。通常来说,浏览几个内容连贯的文档子集会比浏览一篇篇独立的文档更容易
    6. 聚类算法的主要应用
      1. 搜索结果聚类可以将相似的文档放在一起呈现
      2. 给出了一个更好的用户界面,这也是分散-集中(scatter-gather)方法的目标
      3. 基于倒排索引获得初始文档集,然后将处于同一簇中、甚至与查询相似度不高的其他文档也会加入到结果文档集合
    7. 聚类算法的评价
      1. 利用已有的分类文档集合作为评价基准或黄金标准
  11. 机器学习
    1. 基于机器学习评分
    2. 基于机器学习的检索结果排序
  12. 概率检索模型
    1. BM25 权重计算机制(BM25 weighting scheme) 或Okapi 权重计算机制(Okapi weighting)
      1. tftd 是词项 t 在文档 d 中的权重,Ld 和 Lave 分别是文档 d 的长度及整个文档集中文档的平均长度。
      2. k1 是一个取正值的调优参数,用于对文档中的词项频率进行缩放控制。
        1. 如果 k1 取0,则对应BIM模型
        2. 如果 k1 取较大的值,那么对应于使用原始词项频率
      3. b 是一个调节参数,(0≤ b≤ 1),决定文档长度的缩放程度
        1. b = 1 表示基于文档长度对词项权重进行完全的缩放
        2. b = 0 表示归一化时不考虑文档长度因素
  13. XML 检索
    1. 为结构化检索(structured retrieval)
    2. 挑战性问题
      1. 用户希望返回文档的一部分(即 XML 元素),而不像非结构化检索那样往往返回整个文档
        1. 系统应该总是检索出回答查询的最明确最具体的文档部分
      2. 对文档的哪些部分进行索引
        1. 将节点分组,形成多个互不重叠的伪文档(pseudodocument)
          1. 缺点是,由于这些伪文档的内容并不连贯,所以它们对用户而言可能没有什么意义
        2. 使用最大的一个元素作为索引单位,然后通过对结果进行后处理,从而找到更适合作为答案的子元素。(自顶向下)
        3. 直接对所有叶节点进行搜索并返回最相关的一些节点,然后通过后处理将它们扩展成更大的单位(自底向上)
  14. 查询优化(query refinement)
    1. 布尔查询
      1. 考虑倒排记录表的访问顺序
    2. 全局方法
      1. 查询扩展方法
        1. 使用人工编辑的一部受控词汇表
        2. 基于同义词词典(thesaurus)或 WordNet 的查询扩展
        3. 自动构造同义词词典
          1. 构建方法
          2. 一种方法是简单地使用词共现信息
          3. 更具鲁棒性(它不可能会产生分析器出错所导致的错误)
          4. 采用浅层语法分析器来分析文本得到词汇之间的语法关系或语法依存性
          5. 有可能会更精确
        4. 拼写校正
        5. 基于查询日志挖掘进行查询重构
    3. 局部方法
      1. RF(relevance feedback,相关反馈)
        1. 在检索过程中通过用户交互来提高效果
        2. 图像搜索是一个使用相关反馈的很好的例子
        3. 因为在图像搜索中返回的结果非常直观
        4. Rocchio 相关反馈算法
          1. 最优的查询向量等于相关文档的质心向量和不相关文档的质心向量的差
          2. 可以同时提高召回率和正确率
        5. 相关反馈的成功依赖于某些假设
          1. 用户必须要有足够的知识来建立一个不错的初始查询, 该查询至少要在某种程度上接近需求文档
          2. 相关反馈方法要求相关文档之间非常相似
      2. 伪相关反馈
        1. 首先进行正常的检索过程,返回最相关的文档构成初始集,然后假设排名靠前的k 篇文档是相关的,最后在此假设上像以往一样进行相关反馈
        2. 缺点,出现不必要的主题偏移
      3. 间接相关反馈
        1. 收集用户的大量隐式反馈信息
  15. 索引压缩
    1. 优点
      1. 节省磁盘空间
      2. 能增加高速缓存(caching)技术的利用率
      3. 加快数据从磁盘到内存的传输速度
    2. 统计特性
      1. 预处理对词典大小和无位置信息倒排记录的数目影响很大
      2. Heaps 定律
        1. 词项数目的估计
          1. 文档集大小和词汇量之间可能存在的最简单的关系是它们在对数空间(log-log space)中存在线性关系,并且这种线性关系往往和实际情况相吻合。
        2. 两点假设
          1. 随着文档增加,词汇量会持续增长而不会稳定到一个最大值
          2. 大规模文档集的词汇量也会非常大
      3. Zipf 定律
        1. 对词项的分布建模
          1. 如果t1 是文档集中的出现最多的词项,t2 是文档集中的出现第二多的词项,依此类推,那么,排名第i 多的词项的文档集频率cfi 与1/i 成正比
    3. 词典压缩
      1. 主要目的是将词典放入内存,获得很高的查询吞吐率
      2. 词典数据结构
        1. 采用定长数组,所有词项按照词典序排序
          1. 缺点
          2. 存在着明显的空间浪费
          3. 优化
          4. 将所有的词项合成一个长字符串并给每个词项增加定位指针
        2. 按块存储
          1. 将长字符串中的词项进行分组变成大小为k 的块, 然后对每个块只保留第一个词项的指针
          2. 前端编码,提取公共前缀
    4. 倒排记录表压缩
      1. 按字节压缩
        1. VB(Variable byte, 可变字节)编码利用整数个字节来对间距编码
      2. 按位压缩
        1. γ 编码
          1. 实际结果与计算结果有误差
          2. Zipf 定律实际文档集的词项频率实际分布的估计不是很准确
          3. 间距并不满足均匀分布
  16. 索引构建
    1. 基于块的排序索引方法
      1. 必须使用基于磁盘的外部排序算法
    2. 内存式单遍扫描索引构建方法
    3. 分布式索引构建方法
      1. 基于 MapReduce
    4. 动态索引构建方法
      1. 要求能够及时检索到新文档
        1. 同时保持两个索引
    5. 考虑文档对不同用户的可见性
      1. 考虑拼写校正之类的影响
  17. 倒排索引
    1. 每个词项都有一个记录出现该词项的所有文档的列表, 该表中的每个元素记录的是词项在某文档中的一次出现信息
      1. 该信息中往往还包括词项在文档中出现的位置
    2. 这个表中的每个元素通常称为倒排记录(posting)
    3. 每个词项对应的整个表称为倒排记录表(posting list)
      1. 快速合并算法
        1. 基于跳表
          1. 在每个 根号P 处均匀放置跳表指针,其中 P 是倒排记录表的长度
      2. 表中的记录的排序方式
        1. 对于布尔检索,按文档 ID 排序
        2. 对于排序式检索,基于权重或影响度排序
    4. 所有词项的倒排记录表一起构成全体倒排记录表(postings)
      1. 所有的词项组成词典
    5. 每个倒排记录表存储了词项出现的文档列表,也可以存储一些其他信息,比如词项频率,词项在文档中出现的位置
      1. 词项在文档中出现的位置,可用于短语查询
    6. 二元词索引
      1. 是将文档中每个接续词对看成一个短语
    7. 混合索引机制
      1. 对高频常见的短语使用短语索引或只使用二元词索引, 而对其他短语查询则采用位置索引
      2. 再优化:部分后续词索引
        1. 对每个词项,有个后续词索引记录了它在文档中的下一个词项
  18. 词项
    1. 索引的单位
    2. 词条化(tokenization)
      1. 将每篇文档转换成一个个词条(token)的列表,这个过程通常称为词条化(tokenization)
      2. 不对数字、URL 等词条进行索引,避免显著扩大索引的词汇量
      3. CJK语言,先进行分词
        1. 基于词典的最大匹配法
        2. 基于机器学习序列模型的方法
        3. 短字符序列的方法(如k-gram )
      4. 停用词
        1. 采用好的压缩技术来降低常用词倒排记录表的存储开销
        2. 词项权重计算方法能将高频常用词对文档排序的影响降至极低
        3. 不论是对于索引大小还是查询处理的时间而言,不去除停用词所增加的开销并没有那么大
    3. 归一化
      1. 就是将看起来不完全一致的多个词条归纳成一个等价类,以便在它们之间进行匹配的过程
      2. 常规的做法是隐式地建立等价类
        1. 等价类的建立过程是隐式的,不需要事先计算出等价类的全部元素,在映射规则下输出相同结果的词项一起构成等价类集合
        2. 构建“ 去除字符” 这种映射规则比较容易
      3. 另一种方法是维护多个非归一化词条之间的关联关系
        1. 可以进一步扩展成同义词词表的构建
        2. 增加了一部查询扩展词典,因此在查询处理时需要更多的时间
      4. 另一种方式是在索引构建时就对词进行扩展
        1. 需要更多的存储空间来存储倒排记录
      5. 处理外来词或者复合词时,拼写不明确或者音译标准不同会产生不同的拼写结果。一种做法是采用启发式方法来建立等价类,或者根据发音相同来进行词项扩展。
      6. 词干还原和词形归并
        1. 词干的精确形式本身并不重要,重要的是能够得到等价类
      7. 意味着从不同关联词出发可以进行不对称的扩展
    4. 词项频率(term frequency,即词项在文档中出现的次数)