Inverted File Index倒排索引⚓︎
定义
Index: 对于一个词/词组，查询其在诸多文档中的出现情况
Inverted file: 对于某个单词包含一系列指针，指向在所有文章中这个单词的出现位置
通过建立 Inverted file 可以便捷地从关键词定位到其出现的文章及具体位置（例如笔记本右上角的搜索就是其应用之一）
Inverted file的建立方法
为了建立 Inverted file ，需要对文章的单词进行拆分识别，同时进行一系列的字符串匹配以将文章中的单词与单词列表进行对照，而这里的字符串匹配可以使用如下方法：
-
字符串哈希
-
搜索树（B树，B+树，Trie树等）
二者各有优劣，例如哈希在模糊搜索的角度就不如搜索树。
评价指标⚓︎
对于一次搜索
| Relevant | Irrelevant | |
|---|---|---|
| Retrieved | \(R_R\) | \(I_R\) |
| Not Retrieved | \(R_N\) | \(I_N\) |
则有两个评估指标
- Precision精确度 \(P=R_R/(R_R+I_R)\)
- Recall召回率 \(R=R_R/(R_R+R_N)\)
下面为了这两个指标的提升，介绍一些优化/技术
Word Stemming⚓︎
直接建立 Inverted file 会精确匹配与其完全一致的单词，对于存在时态/单复数的英语单词来说不可接受（例如搜索 run 而不接受 running 和 runner）， word stemming 正是为了处理这个问题，提高召回率。
从目标来说， word stemming 希望将一个单词化为它的词根而去除掉变形的因素。但是由于变形的语法过于复杂（是否双写，是否变 y 为 i 等等），在实际实现时会做出一些妥协，例如会将 mate 化成 mat （这个例子是随便举的，但是确实有类似情况） 。
因此我认为 word stemming 处理过后也许精确度会有所下降。
Stop Words⚓︎
对于 a,the,it 这类单词，绝大多数的文章里面都有，如果对其建立倒排索引，对存储是不必要的负担，对搜索精确度来说也毫无益处。
所以会将这类词设为 "stop words" ，不参与 index 的过程。
这类 stop words 一般 具有较高的出现频率，但是 出现频率最高的单词不一定是 stop word ，且一份 stop words 列表不适用于所有文档。
一个简单的例子是，如果基于莎士比亚作品全集建立倒排索引， "Shakespeare" 应该成为 stop word ，但是普通搜索引擎显然不会这样设置。
Distributed Indexing⚓︎
倒排索引数据量过大，可能需要分布式存储在若干设备上，此时的分发方式及其特点如下
-
Term-partitioned Index 依据单词字典序存储，存储困难，检索容易，容灾能力差
例如一台电脑专门存储所有 A 开头单词的倒排索引。对每个单词要单独确定其应当被分发到哪台设备因此存储困难，但是在检索时可以通过字典序迅速确定应该在什么设备提取这些倒排索引。
但是如果一台设备故障，相关单词全部无法搜索，这就是容灾能力差。
-
Document-partiitioned index 依据文章划分存储，存储容易，检索困难，容灾能力好
检索时需要去不同的设备上找某单词的倒排索引，较为复杂。
但是如果一台机器故障，只会影响某些单词搜索结果的部分条目，相对来说更能接受。
Dynamic Indexing⚓︎
在处理文档的动态变化的过程中，遵循如下策略：
-
文档加入：正常插入即可
-
文档删除：攒够一定量删除请求（存在auxiliary index）统一处理（可能是 auxiliary index 写满了或者隔一段时间定期处理掉），处理时需要在main index和auxiliary index同步检索
- 树型结构太大就改用懒删除
Thresholding⚓︎
设定一定的阈值，从而提高搜索的准确率
对于搜索的文档，每个文档基于其权重进行排序，只展示权重最高的 x 份。
其优点是可以减少搜索的开销，但是在面对布尔查询（返回所有相关文档）时就失效了；且这个权重与相关性不一定正相关，因此可能遗漏部分文档。
对于询问，若询问有多个关键词，对词组按出现频率升序排列，并只基于询问中的部分词进行搜索。
相对高频的词汇在更多的文档出现因此更不具有区分度，优先利用低频词进行筛选有利于提高检索效率。
作业题⚓︎
T1：Distributed Indexing
区分两种存储方式
T3：accessing terms
