Clone wiki

InvertedIndex / Home

介绍

海量数据分析(Massive Data Processing)课程实验。主要是在MapReduce中将一系列输入文档中的词(Term)进行反向倒排索引。

目标

现在假设有两个文档Doc1和Doc2,它们的内容分别如下:

Doc1:

Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo. 

Doc2:

Buffalo are mammals.

我们的目标是将文档中的内容切成一个个词,并标记每个词出现的文档。如下:

Buffalo -> Doc1, Doc2
buffalo -> Doc1 
buffalo. -> Doc1 
are -> Doc2 
mammals. -> Doc2

分词的实现

目前的切分支持英文、数字和中文这几种方式。我们的实现中对标点符号是不敏感的(即不索引标点)。中文的切分实现了两种简单的分词方法(前向最大匹配和后向最大匹配)。

com.chine.invertedindex.analysis模块实现了对句子的切分。其中segment.ChineseSegment中实现了分词算法。使用的词库是IBM的ICU库,也是Chrome浏览器中所使用的中文词库,地址见这里

分词实现包括两步,第一步是Tokenizer的过程,即把句子拆分成一些列的词,也叫token;第二步是Filter的过程,这其中包括一系列的filter,比如LowercaseFilter:将一个个的token变成小写。为了方便,Analyzer的作用主要是对以上过程进行了包装,即不需要手动处理Tokenizer=>Filter1=>Filter2=>...=>FilterN的过程。

实现的Tokenizer主要包括:

  • Tokenizer:基类,主要处理英文和数字(按空格切分)。
  • ChineseTokenizer:在Tokenizer基础上的包装,支持中文分词为基础的切分。
  • HTMLChineseTokenizer:对ChineseTokenizer的包装,支持HTML标签的去除。

实现的Filter包括:

  • LowercaseFilter:将英文单词变为小写。
  • StopFilter:去除英文中的停词。如this等等。
  • StemFilter:基于Porter Stemmer的过滤器。主要将一个单词剥离后缀,如把flowers变为flower。

实现的Analyzer包括:

  • Analyzer:基类,可以用一个Tokenizer来初始化,并提供添加一系列的过滤器的方法。
  • ChineseAnalyzer:继承自Analyzer,用HTMLChineseTokenizer初始化,默认添加了LowercaseFilter和StopFilter。(考虑到Porter Stemmer的bug,默认没有添加)

MapReduce

  • Downloads中的InvertedIndex.jar是不索引词出现位置的MapReduce操作。
  • InvertedIndex2.jar索引文件位置。
  • Search.jar可以对索引进行搜索。
  • hlSearch.jar可以使搜索结果高亮

运行

使用如下命令来进行搜索。

hadoop jar Search.jar -D search.text="whom scene"

这个即搜索“whom scene”关键字。当文件没有索引时,会先进行索引。“-D”用来进行选项设置。支持的选项:

  • index.input:输入的文件路径。默认为:/invertedindex/in
  • index.output:索引的文件路径。默认为:/invertedindex/index/out
  • search.output:搜索的输出路径。默认为:/invertedindex/search
  • forceindex:设置为true时,强制重新索引文件。(当索引文件存在时,默认不进行索引)
  • onlyindex:设置为true时,只索引文件,而不进行搜索。

搜索时,是使用ChineseAnalyzer对搜索内容进行tokenize的。

搜索结果高亮

搜索结果高亮,即显示搜索结果关于关键子的“片段”。类似于搜索,使用如下命令来使搜索结果高亮。

hadoop jar hlSearch.jar -D search.text="whom scene"

除了以上支持的选项,新的支持选项有:

  • search.highlight.output:搜索结果输出路径。默认为:/invertedindex/highlight
  • search.highlight.on:此时已默认不开启普通搜索。
  • search.snippet:搜索结果高亮显示的字数。默认为50。
  • highlight.left:包裹关键字的左字符。默认为“[”。
  • highlight.right:包裹关键字的右字符。默认为“]”。

考虑添加的功能或进行的改进

优先考虑的功能:

  1. 支持对搜索内容的语法解析。

其他功能:

  1. 支持中文停词的去除。
  2. 现有的中文分词算法性能的改进,使用Trie树加载字典。
  3. 使用更好的中文分词算法。
  4. 改进剥离后缀算法。(Porter Stemmer)
  5. 添加Lemmatization的支持。

Updated