精华内容
下载资源
问答
  • 使用倒排索引实现的简单的搜索引擎demo 能对莎士比亚全集的文本进行搜索,并显示该词语所在的篇目和所在句子 源代码及说明也可在github获取 https://github.com/yunwei37/myClassNotes
  • 倒排索引实现原理

    2019-06-27 10:21:00
    Term Dictionary(索引表,可简称为Dictionary)Terms组成 Postings List(倒排表),由所有的Term对应的Postings组成 倒排索引实现原理

    Term Dictionary(索引表,可简称为Dictionary) Terms组成

    Postings List(倒排表),由所有的Term对应的Postings组成

     

     

     

    倒排索引实现原理

    展开全文
  • Lucene倒排索引实现原理探秘(1) 前言 在全文检索领域, Lucene可谓是独领风骚数十年。倒排索引构成全文检索的根基,只有深入理解了倒排索引的实现原理,才能算是入门了全文检索领域。本文将对Lucene的倒排索引的...

    Lucene倒排索引实现原理探秘(1)

    前言

    在全文检索领域, Lucene可谓是独领风骚数十年。倒排索引构成全文检索的根基,只有深入理解了倒排索引的实现原理,才能算是入门了全文检索领域。本文将对Lucene的倒排索引的实现原理和技术细节进行详细的剖析,这些内容适用于Lucene 5.x至7.x系列版本。文章整体内容组织如下:

    1. 倒排索引理论
    2. Lucene倒排索引实现
    3. Lucene索引文件构成
    4. 什么是Terms Index?
    5. 什么是Terms Dictionary?
    6. 结束语

    理论

    在学术上,倒排索引结构非常简明易懂,如下:

    也许你已接触过倒排索引,下面这张图你或许已经看过很多次了。本文将从你熟悉的部分开始,一步步深入去挖掘这张图的一个个细节。这里先介绍两个重要概念:

    1. 索引,索引词表。倒排索引并不需要扫描整个文档集,而是对文档进行预处理,识别出文档集中每个词。

    2. 倒排表,倒排表中的每一个条目也可以包含词在文档中的位置信息(如词位置、句子、段落),这样的结构有利于实现邻近搜索。词频和权重信息,用于文档的相关性计算。

    倒排索引由两部分组成,所有独立的词列表称为索引,词对应的一系列表统称为倒排表。 —— 来自《信息检索》

    如图,整个倒排索引分两部分,左边是Term Dictionary(索引表,可简称为Dictionary),是由一系列的Terms组成的;右边为Postings List(倒排表),由所有的Term对应的Postings组成。

    实际上Lucene所用的信息信息检索方面的术语基本跟Information Retrieval(《信息检索》原版)保持一致。比如Term、Dictionary、Postings等。

    首先,有必要解释一下,每个Segment中的每个字段(Field)都有这么一个独立的结构。其次,它是不可改写的,即不能添加或更改。至于为何选择不可改写的设计,简单说有两个方面:一是更新对磁盘来说不够友好;另一方面是写性能的影响,可能会引发各种并发问题。

    我们可以用一个HashMap来简单描述这个结构:Map<String, List<Integer>>,这个Map的Key的即是Term,那它的Value即是Postings。所以它的Key的集合即是Dictionary了,这与上图的描述太贴切了。由于HashMap的Key查找还是用了HashTable,所以它还解决Dictionary的快速查找的问题,一切显得太美好了。这可以说是一个hello world版的倒排索引实现了。

    Lucene的实现

    全文搜索引擎通常是需要存储大量的文本,Postings可能会占据大量的存储空间,同样Dictionary也可能是非常大的,因此上面说的基于HashMap的实现方式几乎是不可行的。在海量数据背景下,倒排索引的实现都极其复杂,因为它直接关系到存储成本以及搜索性能。为此,Lucene引入了多种巧妙的数据结构和算法。

    Lucene索引文件构成

    我们知道Lucene将索引文件拆分为了多个文件,这里我们仅讨论倒排索引部分。Lucene把用于存储Term的索引文件叫Terms Index,它的后缀是.tip;把Postings信息分别存储在.doc.pay.pox,分别记录Postings的DocId信息和Term的词频、Payload信息、pox是记录位置信息。Terms Dictionary的文件后缀称为.tim,它是Term与Postings的关系纽带,存储了Term和其对应的Postings文件指针。

    总体来说,通过Terms Index(.tip)能够快速地在Terms Dictionary(.tim)中找到你的想要的Term,以及它对应的Postings文件指针与Term在Segment作用域上的统计信息。

    postings: 实际上Postings包含的东西并不仅仅是DocIDs(我们通常把这一个有序文档编号系列叫DocIDs),它还包括文档编号、以及词频、Term在文档中的位置信息、还有Payload数据。

    所以关于倒排索引至少涉及5类文件,本文不会全面展开。

    什么是Terms Index

    下面引用了一张来自网络上的图,非常直观:

    Terms Index即为上图中.tip部分,它实际上是由一个或多个FST组成的,Segment上每个字段都有自己的一个FST(FSTIndex)记录在.tip上,所以图中FSTIndex的个数即是Segment拥有字段的个数。另外图中为了方便我们理解把FST画成Trie结构,然后其叶子节点又指向了tim的Block的,这实际上是用了一种叫Burst-Trie的数据结构。

    Burst-Trie

    .tip看起来是像一棵Trie,所以整张图表现出来就是论文上的Burst-Trie结构了。上面一棵Trie,Trie的叶子节点是Container(即是Lucene中的Block)。下图就是Paper上描述的Burst-Trie的结构:

    来自Burst-Trie论文上的一张图

    Burst-Trie,关于Burst-Trie,网上有很多专业资料,这里只做简单介绍。Burst-Trie可以认为是Trie的一种变种,它主要是将后缀进行了压缩,降低了Trie的高度,从而获取更好查询性能。

    Lucene工程上的实现方式

    Burst-Trie在Lucene是如何应用的?

    前面提到了Lucene是采用Burst-Trie的思想,但在实现上存在一定的出入,Lucene的Burst-Trie被拆成两部分。如果一定把它们对应起来的话,我认为Burst-Trie的AccessTree的实现是FST,存在.tip文件中;Container的实现是Block,存在.tim文件里。Burst-Trie的Container内部是开放性结构,可能是Binary-Tree,可以也List。Lucene的block是数组,准确的说,就是把一系列的Block系列化写到文件上,这里好像并没有做特殊的处理。

    FST

    在Lucene,Terms Dictionary被存储在.tim文件上。当一个Segment的文档数量越来越多的时候Dictionary的词汇也会越来越多,那查询效率必然也会逐渐变低。因此需要一个很好的数据结构为Dictionary建构一个索引,将Dictionary的索引进一步压缩,这就是后来的Terms Index(.tii)。这是在早期的版本中使用的,到Lucene 4.0之后做一次重构和升级,同时改名为.tip。

    FST:Finite-State-Transducer,结构上是。我们知道把一堆字符串放一堆,把它们的共同前缀进行压缩就会变成Burst-Trie。如果把后缀变成一个一个节点,那么它就是Trie结构了。如果将后缀也进行压缩的话,那你就能发现他更变成一张图结构了。 那么我们易知FST是压缩字典树后缀的图结构,她拥有Trie高效搜索能力,同时还非常小。这样的话我们的搜索时,能把整个FST加载到内存。

    实际上,FST的结构非常复杂,我们可以简单的将其理解为一个高效的K-V结构,而且空间占用率更高。这里想简单强调一下:Lucene到底在FST里存了什么数据? 如果你已经了解FST在Lucene中充当的角色和作用的话,我想你可能会误认为FST中存了Dictionary中所有的Terms数据,这样可以通过FST是找到具体的Term的位置,或者通过FST可以切实获知一个Term是否存在。

    然而,事实并非如此。 FST即不能知道某个Term在Dictionary(.tim)文件上具体的位置,也不能仅通过FST就能确切的知道Term是否真实存在。它只能告诉你,查询的Term可能在这些Blocks上,到底存不存在FST并不能给出确切的答案,因为FST是通过Dictionary的每个Block的前缀构成,所以通过FST只可以直接找到这个Block在.tim文件上具体的File Pointer,并无法直接找到Terms。关于FST的详细细节,后面将以一篇独立的文章来讲解,这里暂时不展开过多细节。

    下面会详细的介绍Dictionary的文件结构,这里先提一下。每个Block都有前缀的,Block的每个Term实际不记录共同前缀的。只有通过Block的共同的前缀,这是整个Block的每个Term共同的,所以每个Term仅需要记录后缀可以通过计算得到,这可以减少在Block内查找Term时的字符串比较的长度。

    简单理解的话,你可以把它当成一个高级的BloomFilter,我们BloomFilter是有一定的错误率的;同时BloomFilter是通过HashCode实现的,只能用它来测试是否存在,并无法快速定位。在FST中,并无错误率且能快速定位。但是BloomFilter有更高的性能。

    说了这么多,Terms Index到底带来哪些实质性的功能呢? Terms Index是Dictionary的索引,它采用 了FST结构。上面已经提及了,FST提供两个基本功能分别是:

    1. 快速试错,即是在FST上找不到可以直接跳出不需要遍历整个Dictionary。类似于BloomFilter的作用。

    2. 快速定位Block的位置,通过FST是可以直接计算出Block的在文件中位置(offset,FP)。

    上面已经介绍了FST的一种功能,此外,FST还有别的功能,因为FST也是一个Automation(自动状态机)。这是正则表达式的一种实现方式,所以FST能提供正则表达式的能力。通过FST能够极大的提高近似查询的性能,包括通配符查询、SpanQuery、PrefixQuery等,甚至包括近期社区正在做的基于正则表达式的查询。

    什么是Terms Dictionary?

    前面我们已经介绍了Terms Dictionary的索引,Terms Index。已经频频提到的Terms Dictionary到底是什么东东?Terms Dictionary是Segment的字典,索引表。它能够让你知道你的查询的这个Term的统计信息,如tf-idfdf(doc_freq)Total Term Frequence(Term在整个Segment出现频率);还能让你知道Postings的元数据,这里是指Term的docids、tf以及offset等信息在Postings各个文件的文件指针FP。

    Block并不记录这个Block的起始和结束的范围,所以当FST最终指向多个Block时,就会退化为线性搜索。那什么时候会出现FST最终指向多个Block呢?最简单的一种情况是,超过48个的Term,且出现首字母相同的term的个数不超过25个。这种情况下由于没有每个Block都没有共同前缀,所以构建出来的FST只有一个结束节点记录每个Block的文件寻址的偏移增量。

    Lucene规定,每个Block的大小在25-48范围内

    说这么多,还是觉得太抽象了,我们来看一下.tim文件结构示意图:

    主要是大两部分信息,1. Block信息,包含所有Term的详情;2. Field的自有属性和统计信息。接下来我们将展开来介绍这两部分内容。

    Block信息 — NodeBlock

    在整个.tim文件上,我觉得比较复杂且值得拎出来讲的只有NodeBlock。那么,Block又是什么东东?它是如何被构建的?这部分代码,还是比较晦涩难懂得,我每次读时也都会产生一些新的疑问。

    我们前面所有说的Block即是NodeBlock的一个Entry。 由上图可以知道,Block中有两种OuterNode和InnerNode。这里我想引用代码上两个类名来辅助我们接下来的剖析:PendingTerm/PendingBlock,我们暂且把它们叫作待写的Term子Block的指针吧。

    NodeBlock从构建逻辑上来讲是它是树型结构,所以它由叶子节点和非叶子节点两种节点组成。叶子节点就叫OutterNode,非叶子节点就叫InnerNode。一个Block可能含有一堆的Term(PendingTerm)和PendingBlock(当它是非叶子节点时),实际上PendingBlock也是不可能出现在叶子节点上的。如果是PendingBlock,那么这个Entry只记录两个信息:后缀(这个Block的共同后缀)以及子Block的文件指针,此时就不必再记上所说的统计信息和postings信息了。

    如图所示,一个Block记录的信息非常多,首先是Block的类型和Entry的条数等元数据信息,而后是该Block拥有的所有Entry。

    这里每个Entry含有后缀、统计信息(对应为前面据说的权重,它含有ttf和df)、Postings的位置信息(这就是反复提及postings相关的文件指针,postings是拆分多文件存储的)。 关于Postings更多细节,放到下个章节来讨论。

    Field信息 — FieldMetadata

    相对来说FieldMetadata组织结构就简单多了,纯粹的线性写入即可。但Field信息记录的内容还是挺多的,包括字段本身的属性,如字段编号、Terms的个数、最大和最小的Terms;此外还记录了Segment级别的一些统计信息,包括tdf、拥有该字段的文档总数(如果文档没有该字段,或者该字段为空就不计了)。

    1. RootCode实际上指向该字段第一个Block的文件指针。

    2. LongsSize这个名字有点隐晦,它是说该字段的字段存储哪些Postings信息。因为我们是可以指定Postings存储或者不存储诸如位置信息和Payload信息的,存与不存将被表现在这里了。

    从搜索流程来看,Lucene先读到FieldMetadata的信息,然后判断Query上Terms是否落在这里字段的MinTerm和MaxTerm之间。如果不在的话,完全不需要去读NodeBlock的。MinTerm和MaxTerm可以有效的避免读取不必要的.tip文件。

    结束语

    到这里,关于倒排索引结构中第一部分内容已经介绍完了,限于篇幅的原因,还有更多有趣的小细节没有呈现出来。简单总结一下:我们先从Information Retrieve开始了解学术上倒排索引结构,接着我们又对Luecne的实现做了深入剖析。Lucene对索引词表也做了索引(叫Terms Index,文件后缀是.tip),索引词表的索引采用Finite-State Transducer这种数据结构。由于这种结构占用空间极小,所以它完成可以被加载到内存加速Terms Dictionary的查找过程。而后又介绍了Terms Dictionary,Terms Dictionary以Terms Index共同构成与Burst-Trie类似的数据结构,Terms Dictionary含两部分信息:1. NodeBlock记录Dictionary的所有Terms;2. FieldMetadata存储了FieldInfos信息和Segment的统计信息。

    关于倒排索引还有Postings List,这部分内容将在下篇文章中介绍。

     

    转载自: 

    展开全文
  • MapReduce程序 完整实验报告 和 jar包 和简单实验数据
  • 采用MFC可视化,通过建立倒排索引表,简单实现了搜索功能
  • MapReduce倒排索引实现

    2016-12-05 08:28:35
    输入数据 ...本实例设计的倒排索引在文件数目上...除此之外,还可以利用复合键值对等实现包含更多信息的倒排索引。 参考来源 参考自 http://www.cnblogs.com/xia520pi/archive/2012/06/04/2534533.html

    输入数据

    这里写图片描述
    这里写图片描述

    输出数据

    这里写图片描述

    代码

    package com.test.ReversedIndex;
    
    import java.io.IOException;
    import java.util.StringTokenizer;
    
    import org.apache.hadoop.mapreduce.Mapper;
    import org.apache.hadoop.mapreduce.Reducer;
    import org.apache.hadoop.io.Text;
    import org.apache.hadoop.io.IntWritable;
    import org.apache.hadoop.mapreduce.lib.input.FileSplit;
    import org.apache.hadoop.conf.Configuration;
    import org.apache.hadoop.mapreduce.Job;
    import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
    import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
    import org.apache.hadoop.fs.Path;
    
    public class ReversedIndex {
        public static class ReversedIndexMapper extends Mapper<Object, Text, Text, Text> {
            public void map(Object key, Text value, Context context) throws IOException, InterruptedException {
                //FileSplit fs = new FileSplit();
                StringTokenizer st = new StringTokenizer(value.toString());
                String fileName = ((FileSplit) context.getInputSplit()).getPath().getName();
                while (st.hasMoreTokens()){
                    String word = st.nextToken();
                    String outputKey = word + ":" + fileName;
                    context.write(new Text(outputKey), new Text("1"));      
                }
            }
    
        }
    
        public static class ReversedIndexCombiner extends Reducer<Text, Text, Text, Text> {
            public void reduce(Text key, Iterable<Text> values, Context context) throws IOException, InterruptedException {
                int sum = 0;
                for (Text value:values){
                    sum += Integer.parseInt(value.toString());
                }
                int index = key.toString().indexOf(":");
                String word = key.toString().substring(0, index);
                String fileName = key.toString().substring(index+1);
                context.write(new Text(word), new Text(fileName + ":" +Integer.toString(sum)));         
            }
        }
    
        public static class ReversedIndexReducer extends Reducer<Text, Text, Text,Text> {
            public void reduce(Text key, Iterable<Text> values, Context context) throws IOException, InterruptedException {
                String newValue = "";
                for (Text value:values){
                    newValue += (value.toString() + ";");               
                }
                context.write(key, new Text(newValue));
            }
        }
    
        public static void main(String[] args) throws Exception {
            Configuration conf = new Configuration();
            Job job = new Job(conf, "ReversedIndex");
            job.setJarByClass(ReversedIndex.class);
            job.setMapperClass(ReversedIndexMapper.class);
            job.setCombinerClass(ReversedIndexCombiner.class);
            job.setReducerClass(ReversedIndexReducer.class);
    
            job.setOutputKeyClass(Text.class);
            job.setOutputValueClass(Text.class);
    
            FileInputFormat.addInputPath(job, new Path(args[0]));
            FileOutputFormat.setOutputPath(job, new Path(args[1]));
    
            System.exit(job.waitForCompletion(true) ? 0:1);
    
        }
    
    
    }
    

    说明

    本实例设计的倒排索引在文件数目上没有限制,但是单词文件不宜过大(具体值与默认HDFS块大小及相关配置有关),要保证每个文件对应一个split。否则,由于Reduce过程没有进一步统计词频,最终结果可能会出现词频未统计完全的单词。可以通过重写InputFormat类将每个文件为一个split,避免上述情况。或者执行两次MapReduce,第一次MapReduce用于统计词频,第二次MapReduce用于生成倒排索引。除此之外,还可以利用复合键值对等实现包含更多信息的倒排索引。

    参考来源

    参考自 http://www.cnblogs.com/xia520pi/archive/2012/06/04/2534533.html

    展开全文
  • 倒排索引(英语:Inverted index),也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。 ...

    Introduce to Inverted List

    倒排索引(英语:Inverted index),也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。
    有两种不同的反向索引形式:
    • 一条记录的水平反向索引(或者反向档案索引)包含每个引用单词的文档的列表。
    • 一个单词的水平反向索引(或者完全反向索引)又包含每个单词在一个文档中的位置。
    后者的形式提供了更多的兼容性(比如短语搜索),但是需要更多的时间和空间来创建。

    英文为例,下面是要被索引的文本:

    • T_0="it is what it is"
    • T_1="what is it"
    • T_2="it is a banana"

    我们就能得到下面的反向文件索引:

     "a":      		{2}
     "banana": 	{2}
     "is":     		{0, 1, 2}
     "it":     		{0, 1, 2}
     "what":   		{0, 1}
    后面的编号对应的就是文档号,例如,“a”只在T2中出现
    其实倒排列表还可以存储额外的信息,像tf(term freq),df(doc freq),postition(term posititon),例如如下所示额外存储了term在文档中的位置
    "a":      		{(2, 2)}
    "banana": 	{(2, 3)}
    "is":     		{(0, 1), (0, 4), (1, 1), (2, 1)}
    "it":     		{(0, 0), (0, 3), (1, 2), (2, 0)} 
    "what":   		{(0, 2), (1, 0)}
    
    详细的倒排索引知识请见参考[1]的文章。

    MapReduce Implementation

    实现一

    下面我将实现的倒排列表时带有term freq信息的。MapReduce实现很简单,最最简单的伪代码实现如下:

    class MAPPER
    	procedure MAP(docid n, doc d)
    		for all term t in doc d
    			EMIT(term t, <n, 1>)
    			
    class REDUCER
    	method INITIALIZE
    		t(pre) <-- null
    	procedure REDUCER(term t, postings[<docid n1, tf1>,<docid n2, tf2>....])
    		P <-- new ASSOCIATIVE_SORTED_MAP
    		if t(pre) != t AND t(pre) != null
    			EMIT(t, P)
    			P.RESET
    		for all posting<n, tf> in postings[....]
    			P{n, tf} = P{n, tf++};
    	method CLOSE
    		EMIT(term t, P)


    以上实现中,Mapper每次都提交一个三元组<term t, docid n, 1>,然后在Reducer端,在对相同的term进行每个doc 的tf统计,最后提交。方法确实很简单,基本上所有的工作都在Reducer端完成,Mapper端只是分解doc提交而已,如果一篇文章很长,每个term出现的次数又比较多,那么这样导致 mapper提交次数过多,生成的中间结果过多,网络传输就会很频繁,从来在shuffle和sort阶段很费时费力。实现二就简单简单解决了这个问题

    实现二


    该实现在mapper端词频做了统计,然后再提交各Reducer,这样就大大减少了mapper的提交次数。这样还是存在问题的。
    基本的MapReduce执行框架不能保证Mapper端提交的value被发送到reducer的排序问题,就是说,不能保证在Reducer端相同的key所对应的value列表的值是有序的。reducer端对于相同的key必须缓存其值列表。然后再在内存进行排序,最后在写到磁盘,这样很有可能会导致reducer端out-of-memory 。

    一个比较好的解决办法是让MapReduce框架帮我们做value的排序工作,以此来保证传递给reducer的相同的key所对应的values列表值是有序的。在Mapper端用提交以下形式来代替原先的de

    (tuple <term t, docis n>, tf)

    这是一种比较典型的MapReduce value-to-key转换的设计模型,这样的话,在Reducer端缓存的postings列表的内存使用率将大大降低,从而减少out-of-memory发生,具体实现如下伪代码:



    Code

    /**
       * input format
       *    docid<tab>doc content
       *    
       * output format
       *    (term:docid)<tab>(tf in this doc)
       *
       */
      public static class InvertedListMap extends Mapper<IntWritable/*docid*/, Text/*doc content*/, Text, IntWritable> {
    
        @Override
        protected void map(IntWritable key, Text value, Context context)
            throws IOException, InterruptedException {
          HashMap<Text, IntWritable> freqs = new HashMap<Text, IntWritable> ();
          
          // the document can be preprocessed by thrid analynized tool first
          // here is simplify this procedure using split by whitespace instead
          String[] terms = value.toString().split(" "); 
          for (String term : terms ) {
            
            if (term == null || "".equals(term)) continue;
            
            if (freqs.containsKey(new Text(term))) {
              int tf = freqs.get(new Text(term)).get();
              freqs.put(new Text(term), new IntWritable(tf + 1));
            } else {
              freqs.put(new Text(term), new IntWritable(1));
            }
          } // end of for loop
          
          Iterator<Map.Entry<Text, IntWritable>> entryIter = (Iterator<Entry<Text, IntWritable>>) freqs.entrySet().iterator();
          while (entryIter.hasNext()) {
            Map.Entry<Text, IntWritable> entry = entryIter.next();
            Text tuple = new Text();
            tuple.set(entry.getKey().toString() + ":" + key.toString());
            context.write(tuple, freqs.get(entry.getKey()));
          }
        }
        
      }
      
      public static class InvertedListReduce extends Reducer <Text, IntWritable, Text, Map<IntWritable, IntWritable>> {
    
        private String term = null;
        private Map<IntWritable, IntWritable> posting = null;
        
        @Override
        protected void setup(Context context)
            throws IOException, InterruptedException {
          term = null;
          posting = new TreeMap<IntWritable, IntWritable>();
        }
    
        @Override
        protected void cleanup(Context context)
            throws IOException, InterruptedException {
          context.write(new Text(term), posting);
        }
    
        @Override
        protected void reduce(Text key, Iterable<IntWritable> values,
            Context context) throws IOException, InterruptedException {
          String[] tuple = key.toString().split(":");
          if (term != null && !term.equalsIgnoreCase(tuple[0])) {
            context.write(new Text(tuple[0]), posting);
            posting.clear();
          } else {
            for (IntWritable val : values) {
              posting.put(new IntWritable(Integer.parseInt(tuple[1])), val);
            }
            
            term = key.toString();
          }
        }
        
      }



    今天就到这了。关于如何优化Map和Reduce,Google MapReduce的 Pairs 和 Stripes优化过程[3]

    后续考虑一下这个MapReduce倒排索引同时进行索引压缩存储。


    Reference


    2、2010 - Jimmy Lin - Data-Intensive Text Processing with MapReduce

    展开全文
  • C风格文件、C++风格读写操作 、英文文章单词的正确分割 、基于Trie树实现文件词频统计 、基于Trie树实现倒排索引的文件词频统计
  • 对搜狐(或者csdn)爬取新闻(博客)标题,然后把这些新闻标题和它的链接地址上传到hdfs多个文件上,一个文件对应一个标题和链接地址,然后通过分词技术对每个文件中的标题进行分词,分词后建立倒排索引以此来实现搜索...
  • 通过kafka获取爬虫爬到的数据,使用Dstream中的map,flatmap,reduce等对数据进行倒排索引,然后通过rdd将数据持久化到Hbase中。 实时运行,每10秒处理一次收到的数据。 导入关联词库程序: 通过python和...
  • 倒排索引java实现

    2020-10-02 01:00:14
    倒排索引的java实现,对于已经转化为txt的网页文档使用IK分词,然后建索引 倒排索引的java实现,对于已经转化为txt的网页文档使用IK分词,然后建索引
  • 倒排索引原理和实现

    千次阅读 2018-08-12 21:56:19
    关于倒排索引 搜索引擎通常检索的场景是:给定几个关键词,找出包含关键词的文档。 怎么快速找到包含某个关键词的文档就成为搜索的...倒排索引源于实际应用中需要根据属性的值来查找记录,lucene是基于倒排索引实现...
  • 基于hadoop集群系统(也可以在伪分布式系统上运行)系统使用Java编写的倒排索引实现,具有使用停词表功能,使用正则表达式选择规范的单词。代码重构了setup(),map(),combiner(),partitation()和reducer()函数,...
  • C语言实现倒排索引算法(含全部源码) C语言实现倒排索引算法(含全部源码) C语言实现倒排索引算法(含全部源码) C语言实现倒排索引算法(含全部源码)
  • c++实现倒排索引算法

    2020-12-03 17:17:12
    c++倒排索引算法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,828
精华内容 12,331
关键字:

倒排索引的实现