hadoop--之搜索引擎，倒排索引，hadoop--索引
倒排索引的用处
搜索引擎的关键步骤就是建立倒排索引，所谓倒排索引一般表示为一个关键词，然后是它的频度（出现的次数），位置（出现在哪一篇文章或网页中，及有关的日期，作者等信息），它相当于为互联网上几千亿页网页做了一个索引，好比一本书的目录、标签一般。读者想看哪一个主题相关的章节，直接根据目录即可找到相关的页面。不必再从书的第一页到最后一页，一页一页的查找。倒排索引是搜索引擎之基石。建成了倒排索引后，用户要查找某个query，如在搜索框输入某个关键词：“倒排索引”后，搜索引擎不会再次使用爬虫又一个一个去抓取每一个网页，从上到下扫描网页，看这个网页有没有出现这个关键词，而是会在它预先生成的倒排索引文件中查找和匹配包含这个关键词“结构之法”的所有网页。找到了之后，再按相关性度排序，最终把排序后的结果显示给用户
倒排索引的概念
倒排表以字或词为关键字进行索引，表中关键字所对应的记录表项记录了出现这个字或词的所有文档，一个表项就是一个字表段，它记录该文档的ID和字符在该文档中出现的位置情况。由于每个字或词对应的文档数量在动态变化，所以倒排表的建立和维护都较为复杂，但是在查询的时候由于可以一次得到查询关键字所对应的所有文档，所以效率高于正排表。在全文检索中，检索的快速响应是一个最为关键的性能，而索引建立由于在后台进行，尽管效率相对低一些，但不会影响整个搜索引擎的效率。
倒排索引的组成成分
文档(Document)：一般搜索引擎的处理对象是互联网网页，而文档这个概念要更宽泛些，代表以文本形式存在的存储对象，相比网页来说，涵盖更多种形式，比如Word，PDF，html，XML等不同格式的文件都可以称之为文档。再比如一封邮件，一条短信，一条微博也可以称之为文档。在本书后续内容，很多情况下会使用文档来表征文本信息。
文档集合(Document Collection)：由若干文档构成的集合称之为文档集合。比如海量的互联网网页或者说大量的电子邮件都是文档集合的具体例子。
文档编号(Document ID)：在搜索引擎内部，会将文档集合内每个文档赋予一个唯一的内部编号，以此编号来作为这个文档的唯一标识，这样方便内部处理，每个文档的内部编号即称之为“文档编号”，后文有时会用DocID来便捷地代表文档编号。
单词编号(Word ID)：与文档编号类似，搜索引擎内部以唯一的编号来表征某个单词，单词编号可以作为某个单词的唯一表征。
倒排索引(Inverted Index)：倒排索引是实现“单词-文档矩阵”的一种具体存储形式，通过倒排索引，可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成：“单词词典”和“倒排文件”。
单词词典(Lexicon)：搜索引擎的通常索引单位是单词，单词词典是由文档集合中出现过的所有单词构成的字符串集合，单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。
倒排列表(PostingList)：倒排列表记载了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息，每条记录称为一个倒排项(Posting)。根据倒排列表，即可获知哪些文档包含某个单词。
倒排文件(Inverted File)：所有单词的倒排列表往往顺序地存储在磁盘的某个文件里，这个文件即被称之为倒排文件，倒排文件是存储倒排索引的物理文件。
单词词典
单词词典是倒排索引中非常重要的组成部分，它用来维护文档集合中出现过的所有单词的相关信息，同时用来记载某个单词对应的倒排列表在倒排文件中的位置信息。在支持搜索时，根据用户的查询词，去单词词典里查询，就能够获得相应的倒排列表，并以此作为后续排序的基础。对于一个规模很大的文档集合来说，可能包含几十万甚至上百万的不同单词，能否快速定位某个单词，这直接影响搜索时的响应速度，所以需要高效的数据结构来对单词词典进行构建和查找，常用的数据结构包括哈希加链表结构和树形词典结构。
4.1 哈希加链表
图1-7是这种词典结构的示意图。这种词典结构主要由两个部分构成：
主体部分是哈希表，每个哈希表项保存一个指针，指针指向冲突链表，在冲突链表里，相同哈希值的单词形成链表结构。之所以会有冲突链表，是因为两个不同单词获得相同的哈希值，如果是这样，在哈希方法里被称做是一次冲突，可以将相同哈希值的单词存储在链表里，以供后续查找。
图1-7 哈希加链表词典结构
在建立索引的过程中，词典结构也会相应地被构建出来。比如在解析一个新文档的时候，对于某个在文档中出现的单词T，首先利用哈希函数获得其哈希值，之后根据哈希值对应的哈希表项读取其中保存的指针，就找到了对应的冲突链表。如果冲突链表里已经存在这个单词，说明单词在之前解析的文档里已经出现过。如果在冲突链表里没有发现这个单词，说明该单词是首次碰到，则将其加入冲突链表里。通过这种方式，当文档集合内所有文档解析完毕时，相应的词典结构也就建立起来了。
在响应用户查询请求时，其过程与建立词典类似，不同点在于即使词典里没出现过某个单词，也不会添加到词典内。以图1-7为例，假设用户输入的查询请求为单词3，对这个单词进行哈希，定位到哈希表内的2号槽，从其保留的指针可以获得冲突链表，依次将单词3和冲突链表内的单词比较，发现单词3在冲突链表内，于是找到这个单词，之后可以读出这个单词对应的倒排列表来进行后续的工作，如果没有找到这个单词，说明文档集合内没有任何文档包含单词，则搜索结果为空。
4.2 树形结构
B树（或者B+树）是另外一种高效查找结构，图1-8是一个 B树结构示意图。B树与哈希方式查找不同，需要字典项能够按照大小排序（数字或者字符序），而哈希方式则无须数据满足此项要求。
B树形成了层级查找结构，中间节点用于指出一定顺序范围的词典项目存储在哪个子树中，起到根据词典项比较大小进行导航的作用，最底层的叶子节点存储单词的地址信息，根据这个地址就可以提取出单词字符串。
简单案例实现
原始数据为 三个文件 a.txt b.txt c.txt 在HDFS中创建新的文件夹 然后把这三个文件上传到文件夹中
然后经过第一次mapreduce
import org.apache.commons.lang.StringUtils;
import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.FileSystem;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.LongWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.Mapper;
import org.apache.hadoop.mapreduce.Reducer;
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
import org.apache.hadoop.mapreduce.lib.input.FileSplit;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
public class IndexOne {
public static class MapOne extends Mapper<LongWritable, Text,Text,LongWritable>
{
@Override
protected void map(LongWritable key, Text value,Context context)
throws IOException, InterruptedException {
// 需求： 将 hello world --》 hello--a.txt 1 world-->a.txt 1
//1.取出一行数据 转为字符串
String line = value.toString();
//2.将这一行数据按照指定的分割符进行第一次切分
String[] words = StringUtils.split(line," ");
//3.获取读取的文件所属的文件切片
Configuration conf = new Configuration();
FileSystem fs = FileSystem.get(conf);
//4.使用context参数来获取子对象
FileSplit inputSplit=(FileSplit)context.getInputSplit();
//5,使用切片对象来获取文件名称
String filename = inputSplit.getPath().getName();
//6.讲数据进行传递
for(String word:words)
{ //7，封装数据输出格式为 k: hello-->a.txt v:1
context.write(new Text(word+"-->"+filename),new LongWritable(1));
}
}
}
//======================reduce============================
public static class ReduceOne extends Reducer<Text, LongWritable,Text,LongWritable>
{
@Override
protected void reduce(Text key, Iterable<LongWritable> values,
Context context) throws IOException, InterruptedException {
//1.reduce 从map端接受来的数据格式为 hello-->a.txt 1,1,1
//2,定义for循环将values集合中的数据进行累加
long count = 0;
for(LongWritable value:values)
{
count += value.get();
}
context.write(key,new LongWritable(count));
}
}
//===================主方法提交job==========================
public static void main(String[] args) throws IOException, ClassNotFoundException, InterruptedException {
//1.获取job对象
Configuration conf = new Configuration();
Job job = Job.getInstance(conf);
//2.指定jar包的类
job.setJarByClass(IndexOne.class);
//3.指定map（）的类
job.setMapperClass(MapOne.class);
//4.指定reducer()的类
job.setReducerClass(ReduceOne.class);
//5,指定输出类型
job.setOutputKeyClass(Text.class);
job.setOutputValueClass(LongWritable.class);
//6,指定文件输入路径
FileInputFormat.setInputPaths(job,new Path(args[0]));
//7,进行健壮型判断如果存储文件已经存在则删除
Path output = new Path(args[1]);
FileSystem fs = FileSystem.get(conf);
if(fs.exists(output))
{
fs.delete(output,true);
}
//8，指定文件的输出路径
FileOutputFormat.setOutputPath(job,new Path(args[1]));
//9，提交任务
System.exit(job.waitForCompletion(true)?0:1);
}
}
第一次mapreduce运行之后的输出结果为
然后经过第二次mapreduce
import java.io.IOException;
import org.apache.commons.lang.StringUtils;
import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.FileSystem;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.LongWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.Mapper;
import org.apache.hadoop.mapreduce.Reducer;
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
public class IndexTwo {
// --------------------map()-------------------------------
// google-->c.txt1
// hadoop-->a.txt2
//以上形式为上一次mapreduce的输出形式 要作为这一次maprede的map的输入形式
// 经过map()操作后 输出形式为 google c.txt-->1
public static class MapTwo extends Mapper<LongWritable,Text,Text,Text>
{
@Override
protected void map(LongWritable key, Text value,Context context)
throws IOException, InterruptedException {
//1.将读到的每一行数据转换为String类型进行操作
String line = value.toString();
//2.以指定的格式进行切分
String[] filds = StringUtils.split(line,"\t");
//3，上面哪个第一次切分 后的结果为 google-->c.txt 1
// 下面第二次且分 后的结果为 google c.txt 1
String[] words = StringUtils.split(filds[0],"-->");
//4,获取字段的内容
String word = words[0];
String filename=words[1];
long count = Long.parseLong(filds[1]);
//5.将字段的内容重新组合进行输出 输出格式为 google a.txt-->2;
context.write(new Text(word), new Text(filename+"-->"+count));
}
}
public static class ReducerTwo extends Reducer<Text, Text,Text,Text>
{
@Override
protected void reduce(Text key, Iterable<Text> values,Context context)
throws IOException, InterruptedException {
//1,从map端接受数据 定义链接符
String link = "";
for(Text value:values)
{
//2将集合中的数据取出 进行链接
link+=value+" ";
}
//3输出数据 输出格式为 google a.txt-->2 b.txt-->1
context.write(key,new Text(link));
}
}
public static void main(String[] args) throws IOException, ClassNotFoundException, InterruptedException {
Configuration conf = new Configuration();
Job job = Job.getInstance(conf);
job.setJarByClass(IndexTwo.class);
job.setMapperClass(MapTwo.class);
job.setReducerClass(ReducerTwo.class);
job.setOutputKeyClass(Text.class);
job.setOutputValueClass(Text.class);
FileInputFormat.setInputPaths(job,new Path(args[0]));
Path output = new Path(args[1]);
FileSystem fs = FileSystem.get(conf);
if(fs.exists(output))
{
fs.delete(output,true);
}
//8，指定文件的输出路径
FileOutputFormat.setOutputPath(job,new Path(args[1]));
//9，提交任务
System.exit(job.waitForCompletion(true)?0:1);
}
}
第二次mapreduce运行之后的输出结果为