【大数据管理】数据组织与存储（四）_大数据的数据组织与处理方法

    (1) 收集待建索引的文档；

    (2) 对这些文档中的文本进行词条化；

    (3) 对第2 步产生的词条进行语言学预处理，得到词项；

    (4) 根据词项对所有文档建立索引

 •本章首先定义文档的基本组成单位并介绍在文档中确定这些单位所含字符序列的方法.

•将详细讨论在词条化和语言学预处理过程中所涉及到的主要的语言学相关问题，通过词条化和语言学预处理可以确定系统所用的词项词典。

•考察了一个扩展的带跳表的倒排记录表数据结构，该结构能够支持查询的快速处理。

•主要介绍适合于处理处理短语查询和邻近查询的索引结构，这些查询在支持扩展布尔操作的检索系统和Web 搜索系统中的使用十分普遍。

 

转换字符序列的生成

•作为索引构建过程的输入，数字文档一般由文件中或者Web服务器上的一系列字节组成。

•因此，文档处理的第一步往往是将这些字节序列转换成线性的字符序列。

•对于ASCII编码的纯英文文本来说，处理起来似乎并非难事。

•然而，实际中往往会遇到非常复杂的情况。比如字符序列可能采用各种单字节或者多字节编码方式（比如 Unicode中的UTF-8 编码），也可能采用不同国家、不同厂家的特定编码方式。

•因此，为了实现从字节序列到字符序列的转换，首先要正确地判断出文档的编码方式.

•实际中往往通过启发式方法来实现，也可以利用文档的元信息或者直接由用户手工选择来确定.

•确定编码方式后，我们就可以将字节序列转换成字符序列，在此过程中还应该保存编码信息，因为该信息有时能帮助确定文档的语言种类。

•有时，必须从一些二进制文档（如Microsoft 的.doc 文档或.zip 之类的压缩文档等等）中得到字符序列。这时，我们也必须先确定文档的格式，然后才能采用合适的编码转换方式还原出字符序列。

•即便是对纯文本文档，有时也需要进行额外的转换过程。比如，对于XML 文档, ），一些转义字符串就需要就转换成它原本代表的字符，如“ &” 就要转换成“ &”.

•最后，如果文档中同时存在文本和非文本部分，当不需要对非文本部分进行处理时，就需要将文本部分单独抽取出来进行处理.比如，在处理XML 文档时，可以不考虑其中的标签.

 

文档单位的选择

•下一步需要确定索引的文档单位（document unit）。至今为止，都假设在建立索引时每篇文档就是固定的索引单位。比如，将某个目录下的每个文件都看成一个文档。

•但是，很多情况下并非如此。传统的Unix （mbox 格式）邮件系统将某个邮件目录下的一系列邮件都存放到单个文件中，但是希望将每封邮件都看成一个独立的文档.

•很多邮件还有附件，还希望将每封邮件和它的每个附件都分开看成不同的文档。

•如果邮件的附件是一个zip 文件，想将附件解压缩并将其中的每个文件都看成一个文档.

•与此不同的是，网络上的各种软件（如latex2html）有时把认为的单一文档（如一个PowerPoint 文件或Latex 文档）以幻灯片或者小节为单位切分成多个HTML 页面，并将每个页面保存到独立的文件中。这种情况下，反而希望将多个文件合并成一个文档来构建索引。

•对于长文档而言，一个更一般的说法是说此时存在一个“ 索引粒度” （indexing granularity）的问题。

•对于一个书库来说，将整本书作为索引单位通常是个糟糕的做法。这种情况下，如果搜索“ Chinese toys” ，那么很有可能返回这样一本书.

•可取的做法是将每章或每段看成一个微型文档（mini-document）来建立索引.

•此时，匹配的结果可能与查询更相关，而由于匹配单位的粒度更小，用户也更容易在文档中找到相关的段落。

•但是谈到这里，另一个问题出现了，为什么不进一步采用更小粒度的单位呢？比如，可以将每个句子作为索引单位.

•很显然，这里存在着一个正确率和召回率之间的权衡问题：如果索引粒度太小，那么由于词项散布在多个细粒度文档中，就很可能错过那些重要的段落，也就是说此时正确率高而召回率低.

•反之，如果索引粒度太大，就很可能找到很多不相关的匹配结果，即正确率低而召回率高。

 

词项集合的确定

词条化

•定义好文档单位之后，词条化是将给定的字符序列拆分成一系列子序列的过程，其中每个子序列称为一个词条（token）。当然，在这个过程中，可能会同时去掉一些特殊字符，如标点符号等。下面给出了一个词条化的例子：

•在非严格的情况下，词条往往和词项或词通用。然而，有时需要对词条和词条类进行严格的区分.

•一个词条指的是在文档中出现的字符序列的一个实例, 而一个词条类（type）指的是相同词条构成的集合.

•一个词项指的是在信息检索系统词典中所包含的某个可能经过归一化处理的词条类.

•词项集合和词条集合可以完全不同，比如可以采用某一个分类体系中的类别标签作为词项。

•当然，在实际的信息检索系统中，词项往往和词条密切相关。但是，词项未必就是原始的词条，实际上它往往要通过对原始词条进行归一化来得到.

•举例来说，如果要对“ to sleep perchance to dream” 进行索引，那么会得到5 个词条，但是此时只有4个词条类（出现的两个 to 的实例归成一类）。然而，如果索引时将to看成停用词去掉的话，那么最后就只有3 个词项：sleep、perchance和dream。

 

 

 去除停用词

•某些情况下，一些常见词在文档和用户需求进行匹配时价值并不大，需要彻底从词汇表中去除。这些词称为停用词（stop word）。

•一个常用的生成停用词表的方法就是将词项按照文档集频率（collection frequency，每个词项在文档集中出现的频率）从高到低排列，然后手工选择那些语义内容与文档主题关系不大的高频词作为停用词。

•停用词表中的每个词将在索引过程中被忽略。

•图2-5 给出了一个停用词表的片段。使用停用词表可以大大减小系统所需要存储的倒排记录表的数目。

•在信息检索系统不断发展的历程中，有从大停用词表（200～300 个词）到小停用词表（7～12个词）最后到不用停用词的趋势。

•Web 搜索引擎通常都不用停用词表。

•一些现代IR 系统更关注如何利用语言的统计特性来更好地处理常见词问题。

•对于现代IR 系统来说，不论是对于索引大小还是查询处理的时间而言，不去除停用词所增加的开销并没有那么大。

 

 

词项归一化

 •将文档和查询转换成一个个的词条之后，最简单的情况就是查询中的词条正好和文档中的词条相一致

•然而在很多情况下，即使词条之间并不完全一致，但实际上人们希望它们之间能够进行匹配。比如查询USA 时我们希望能够返回包含U.S.A.的文档。

•词条归一化（token normalization）就是将看起来不完全一致的多个词条归纳成一个等价类，以便在它们之间进行匹配的过程.

•最常规的做法是隐式地建立等价类，每类可以用其中的某个元素来命名。比如，在文档和查询中，都把词条anti-discriminatory 和 antidiscriminatory映射成词项antidiscriminatory, 这样对两个词中的任一个进行搜索，都会返回包含其中任一词的文档。

•这种处理方法的优点在于：等价类的建立过程是隐式的，不需要事先计算出等价类的全部元素，在映射规则下输出相同结果的词项一起构成等价类集合.

•另一种建立等价类的方法是维护多个非归一化词条之间的关联关系。

•该方法可以进一步扩展成同义词词表的手工构建，比如将car 和 automobile归成同义词。

•这些词项之间的关系可以通过两种方式来实现：   

1.常用的方式是采用非归一化的词条进行索引，并为某个查询词项维护一张由多个词组成的查询扩展词表。当输入一个查询词项时，则根据扩展词表进行扩展并将扩展后得到的多个词所对应的倒排记录表合在一块。

2.在索引构建时就对词进行扩展。比如，对于包含automobile的文档，我们同时也用car来索引（同样，包含car的文档也用automobile来索引）；

•上述两种方式相对于隐式建立等价类的方法来说效率较低，这是因为它们需要存储和合并更多的倒排记录。

•第一种方式增加了一部查询扩展词典，因此在查询处理时需要更多的时间

•第二种方式需要更多的存储空间来存储倒排记录。

•另一方面，由于两个关联词的扩展词表之间可以存在交集但不必完全相同，所以上述两种方式相对于隐式建立等价类的方法来说更具灵活性。

•这也意味着从不同关联词出发可以进行不对称的扩展。

•图2-6 给出了一个例子。该例子中，如果用户输入windows，希望返回包含Windows 操作系统的文档。但是如果用户输入 window，虽然此时可以和小写的windows相匹配，但是不太可能会和Windows 操作系统中的Windows 相匹配。

•接下来给出一些在实际当中会遇到的词条归一化问题及其对策。

•重音及变音符号问题。英语中变音符号的使用越来越少见，尽管如此，人们很可能希望cliche 和cliché 或者naive 和naïve 能匹配。这可以通过在词条归一化时去掉变音符号来实现。

•大小写转换问题。大小写转换（case-folding）问题的一个一般处理策略是将所有的字母都转换成小写。

•但是，这种全部进行小写的处理方法可能会将那些应该区分的词语等同化。很多专有名词由普通名词构成，因此，大小写不同则意义也不同，而且这种意义上的不同只能通过大小写来区分。这种专有名词包括公司名称（如 General Motors，The Associated Press）、政府组织（the Fed 和fed）和人名（Bush、Black）等等。

 •对英语来说，大小写处理的另一种做法是只将部分词条转换成小写形式。

•最简单的启发式处理方法是，将句首词转换成小写形式，并将标题中大写或首字母大写的全部单词都转换成小写形式。这些首字母大写的单词通常都是普通词。

•当处理外来词或者复合词，特别是外来的名称时，拼写可能不明确或者在不同的音译标准下会产生不同的拼写结果（如Chebyshev 和Tchebycheff、Beijing 和 Peking 等）。

•处理此类情况的一种做法是，采用启发式方法来建立等价类，或者根据发音相同来进行词项扩展。后者最出名的算法是将介绍的Soundex 算法。

 

 

词干还原和词形归并

 •出于语法上的要求，文档中常常会使用词的不同形态，比如organize、organizes 和organizing。

•另外，语言中也存在大量意义相近的同源词，比如democracy、democratic 和democratization。

•在很多情况下，如果输入其中一个词能返回包含其同源词的文档，那么这样的搜索似乎非常有用。

•词干还原和词形归并的目的都是为了减少屈折变化的形式，并且有时会将派生词转化为基本形式。比如：am, are, is ⇒ be         

 car, cars, car’s, cars’ ⇒ car

•利用上述方式对文本进行映射处理，可以得到类似如下的结果：

The boy’s cars are different colors ⇒

the boy car be differ color

•然而，词干还原（stemming）和词形归并（lemmatization）这两个术语所代表的意义是不同的。

•前者通常指的是一个很粗略的去除单词两端词缀的启发式过程，并且希望大部分时间它都能达到这个正确目的，这个过程也常常包括去除派生词缀.

•而词形归并通常指利用词汇表和词形分析来去除屈折词缀，从而返回词的原形或词典中的词的过程，返回的结果称为词元（lemma）

•假如给定词条saw，词干还原过程可能仅返回s。

•而词形归并过程将返回see 或者saw。当然具体返回哪个词取决于在当前上下文中saw 到底是动词还是名词。

•英文处理中最常用的词干还原算法是Porter 算法（Porter 1980），它的高效性已反复被实践所证明。

•整个算法很长也很复杂，下面只给出算法的核心思想。Porter算法包括5 个顺序执行的词约简步骤。在每个步骤中，都有选择规则的一些不同约定，比如从规则组中选择作用时词缀最长的那条规则。比如在第一步，规则选择方法如下：

 •后续步骤的很多规则中都使用了词的测度（measure）的概念，即通过粗略检查音节的个数来判断词是否足够长，在足够长的情况下才将规则的匹配部分看成词缀而不是词干的一部分来进行处理。这是一种合理的做法。例如：有一条规则为：（m > 1） EMENT →

•在这条规则下，可以把repalcement转换成replac，但是此时不能将cement转换成c

•可以选择词形归并工具（lemmatizer）而不是词干还原工具来处理相关问题。

•词形归并工具是一种自然语言处理工具，它能够通过进行详尽的词形分析来精确地得到每个词的词元。

•进行详尽的词形分析只能为检索带来极其有限的帮助，不会太多，因为总体而言，上面两种归一化方法往往并不能显著改善英文检索的性能。

•尽管进行归一化对于部分查询来说有帮助，但是同时也会降低其他很多查询的效果。

 

 

基于跳表的倒排记录表快速合并算法

•讨论倒排记录表数据结构的其他扩展形式，以及如何提高倒排记录表的使用效率。

•回想一下在1.3 节所讨论的倒排记录表的基本合并算法：同时在两个表中遍历，并且最后算法的时间复杂度为记录表大小的线性函数。

•假定两个表的大小分别是m 和n，那么合并过程有O（m + n）次操作。很自然的一个问题就是能否做得更好？

•下面将看到，如果索引变化不太频繁的话那么答案是肯定的。

•一种实现的方法是采用跳表（skip list），在构建索引的同时在倒排记录表上建立跳表（如图2-9 所示）。跳表指针能够提供捷径来跳过那些不可能出现在检索结果中的记录项。

•跳表指针能够提供捷径来跳过那些不可能出现在检索结果中的记录项

•构建跳表的两个主要问题是：在什么位置设置跳表指针？如何利用跳表指针进行倒排记录表的快速合并？

•以下图为例来先考虑快速合并的问题。假定在两个表中遍历一直到发现共同的记录 8 为止，将 8 放入结果表中之后继续移动两个表的指针.

•假定第一个表的指针移到 16处，而第二个表的指针移到 41 处，两者中较小项为 16 。

•这时候并不继续移动上面的表指针，而是检查跳表指针的目标项，此时为 28 ，仍然比 41 要小，因此此时可以直接把上表的表指针移到 28 处，这样就跳过了 19 和 23 两项。

•基于跳表的倒排记录表合并算法有很多变形，它们的主要不同可能在于跳表检查的时机不一样.图2-10 给出了一种合并算法的例子。

•最后，需要注意的是，跳表指针只对AND 类型的查询有用，而对OR 类型的查询不起作用。

•再考察另一个问题，即在什么位置上放置跳表指针？

•这里存在一个指针个数和比较次数之间的折中问题。

•跳表指针越多意味着跳跃的步长越短，那么在合并过程中跳跃的可能性也更大，但同时这也意味着需要更多的指针比较次数和更多的存储空间。

•放置跳表指针位置的一个简单的启发式策略是，在每个    处均匀放置跳表指针，其中P 是倒排记录表的长度。

•这个策略在实际中效果不错，但是仍然有提高的余地，因为它并没有考虑查询词项的任何分布细节。

•如果索引相对固定的话，建立有效的跳表指针则比较容易。但是如果倒排记录表由于经常更新而发生变化，那么跳表指针的建立就比较困难。恶意的删除策略可能会使跳表完全失效。