主题：[推荐]《An Introduction to Information Retrieval》参考译文之三——字典和标记列表

2 字典和标记列表
2．1 文档中的字符序列
2．1．1 获得文档字符
索引要处理的文档是一个由字节信息组成的文件，所以首先需要将这些字节信息转换为字符信息。对于以ASCII码编码的英文文本而言，这当然很简单。但是，如果对于那些采用可变单字节或者多字节的编码方式，情况就复杂的多。可以将识别字符模式的问题看成是一个机器学习中的分类问题，但是也可以采用启发式方法、用户选择、使用文档元数据等方法来识别。一旦字符编码方式确定下来，则最终的字节信息转换就很简单了。
除此以外，还要考虑文档的格式问题，必须时还需从诸如Word和Zip等某些二进制文档中将字符解码出来。即便是文本文档，额外的解码工作有时也是必须的，如XML中的字符实体，比如&就需要解码成&字符。总而言之，任何不可以直接处理的文档就必须首先将其可用的字符信息抽取出来。如对于XML文档而言，通常需要忽略相关的标签信息，类似的工作还可能应用在PDF等文件处理中。这些问题不属于信息检索的范畴，但是任何信息检索系统都需要利用一些现有的商业产品来解决各种不同类型文档的解码问题。
更为有趣的是，在一些书写方法中，甚至都不能将文本看成一个字符的线形序列，如在阿拉伯语言中，文本采用了两个不同的书写方向。当然，尽管如此，它的发音仍然表现为是一个单一的序列。现代编码系统一般采用和概念一致的顺序来组织相关字符的顺序，反向显示的问题通常提交给所在系统来处理，但是对于早期的一些编码系统却不是这样。

2．1．2 文档处理单元
下一步需要解决的问题就是决定要索引的文档单位有多大，这也被称为索引的粒度问题，它实际上是个如何协调检索精度和召回度的问题。如果单位过小，则在检索时易于丢失重要的信息，因为相关词语分布在各个不同的文档单位中；反之，如果单位过大，则又容易得到过多不相关的信息。不过，对于较大的文档单位，可以使用位置检索（proximity search）来减少不相关信息获取量。
对于一些特殊的检索，如XML文档检索，可以使用不同层次的粒度来同时构建很多索引，以实现特殊的检索效果。信息检索系统也可以允许用户执行决定索引粒度，当然，这需要用户对相关文档、用户和相应的信息检索需求都有明确的理解。

2．2 字典的定义
2．2．1 得到标识
给定现成的字符序列和文档单位，标识化就是对其再次切分成细小的单位，即标识，同时丢弃一些无用的字符，如重音符号等。
一般情况下，标识（token）和原先的词项是对应的，但是有时也会产生不一致。首先，对于相同的标识需要进行合并，所以最终得到的全部标识和原先的词项并非具有相同的数量，可以称这些不同的标识叫类型（type），同时还需删除诸如停用词等内容，所以最终被索引的词项数量会更少。
这里的主要问题在于如何正确识别标识？对于一般的情况，可以通过删除空格和重音字符等非字母字符来得到标识，但是即便是处理英文，也存在着很多难以处理的问题，如带有省略符和连字号的语句。甚至就是利用空格，也会产生问题，如带有空格的人名和地名等。
不同的处理方式会得到不同的结果。有一点可以肯定，为了保证匹配效果，应该使得对查询的处理和对文档的处理采用相同的标识抽取方法。
抽取标识的做法依赖于特定的语言和环境。如有些词语C#，必须结合特定的环境才被识别为一个标识，否则就完全可以被理解为多个标识。随着计算机技术的快速发展，诸如电子邮箱地址、Web网址、IP地址和行李条码等都成为了一些需要被看成整体的标识。一个可行的选择就是忽略对这些信息的索引，这既能简化问题，同时也能降低字典的大小。当然，这不可避免的会降低检索的能力。

2．2．2 停用词问题
一些出现频率较高的词语通常不能有效区分相关文档，所以被看成停用词。识别停用词的常见方法就是根据词语的文档频率结合人工语义过滤的方式来判断。使用停用词可以有效的减小索引字典的大小，而且这些停用词对于检索而言，意义也非常小。不过，对于词组检索（phrase search）而言就不一定了，如“As we may think”、“To be or not to be”等等。
信息检索系统所使用的停用词多的有200到300个，少的有7到12个，甚至有些系统根本没有停用词，如Web搜索引擎。虽然这样做可以增强检索的能力，但是也增加了处理负担。不过，借助一些快速算法，完全可以降低相关的性能损失。所以，现代信息检索系统往往没有采用停用词去除功能。

2．2．3 规范化
标识规范化可以将一些具有细微差别但具有相同含义的标识规范成一致的表示形式。如对于anti-discriminatory和antidiscriminatory两个标识，可以将前者规范为后者的形式，在检索时，对于任何一个标识的搜索都能得到含有任何一个标识的文档。
这种将连字符去除进行规范化的做法是一种较为简单的规范化方法，它被称为等价类方法，实际效果不错。除此以外的方法，就需要借助映射词表来完成，如可以表达同义词映射关系的规范化词表。它可以通过两种方式来实现：一是常见的方法就是仍然对没有规范的标识进行索引，但是维持着一个查询扩展列表，它可以将查询词映射为多个相关的标识，并以这些标识的查询结果一齐作为最终的查询结果；二是在构建索引时进行标识扩展，如一个包含“automobile”的文档，同时可以在“car”的索引项下进行索引，反之亦然。当然，这两种方法都存在问题，第一种方法增加了额外的查询扩展列表，需要增加查询处理时间，而第二种方法则需要更多的标记存储空间。由于使用词表映射，所以这种方法较等价类方法更为灵活和强大，用户可以自行决定映射关系。

值得注意的是，上述两种规范化方法不可滥用，特别是等价类方法，否则易于将查询扩展到不合适的范围之中。如.net映射为net将会产生严重的误检。不过，对于等价类方法而言，为了保证检索的召回度，应该对查询和文档采用相同的处理措施。
除了连字符问题外，规范化还要处理以下几个问题：
1）语音标记问题。简单的处理可以将其直接删除，事实上，大部分语言中的语音标记符号通常只用于区分读音，对它们的语义影响不大。但是，也有例外，如西班牙语言中存在这样的区分。更为重要的是，这个问题不仅仅只是索引的问题，用户也极有可能因为链入速度、懒惰、软件平台的局限性或者习惯等原因而忽略语音符号的书写。在这种情况下，最为合理的方法就是忽略所有的语音符号来对待所有的索引词语。
2）大小写问题。常见的处理方法就是将全部的字符都转换为小写。但是，另一方面，这也存在着问题，如有些诸如公司名称、政府机构名称和人名等词语就是利用大写字母开头来区别于一般的正常词语。为此，可以采用一些启发式算法只对部分词语进行小写转换，如出现在句子开始处的词语和几乎全部都是大写字母的标题词语，显然，这些词语通常都应该是不大写的正常词语。句子中间的大写词语应该保持原有的模样。更为强大的功能可以使用机器学习算法来推测大小写的情况。但是，正如前面所述一样，用户可能会随意的将所有词语全部写为小写，如果是这样的话，将所有字母全部转换为小写其实非常可行和实用。
3）其他情况。在英语中还有如省略符、日期格式等特殊问题。除英语以外，还有其他语言所面对的特殊问题。虽然英语网页在www上能够达到60％，但是还有40％的网页并非英语网页 。这部分网页的数量也在快速增加，因为毕竟说英语的互联网用户不到全部互联网用户的1/3，相关人口更不到全球人口的10％。有学者进一步指出，在某些新事物当中，情况发生了更为明显的变化，如只有1/3的博客信息是使用英语书写的 。
更为复杂的情况在于，有些网页可能混合了多种语言，这就需要使用语言识别工具对其正确识别后才进行进一步的索引处理。不过，这就需要将一个文档看成若干个不同语言组成的单位。相关索引也需要存储更多的词语信息，甚至需要添加字段以说明语种信息，不过对于有些只会出现在一种特定语言中的词语，完全可以忽略相关语种信息的说明。
在处理多种语言文字时，还会遇到外来词的处理问题，如很多外来词在一种语言中有多种写法。比较有效的处理方法可以采用基于读音序列的比较方法，比较著名的方法就是Soundex算法。

2．2．4 截词（Stemming）和词根提取（lemmatization）
在很多语言中，同一个词语可能具有多种表达形态。在检索时，对其中任何一个词语的检索都需要返回其他相关词语的命中结果。此项操作的主要目的消除这些不同形态，从而将词语转换为标准的形态。如：
the boy’s cars are different colors — the boy car be differ color
不过，截词和词根提取并非一回事。前者就是简单的将词语尾部的若干字符直接删除，而后者往往需要结合词表或者词语的语形学分析以得到词语的词条（lemma）。对这个问题的处理，可以使用很多第三方的商业或者开源产品。
借助一些算法也可以比较有效的处理截词问题，如Porter算法 。该方法比较复杂，大致的流程包含需要连续使用的5个词语约减过程，访问站点为：
http://www.tartarus.org/?martin/PorterStemmer/
除此以外，还有较为古老的、一遍处理式的Lovins词语截取算法 和新出现的Paice/Husk词语截取算法 等。相关参考链接为：
http://www.cs.waikato.ac.nz/?eibe/stemmers/
http://www.comp.lancs.ac.uk/computing/research/stemm
词语截取算法与特定语言密切相关，总体上所需的知识量要少于词根提取算法。对于一些特殊情况，需要使用特殊的截取算法。不过有一点需要明确，那就是最终得到的截取形式是什么并不重要，关键的内容在于它是否把应该属于一类的词语归入了一类。
最后说明一点，这些截词方法和词根提取方法并不能有效的提升信息检索的整体性能，虽然可以有助于部分查询效果的改进，但是却对大多数的查询产生了不利的影响，提高了召回度却降低了检索精度，因为很多词语就是利用这些不同的词语形式变化来表达不同的含义。

2．3 利用跳跃指针（skip pointers）实现标记列表的快速并操作
在进行布尔查询时，就需要利用词语所对应的标记列表计算并操作结果。在操纵两个词语的情况下，就需要同时对两个标记列表进行遍历访问，整体处理时间和所有标记列表的所有元素个数总和成线形正比关系。
如果索引不经常改变，完全可以采用更好的操作策略，如在构建索引时使用跳跃指针构建跳跃列表（skip list）来加快并操作。所谓跳跃指针，其实是指一种可以避免处理与检索结果无关内容的快捷方式，主要的两个问题在于在哪儿放置跳跃指针和如何有效的使用跳跃指针。

此主题相关图片如下：

考虑上述两个标记列表的并操作。假设已经得到8这个结果，接下来需要继续判断。可以同时移动两个列表的指针，分别得到上面列表中的16和下面列表中的41，显然较小的值为16，此时可以直接利用上面列表16元素的跳跃指针来判断，它为28，仍然小于41，所以可以直接将上面列表的当前元素定位到值为28的元素后，即值为43的元素。这样做就避免了对上面列表中的19和23元素的比较处理。

注意两个问题：一是只有原先的标记列表才有跳跃指针，在处理复杂查询期间生成的中间标记列表，hasSkip函数总是返回为false；二是跳跃指针只能有助于AND运算的改进，对OR操作没有效果。
在哪儿放置跳跃指针是个需要折中的问题。越多的跳跃指针意味着跳跃距离越短，跳跃的次数越多，运算中和跳跃指针的比较次数也越多，所要存储的跳跃指针越多。越少的跳跃指针意味着越少的比较次数，但是越长的步进距离也意味着使用跳跃指针的机会越少。实践证明，对于具有长度为P的标记列表，跳跃指针的数量可以设置为P的方根。当然，这种方法完全没有考虑查询词语的分布情况，还有改进的空间。
对于相对静态的索引而言，构建跳跃指针是比较有效的。但是如果索引可能需要经常更新，那么跳跃指针的使用就没有优势了，恶意的删除行为会导致跳跃列表失效。
选择合适的索引优化方式需要紧密联系计算机系统的情况，如如果CPU较慢，高压缩技术就不可行，现在的CPU都比较快，而外存相对较慢，所以减少外存上标记列表的大小是非常必要的。但是，如果运行一种全部系统位于内存的搜索引擎的话，上述优化方式的选择又会不同。

2．4 词组检索（phrase retrieval）
更加复杂的概念、组织和产品名称通常含有多个词语。一般的搜索引擎使用双引号来表达词组检索，这是一种非常易于理解和有效的方法。大概有10％的Web查询都是词组检索，除此以外还有一些隐式的词组检索，它们没有使用双引号但实际上反映的意思是词组检索。为了支持词组检索，仅仅包含所在文档信息的标记列表显然远远不够。所以，不仅要设计更为合理有效的数据结构，而且还要具有较高的效率。

2．4．1 双词索引（Biword indexes）
这个方法将任何两个连续的词语都看成是一个词组，可以将其称为双词（biword），它可以作为索引的基本词项。在检索时，如果检索词语多于2个，则可以将其分割为若干个双词。如：
stanford university palo alto
可以分割为
“stanford university” AND “university palo” AND “palo alto”
这种方法的实际效果不错，但是有时也会产生问题。如果不和文档进行比对，就无法发现所命中的文档是否真正包含原有的词组。
在各种可能的查询中，描述用户查询需求的词语往往具有很多不同的位置状态，有时并不一定是正好连续的，所以很多相关的名词往往被一些功能性词语所分割，如“renegotiation of the constitution”。在构建双词索引时，可以考虑这种特殊的因素。首先，对词语进行分词并进行词语标注（part-of-speech-tagging），词语标注可以将词语归入很多不同的类型，如名词或者动词等，甚至粒度可以更低，如复数专有名词等。现在已经有了一些精确度较高的词语标注工具，部分标记的精确度可达96％，这些工具通常利用机器学习方法从人工标记文本中获取标记模型 。通常对包含专有名词在内的名词标记为N，一些包含冠词和介词在内的功能性词语标记为X。所以，基于上述词语类别，可以对双词模式进行重新定义，如NX*N，满足这个模式的就构成一个双词，如下面的四个词语就构成了一个双词：
renegotiation  of  the  constitution
N    X  X  N
为了处理使用扩展双词索引的查询，有时还有必要将其转换为N’s和X’s。
当然，这种方式在处理较长查询时也会出现问题，如：
cost overruns on a power plant
可以转换为：
“cost overruns” AND “overruns power” AND “power plant”
显然，这里三个双词中的第二个双词显然是多余的。
双词的概念可以进一步扩展到更多的词语组合上，此时被索引的词项可以由多于2个的词语组成，此时的双词索引不妨称之为词组索引。虽然词组索引具有误报 的可能性，但是对3个及3个以上词组进行检索时，误报的可能性非常低。不过，存储较长的词组信息会增加索引文件的大小。所以，这需要做出权衡。在很多情况下，可以采用部分词组索引（partial phrase index）的模式来取得折中效果。
另外，在对单个词语进行检索的时候，双词索引就显得不合适了，因为此时需要搜索所有含有这个词语的双词。因此，单一词语的索引仍然必不可少。

2．4．2 位置索引
位置索引较前者是一种更为常见的方法。对于词表中的每个词语，都不仅要存储相关文档号，而且还要存储词语所在的位置，如：

此主题相关图片如下：

在处理查询时，要对查询中的每个词语都进行索引检索，为了优化，可以先从文档频率最低的词语开始。在并运算的操作期间，还可以采用以前的方法，不过不是仅仅检测相关的文档号，还要检测词语出现的位置以判断是否构成所需的词组，这显然需要词语的偏移地址信息。如上图所示的to和be的位置索引，假设查询“to be or not to be”，需要处理的相关词语有to、be、or、not。首先可以先考虑to和be的情况，此时需要找到同时含有这两个词语的文档，而且还要判断be的出现位置是否正好比to的出现问题多1位偏移，最后还要搜索另一对出现在同一文档中的to和be，判断它们的偏移地址是否正好比第一对to和be的偏移地址多4位偏移。

这样的位置索引还能实现相隔词语数量为k的复杂位置检索（within k word proximity searches），如Westlaw系统中的复杂位置检索：
employment /3 place
这里的/k表示相隔词语数量不超过k。显然，对于这种问题，双词索引显然无法胜任。

存储位置信息的位置索引也会增加索引的大小，而且对检索计算复杂度也产生重大的影响，因为要检查的项不仅包含文档号，而且还要包含文档中出现的位置偏移地址。不过，既便如此，很多信息检索系统仍然需要采用这样的功能来满足用户的要求。
可以大致估算一下位置索引的大小。由于位置索引需要统计每个词语所在文档的位置信息，所以整个索引的大小依赖于文档的平均长度。Web网页的平均长度小于1000的词语，但是对于那些股票交易信息、书籍信息和一些史诗等文档很容易达到10万以上的词语数量。假设每个词语的出现频率为1/1000，相关计算结果为：
Document size  Expected postings  Expected entries in positional posting
1000    1     1
100,000    1     100
准确的索引大小依赖于文档类型和所使用的语言，通过粗略的估计，位置索引大小可以达到一般索引的2到4倍，即便是压缩后的位置索引也可以达到原始文档大小的1/3或者1/2，

2．4． 混合方式
双词索引和位置索引可以组合使用，如果用户只是键入两个词语，这时使用位置索引其实没有双词索引高效。混合方式就是可以按照不同的查询灵活的决定采用何种索引方式。对于词组索引的索引项，一般可以根据最近的用户查询来得到应该索引的词组，但是这也不是绝对的，最有效率的查询词组往往都表现为单个词语较为普通但整体词语较为罕见。如Britney Spears这个索引词项中的两个词语共现度较高，因此有了单一词语的索引就已经能够从一个词语检索到另外一个词语的相关命中信息。而对于The Who之类的罕见词组就比较有效率了，可以极大了提升索引查询效率。所以，即使后一种词组较为罕见，但却是值得索引。
有学者提出更为复杂的混合方式，它不仅充分结合了两种方式，而且还添加了在两种索引中间添加了一种连续词索引（next word index）。这种方式的运行时间只是单纯使用位置索引方式的1/4，不过却多占了26％的额外空间 。