从零开始Java搜索引擎开发-Solr篇
无论是电商、招聘、社交还是教育,每个领域都有“搜索引擎”的用武之地。Solr是基于Lucene的一个企业级搜索引擎开发框架,它文档全、社区活跃、可定制化程度高。本系列文章主要介绍Java搜索引擎开发过程中将会遇到的问题、需求实现、问题解决和原理分析。包括零基础入门开发、进阶定制化开发以及搜索领域相关的算法分析。
  • 搜索引擎入门——启动第一个Solr应用   

    零、关于Solr摘自维基百科: Solr(读作“solar”)是[Apache Lucene](https://zh.wikipedia.org/wiki/Lucene)项目的开源企业搜索平台。其主要功能包括全文检索、命中标示、分面搜索、动态聚类、数据库集成,以及富文本(如Word、PDF)的处理。Solr是高度可扩展的,并提供了分布式搜索和索引复制。Solr是最流行的企业级搜索引擎,Solr 4还增加了NoSQL支持。 Solr是用Java编写、运行在Servlet容器(如[Apache Tomcat](https://zh.wikipedia.org/wiki/ApacheTomcat)或Jetty)的一个独立的全文搜索服务器。 Solr采用了[Lucene](https://zh.wikipedia.org/wiki/Lucene) Java搜索库为核心的全文索引和搜索,并具有类似REST的HTTP/XML和JSON的API。 Solr强大的外部配置功能使得无需进行Java编码,便可对其进行调整以适应多种类型的应用程序。Solr有一个插件架构,以支持更多的高级定制。 因为2010年Apache Lucene和Apache Solr项目合并,两个项目是由同一个[Apache软件基金会](https://zh.wikipedia.org/wiki/Apache%E8%BD%AF%E4%BB%B6%E5%9F%BA%E9%87%91%E4%BC%9A)开发团队制作实现的。提到技术或产品时,Lucene/Solr或Solr/Lucene是一样的。 Solr的历史2004年,Solr作为CNET Networks为公司网站添加搜索功能的一个内部项目,由Yonik Seeley创建。 后来Yonik Seeley随Grant Ingersoll和Erik Hatcher创建了LucidWorks(原名Lucid Imagination),公司提供商业支持、咨询和Apache Solr搜索技术的培训。2006年1月,CNET Networks决定捐赠其到Apache软件基金会顶级项目Lucene,公开发布其源代码。像在Apache软件基金会的任何新项目一样,其进入了一个潜伏期,以助于解决组织、法律和金融问题。2007年1月,Solr结束孵化状态,稳步成长,累积功能,从而形成聚集了用户、参与者和提交者的强大社区。即便作为一个非常新的开源项目,Solr已被应用于一些流量很高的网站。2008年9月,Solr 1.3发布了许多增强功能,包括分布式搜索功能和性能增强等。2009年11月,Solr 1.4发布。此版本对索引、搜索和分面做了增强,并有许多其它改进,例如富文本(PDF、Word和HTML)的处理,基于Carrot 2的搜索结果聚簇,与数据库集成的改进。该版本还提供了许多插件。2010年3月,Lucene和Solr项目合并。产品现在由同一组参与者共同开发。在2011年,Solr改变了版本编号方案,以便与Lucene的匹配。为了使Solr和Lucene有相同的版本号,Solr 1.4的下一版本号为3.1。2012年10月,Solr 4.0版本发布,包括新的SolrCloud功能。以上Solr的历史也是摘自维基百科,目前Solr的稳定版本已经升级到了8.\。而且官方提示: (( (( (( dtextlatestfirstpositiontitle:java^15 ) OR ( dtextlatestfirstpositiontitle:"java"~3^7 ) OR ( dtextlatestfirstcompanyname:java^10 ) OR ( dtextlatestfirstcompanyname:"java"~4^5 ) OR ( dtextlatestsecondpositiontitle:java^5 ) OR ( dtextlatestsecondpositiontitle:"java"~3^2 ) OR ( dtextlatestsecondcompanyname:java^5 ) OR ( dtextlatestsecondcompanyname:"java"~4^2 ) OR ( dmtextotherpositiontitles:java^3 ) OR ( dmtextothercompanynames:java^3 ) OR ( dtexttalenteducationschool:java^15 ) OR ( dtexttalenteducationschool:"java"~2^7 ) OR ( dtexttalenteducationprofessional:java^15 ) OR ( dtexttalenteducationprofessional:"java"~5^7 ) OR ( dtextnostoreworkprojectdetail:"java"~5^1 )) ) AND ( (( expectcityid:33102 )) )) )) 关键字查询字段包括最近一段经历的职位、公司;最近第二段经历的职位、公司;其他经历的职位、公司;毕业院校、专业、全文工作项目经历、简历更新时间、期望工作地点等十多个字段,每个字段的权重都是不同的情况。+ 开始全新的技术选型,开发全新的搜索服务。分布式搜索系统包括ES和Solr-cloud并不能很好的提升查询性能(相比于Solr单机版),分布式应对的主要是索引数据量的激增所带来的问题。但是分布式会比单机模式带来更多的集群管理问题。--- 一、开始后面整个系列的文章都是基于Solr4.7.2版本,大伙参考文章的思想、思路、方法即可。Solr4.7.2版本,启动方式包括jetty和tomcat,由于习惯问题以及频繁修改Solr源码和增加扩展的需要,我选择了tomcat启动方式,这里不做两者优劣对比。 下载旧版本Solr4.7.2Solr官方当然不会建议我们使用如此之旧的EOL版本,所以旧版本入口在官网不是很好找,这里直接给出[下载Solr4.7.2](https://archive.apache.org/dist/lucene/solr/4.7.2/)的链接。![图片](https://oomabc.com/staticsrc/img/201907/23/15638612295586c8e3a8c980b403ba866d620566f51a7.jpg)我们只要下载solr-4.7.2.zip包就行。压缩包解压之后的目录大致如下:![图片](https://oomabc.com/staticsrc/img/201907/23/1563862633349958600e5f42e4d31ae25ed11d6dc0a7a.jpg)大概说一下相关目录的用途:+ contexts:里面只有一个solr-jetty-context.xml文件,顾名思义,就是配置jetty启动时上下文中的solr参数。例如jetty的项目路径和项目访问根路径。+ etc:这里存的是和jetty相关其它配置。例如jetty的访问端口、连接池等等。+ example-DIH:solr的一个数据导入模块的用例,DIH就是data import handler的意思。它的插件支持从数据库、xml文件、word文本等数据源导入数据到Solr索引中。不过我一般不使用,可以了解下。真实应用场景会比较复杂,一个完整的索引数据源可能由多个数据库、多个数据服务甚至多个数据仓库接口组合而成。+ example-schemaless:是一个Solr最小单元的定义举例,也就是Core,可以理解为一个有完整意义的表。比如电商搜索中的商品索引就是一个Core。+ exampledocs:也是一些样例的数据文件,主要是配合example-DIH使用的一些数据源文件。+ lib:就是存放jetty启动时用的一些jar包。+ multicore:主要是支持Solr-cloud模式下的配置。但是4.7.2的cloud模式与当前8.\版本的cloud配置方式完全不同了,这里就不详细说明了。+ solr:Solr正式启动之后使用的目录,包括所有Core配置以及相关的索引数据。每个Collection的结构是一致的,代表一个独立的索引。+ webapps:默认配置下,是Solr的web目录,与tomcat的webapps目录一样。+ start.jar:官方提供的jetty启动脚本。 jetty启动官方提供的默认启动方式就是jetty,因此在你安装了jdk环境之后,启动是很方便的:bash13:57 wjyuian@wjyuianMacBookPro /Users/wjyuian/software/example% java -jar start.jar+ 在/contexts/solr-jetty-context.xml文件中配置Solr基本信息:XML/webapps/solr+ 在/etc/jetty.xml配置项目访问端口:XML 50000 1500 false 或者启动时指定端口号java -jar start.jar -Djetty.port8985。+ 在/webapps/solr/WEB-INF/web.XML中,配置solr索引的配置和数据存储目录:XML solr/home java.lang.String /Users/wjyuian/software/example/solr tomcat启动配置tomcat/conf目录下的server.xml文件:XML -------- 二、solr索引的配置和数据存储目录下面详细说一下solr的索引配置和数据目录。这个目录下存放的是一个个Core,也就是一个个独立的索引。例如在招聘行业就是,职位索引、订单索引、简历索引等等的配置。![图片](https://oomabc.com/staticsrc/img/201907/23/15638646661213869806210e34594a0e332e1d8edd338.jpg)例如上图所示项目的索引配置目录,包含了大约27个Core,其中就包括职位索引、订单所以、简历索引。 position我们进入到其中某一个Core,可以看到里面有两个子目录:conf和data。conf存放的就是结构化配置,data存放的就是实际索引数据。 solr.xml在索引配置的根目录下,还有一个solr.xml文件。XML --- 三、测试访问当我们使用jetty或者tomcat启动Solr之后,通过链接http://localhost:8985/solr//就可以访问到Solr的管理页面。![图片](https://oomabc.com/staticsrc/img/201907/23/1563865193760480984ec2aa64d7eb48987c56b43e0e7.jpg)在Core Selector下拉列表可以选择上面solr.xml中配置的所有Core。当选择了一个Core,点击Query菜单,然后Execute Query可以看到:![图片](https://oomabc.com/staticsrc/img/201907/23/15638653353393be045304a2e4a3eb592c2de7c4b9574.jpg) Core菜单介绍+ Overview:当前Core的总览数据,包括索引更新时间、文档数量、堆内存、数据版本、索引文件Segment数、主从同步状态、索引大小、Core实例的相关路径等等。+ Analysis:Core配置的分词器测试,比如Index阶段的分词、Query阶段的分词。+ Dataimport:数据导入配置,我这里没有配置。+ Documents:主要是通过接口进行索引文档的修改,一般不建议使用。+ Files:索引配置文件。需要重点关注的是schema.xml、solrconfig.xml、solrcore.properties。+ Ping:检查Core的存活情况。+ Plugins/Stats:显示Solr使用的相关插件信息、扩展信息。比如Solr的缓存配置,用到了哪些Cache;Core使用的search数据;高亮插件;查询语句分析器、转换器;数据更新插件等等。+ Query:进行Solr查询,这是最常用的页面,主要是用于索引数据查询和数据调试。+ Replication:进行索引的主从管理。显示了上次同步时间、下次同步时间、同步的数据量、同步状态、主的地址;以及手动执行同步和关闭同步操作。+ Schema Browser:对schema.xml配置进行更为全面的查看,包括静态配置数据和实时数据。下一章将会详细介绍schema.xml的内容和配置。---

    Solr   Java   搜索引擎   2019-07-24 浏览(407) 有用(0) 阅读原文>> [原创]
  • 搜索引擎入门——聊聊schema.xml配置   

    前言Lucene中一个很重要的概念就是文档(Document),它代表一条建立索引的独立且完整的数据。可以对标到我们关系数据库的一条记录。一个Document包含很多个域(Field),对标数据库的字段Column。Field的一些属性配置对标字段的属性。本身Lucene对Document的Field是开放式的,不同Field的Document可以索引到一起,有点类似于noSQL的概念,属于schema-free的。但是这种开放式结构会造成“开发一时爽,维护骂爹娘”的情况,所以Solr在封装Lucene的时候通过schema.xml文件来规范Document的Field定义。类似于MongoDB的一些ORM框架(Morephia、spring-data-mongo)做的事,其实就是定义一个标准、做个存根,方便排查。所以,schema.xml配置的内容就出来了:+ Field Type 定义:定义了字段类型,string、int、double、text等等,名字是自取的。+ Field 定义:字段,比如positionid、name、age等等。------ schema.xml的大致结构XML -- -- -- positionid keyword 从实际的配置文件也可以发现,schema中确实主要包含两个内容,types和fields。+ types:定义Field类型的元数据。+ fields:表示这个索引的每条数据包含哪些字段,分别是什么类型。+ copyField:表示将哪些字段(source)的值复制到某个字段(dest)。 比如我们的职位索引包含了职位标题、职位描述、任职要求、职位公司、工作地点等字段,如果想要关键字搜索包含这些字段,那么需要每个字段都拼接查询条件,然后通过OR连接。这样显得比较麻烦。 那么,我们可以建立一个名为keyword的综合字段,将以上需要关键字搜索的所有字段通过StringBuilder拼接好,然后设置到keyword中。 通过字段拼接虽然灵活,但是麻烦;这时候就用到copyField了。我们配置多个的copyField,source分别是那些字段,dest就是keyword。+ similarity:配置了似度类,这个类必须是继承了lucene-core.4.7.2.jar中的org.apache.lucene.search.similarities.Similarity。+ uniqueKey:定义了索引的主键,类似mySQL的唯一主键。+ defaultSearchField:查询参数q默认的查询域,当用户输入qjava时,默认搜索的就是这个参数指定的字段。当然用户可以通过qtitle:java来指定查询域为title。+ solrQueryParser:指定Solr参数q的默认查询逻辑。当用户输入qtitle:java age:[25 TO 30] city:上海,此时有三个查询条件,且用户未指定查询逻辑,那么就按照这里配置的默认的AND逻辑。如果要全量设置查询逻辑关键字,可以通过参数q.opOR来指定,也可以直接拼接在查询语句中qtitle:java AND age:[25 TO 30] AND city:上海。 types定义XML -- -- -- name就是一个唯一标识符,在后面fields定义时通过属性type指定。 class定义此类型实际的行为类。这个属性的值都是以solr.开头的,例如上面solr.StrField。solr对应标准的Solr目录org.apache.solr.schema。关于StrField、solr.BoolField等实际类型,可以去源码查看定义和解释。StrField字段是不会进行分词的,只会索引和存储。 precisionStep(很重要)对于TrieIntField, TrieFloatField, TrieLongField, TrieDoubleField这些继承与TrieField的数值类型字段,所指定的一个精度值,这也是一个数字,默认值是8。它主要是用于数值字段的范围查询,前提是Field的indexed属性必须是true。在TrieField.java的初始化方法中可以看到,其默认值是precisionStepArg,为8。如果配置值是小于等于0或者大于等于64,则配置值会重置为Integer.MAXVALUE。相当于没有启用这一配置,此时该字段的范围查询将会很慢,与普通的分词查询一样。Java@Overrideprotected void init(IndexSchema schema, Map args) { super.init(schema, args); String p args.remove("precisionStep"); if (p ! null) { precisionStepArg Integer.parseInt(p); } // normalize the precisionStep precisionStep precisionStepArg; if (precisionStep64) precisionStepInteger.MAXVALUE; String t args.remove("type"); if (t ! null) { try { type TrieTypes.valueOf(t.toUpperCase(Locale.ROOT)); } catch (IllegalArgumentException e) { throw new SolrException(SolrException.ErrorCode.SERVERERROR, "Invalid type specified in schema.xml for field: " + args.get("name"), e); } }}在TrieField中使用的NumericRangeQuery对该参数有比较详细的介绍: 该值越小,在索引阶段产生的token将会越多,索引的大小也会越大,但是会提升范围查询性能。这里建议的合理值范围是1~8,一般可以设置为4。一个字段值在索引是产生的token数公式是indexedTermsPerValue ceil(bitsPerValue / precisionStep)。 合适的precisionStep值通常由具体数据类型和使用场景决定的: + 当未指定时,所有数值类型的precisionStep默认值都是4(TrieField中设置了默认值是8)。 + 64位数据类型,比如long、double,理想的precisionStep值是6或者8。 + 32位数据类型,比如int、float,理想的precisionStep值是4。 + 如果某个字段的数值基数比较小,那么将precisionStep设置大一些会比较好。比如,数值都小于100,可以直接选择Integer.MAXVALUE作为precisionStep值。 + 由上面那个公式可以看出来,precisionStep值大于等于数据类型位数时(long、double类型,precisionStep64;int、float类型,precisionStep32),每个字段值在索引时都只会产生一个token,因此在查询的时候会非常慢,与普通的TermRangeQuery差不多。 + 如果你的数值字段只要求排序,不要求范围查询,那么通过将其配置为0或者大于64的任意int值即可。这样设置时,虽然查询效率几乎和纯文本字段一致,但是它的索引效率和排序效率却是远高于纯文本(StrField)类型的数字字段(将数字存储到文本字段)。 Comparisons of the different types of RangeQueries on an index with about 500,000 docs showed that TermRangeQuery in boolean rewrite mode (with raised BooleanQuery clause count) took about 30-40 secs to complete, TermRangeQuery in constant score filter rewrite mode took 5 secs and executing this class took -- -- -- solr.TextField看过前面的介绍就不会找错这个类,因为TextField类有很多,Lucene源码中也有org.apache.lucene.document.TextField。但这里配置的是org.apache.solr.schema.TextField。与上面的其它type一样,它也是通过org.apache.solr.schema.FieldTypePluginLoader.create(SolrResourceLoader, String, String, Node)方法来进行FieldType初始化的。Java@Overrideprotected FieldType create( SolrResourceLoader loader, String name, String className, Node node ) throws Exception { // 普通类型,通过类加载器来初始对象实例 FieldType ft loader.newInstance(className, FieldType.class); ft.setTypeName(name); // 加载查询阶段使用的分词器,typequery // 注:1 String expression "./analyzer[@type'query']"; Node anode (Node)xpath.evaluate(expression, node, XPathConstants.NODE); Analyzer queryAnalyzer readAnalyzer(anode); // 加载多term分词器:模糊查询、正则匹配、占位符查询等 expression "./analyzer[@type'multiterm']"; anode (Node)xpath.evaluate(expression, node, XPathConstants.NODE); Analyzer multiAnalyzer readAnalyzer(anode); // 指定typeindex或者未指定type的,都是索引阶段使用的分词器 // 注:2 expression "./analyzer[not(@type)] ./analyzer[@type'index']"; anode (Node)xpath.evaluate(expression, node, XPathConstants.NODE); Analyzer analyzer readAnalyzer(anode); // 加载用户指定的相似度计算类 // 注:3 expression "./similarity"; anode (Node)xpath.evaluate(expression, node, XPathConstants.NODE); //这是一个solr封装的工厂类,里面持有了lucene定义的Similarity类对象 SimilarityFactory simFactory IndexSchema.readSimilarity(loader, anode); if (null ! simFactory) { ft.setSimilarity(simFactory); } // 如果为定义query阶段的分词器,则用index阶段的分词器代替,并设置,query分词器是否明确定义为false if (null queryAnalyzer) { queryAnalyzer analyzer; ft.setIsExplicitQueryAnalyzer(false); } else { ft.setIsExplicitQueryAnalyzer(true); } // 如果index阶段分词器未定义,则用query阶段分词器代替,也可能两者都为空 if (null analyzer) { analyzer queryAnalyzer; ft.setIsExplicitAnalyzer(false); } else { ft.setIsExplicitAnalyzer(true); } // index、query两个阶段,至少定义了一个分词器,则进入下面的赋值流程 if (null ! analyzer) { ft.setAnalyzer(analyzer); ft.setQueryAnalyzer(queryAnalyzer); if (ft instanceof TextField) { // 这里的text对应类型是TextField if (null multiAnalyzer) { // 如果未定义多term分词器,则用query分词器代替 multiAnalyzer constructMultiTermAnalyzer(queryAnalyzer); ((TextField)ft).setIsExplicitMultiTermAnalyzer(false); } else { ((TextField)ft).setIsExplicitMultiTermAnalyzer(true); } ((TextField)ft).setMultiTermAnalyzer(multiAnalyzer); } } if (ft instanceof SchemaAware){ schemaAware.add((SchemaAware) ft); } return ft;}注1:通过来指定query(查询)阶段所使用的分词器,并进行相关配置。注2:通过或者来指定index(所以)阶段所使用的分词器,并进行相关配置。注3:这里的相似度类定义与上面介绍的配置在最外层的similarity标签一样。可以配置在里面,也可以配置在里面。class可以配置两种类型:1. org.apache.lucene.search.similarities.Similarity的子类;初始化之后会将其通过org.apache.solr.schema.SimilarityFactory匿名类的方式进行包装。2. org.apache.solr.schema.SimilarityFactory的子类,要实现public abstract Similarity getSimilarity()方法,次方法返回的还是org.apache.lucene.search.similarities.Similarity的子类。Javastatic SimilarityFactory readSimilarity(SolrResourceLoader loader, Node node) { if (nodenull) { return null; } else { SimilarityFactory similarityFactory; final String classArg ((Element) node).getAttribute(SimilarityFactory.CLASSNAME); final Object obj loader.newInstance(classArg, Object.class, "search.similarities."); if (obj instanceof SimilarityFactory) { final NamedList namedList DOMUtil.childNodesToNamedList(node); namedList.add(SimilarityFactory.CLASSNAME, classArg); SolrParams params SolrParams.toSolrParams(namedList); similarityFactory (SimilarityFactory)obj; similarityFactory.init(params); } else { // 这里会有类型强转的风险 similarityFactory new SimilarityFactory() { @Override public Similarity getSimilarity() { return (Similarity) obj; } }; } return similarityFactory; }} analyzer.index我在Solr中使用的分词器是IK分词器,所以index和query阶段的配置方式都是基于IK的配置。XML -- 指定的class值是IK分词器实现类的完整路径,它继承了org.apache.lucene.analysis.util.TokenizerFactory。我在index阶段设置了useSmartfalse,这是为了在索引阶段分出更多、更全面的关键词,主要是提高查全率。不过查准率会有所影响,因为出现了很多歧义分词。被注释掉的那一个filter是自己实现的,用于过滤单字切词的。我默认认为,单个字是不存在全文意义的,类似于停用词中的你、的,对与这些关键字的搜索,我直接返回无结果,因为无法分词,所以不会存在单字索引。但是招聘行业也有单字是有意义的,比如C表示C语言,所以这个filter中做了动态例外。后面三个filter是lucene预定义的,其作用分别是过滤停用词、转小写、关键字标记。关于分词器扩展以及filter链扩展,包括同义词扩展,可以参考我的另一篇文章[《搜索引擎进阶——IK分词器扩展》](https://oomabc.com/articledetail?atclide738d22188194d3fac7577d3c38a2219) analyzer.queryXML 在query阶段,分词器配置与index阶段很相似,主要有处不同:1. useSmart设置为true,目的是尽量保持用户关键字的原意,所以采用了智能分词,其实大致就是最大分词。2. 增加了两个filter。同义词过滤转换org.wltea.analyzer.lucene.IKSynonymFilterFactory和重复关键字过滤solr.RemoveDuplicatesTokenFilterFactory。关于分词设置useSmart的区别,可以参考另一篇文章[《搜索引擎开发——关键字预处理模块》](https://oomabc.com/articledetail?atclidcecf525bb9184a10a7f22ef619c4544f)的前言模块。------ fields这一部分定义了当前索引Core的文档结构,也就是包含哪些字段。需要注意的是,从Solr4.+之后的版本,必须要包含至少两个field定义:1. 主键字段:也就是在uniqueKey标签定义过的字段,例子中的是。2. version字段:。这是Solr自己会赋值的字段。 name指定字段名,正常情况下的命名规范是由小写英文、下划线、数字组成。英文开头,多个单词用下划线分隔。 type这就是在types中定义的所有type,值就是type的name。 indexed当前字段是否索引。false表示字段不会进行索引;true表示会进行索引,可以在该字段上进行筛选、排序。如果未配置,会从对应type定义上继承该配置值,默认值是false。 stored当前字段是否存储。 multiValued是否是多值字段。 required是否是必填字段。true表示必填,类似mySQL的NOT NULL。 dynamicField动态字段,字段名可以动态设置。一般来说,我会预留一些动态字段,以应对将来的字段新增。索引一旦超过10G,每次修改schema并重启会很费时,而且有一定风险。所以针对添加新字段的修改,通常通过预留的动态字段来实现。预留字段的原则是,每个类型各留一个单值动态字段、多值动态字段。XML关于schema.xml的相关配置就聊到这了。------

    Java   搜索引擎   schema   分词器   2019-07-24 浏览(393) 有用(0) 阅读原文>> [原创]
  • 搜索引擎入门——什么是中文分词以及它对于搜索引擎的意义   

    什么是分词分词就是将连续的字序列,按照一定的规范重新拆分、组合成词序列的过程。通常字序列是无意义或者弱意义的,而词序列是具有完整意义表达的最小单元,它比字序列饱满但比短语简练。所以分词的直接目的就是将一段文本,提取出一系列最符合文本本意的词序列。我们知道,在英文的行文中,单词之间是以空格作为自然分界符的,而中文只是字、句和段能通过明显的分界符来简单划界,但是词之间是没有形式上的分界符的,所以中文分词大多借助词库字典来进行分词。比如一句话:我是一个年过半甲的程序员,比较合理的分词结果就是我、是、一个、年过半甲、的、程序员。不过,分词的最终结果受应用场景、分词技术综合影响,具体的结果会稍有不同。比如,垂直领域的搜索引擎大多行业相关,所以其停用词(stopword)范围也不一样。上面例子中的我、是、的都被看做停用词,不会被索引,因为搜索这些关键字会被认为是无意义搜索。而对于年过半甲这个词,由于不是一个通用的词语,所以在基于词库的分词器中可能也不会被分出。 停用词(stopword)人类语言包含很多功能词。与其他词相比,功能词没有什么实际含义。最普遍的功能词比如限定词(“这”、“那”、“个”、“啊”等),这些词帮助在文本中描述名词和表达概念,如地点或数量。介词如:“下”,“上” 等表示两个词的相对位置。这些功能词的两个特征促使在搜索引擎的文本处理过程中对其特殊对待。第一,这些功能词极其普遍(词的文档频率很高)。记录这些词在每一个文档中的数量需要很大的磁盘空间。第二,由于它们的普遍性和功能,这些词很少单独表达文档相关程度的信息。如果在检索过程中考虑每一个词而不是短语,这些功能词基本没有什么帮助。在信息检索中,这些功能词的另一个名称是:停用词(stopword)。称它们为停用词是因为在文本处理过程中如果遇到它们,则立即停止处理(其实说是跳过处理比较好理解),将其扔掉。将这些词扔掉减少了索引量,增加了检索效率,并且通常都会提高检索的效果。停用词主要包括英文字符、数字、数学字符、标点符号及使用频率特高的单汉字等。简单的说,这类词几乎可以出现在任意一片文章中,所以不具备标记性。比如每一篇文章都含有的这个词,如果你在搜索引擎中搜索的,相当于没有搜索。 分词用途中文分词是文本挖掘的基础工作,也是让计算机自动理解文本含义的关键。只有分词准确了,计算机才能更好的理解词汇,进而理解短语、句子、段落、文章。中文分词也属于自然语言处理(NLP)的范畴。对于一句话,人可以根据自己的知识积累来明确哪些是词汇,哪些不是,但是如何让计算机也能理解或者说区分词汇呢?这个过程其实就分词算法。--- 分词算法其实,计算机领域很多算法最初都是从现实生活得到启发而产生的,当然也包括分词算法。 基于词库的分词我们可以回想一下,你在看到一句话的时候,是怎么确定哪些是词汇,哪些不是的?是因为你之前在别的地方看到过这些词汇,而且你当时确定这些就是一个个词汇,是不是?所以最简单的思路就是,我们也告诉计算机哪些是词汇就行了。这时候,就产生了第一种最简单、效果最直接的分词算法——基于词库的分词算法,也称为字符匹配算法。而我们是通过一个数据词典来汇总所有我们希望告诉机器的词汇,这就是所谓的词库。 正向最大匹配简单的过程就是,计算机扫描(注意,这里的扫描是正向的)一篇文章,找出其中所有的在词库中出现过的词汇。这个过程就是分词,当然除了词汇本身,通常还会得到每个词汇的位置、长度、词汇出现的次数等信息。基于词库的方法虽然简单直接,但也会出现一些问题,最常见的就是分词歧义。比如这样一句话“研究生命科学”,通常基于词库的分词算法会得到如下分词结果: 1. 如果是最大分词,则结果是:研究生、研究、生命科学、生命、科学。 2. 如果是最少切分,则结果是:研究生、命、科学,如果命不在词库,则只有研究生、科学。所以,不论哪种情况,都会出现歧义词汇研究生,因为它不符合当前语境。但由于我们是正向扫描文本的,所以它又是第一个匹配出来的,所以导致后面的生命科学被拆分了。这个时候,我们又可以向了,如果让生命科学是第一个分词出来,那么剩余的词汇就是研究而不是研究生了,是不是?所以就有了基于词库的第二种方法:逆向最大匹配算法。 逆向最大匹配这个算法还是会扫面字符串,然后找出其中所有在词库中定义的词汇,区别就是从右往左扫描。这个方法应该可以解决大部分句子中的歧义问题。具体到上面的例子,就是先扫描出生命科学,然后是研究生,很自然的就解决了正向最大匹配无法解决的问题。 双向最大匹配顾名思义,就是将正向最大匹配与逆向最大匹配的结果进行综合,可能会很好的分词效果。 基于统计的分词百科的解释是: 从形式上看,词是稳定的字的组合,因此在上下文中,相邻的字同时出现的次数越多,就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计,计算它们的互现信息。定义两个字的互现信息,计算两个汉字X、Y的相邻共现概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时,便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统计,不需要切分词典,因而又叫做无词典分词法或统计取词方法。 但这种方法也有一定的局限性,会经常抽出一些共现频度高、但并不是词的常用字组,例如“这一”、“之一”、“有的”、“我的”、“许多的”等,并且对常用词的识别精度差,时空(时间和空间)开销大。实际应用的统计分词系统都要使用一部基本的分词词典(常用词词典)进行串匹配分词,同时使用统计方法识别一些新的词,即将串频统计和串匹配结合起来,既发挥匹配分词切分速度快、效率高的特点,又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。基于词库的分词算法,有一个很明显的短板就是缺乏新词发现的能力。互联网时代的网络新词层出不穷,比如喜大普奔、BAT、老鹿蹒跚、撸啊撸等等。如果你的词库没有包含这些新词,则无法分词出相应的结果。统计法的分词算法在一定程度上可以解决新词问题,但前提是要这个分词系统准实时性的去统计网络上新出现的文本语料。 统计法是怎么工作的以下内容需要看官仔细阅读,它是我内心的真实思考过程,包含很多错误的具有参考意义的思考。注:这里讨论的统计法分词,与NLP里面的基于分词样本进行统计的分词算法有所不同。NLP中基于分词样本的统计分词算法,需要有已经准确分词并标注词性的样本进行训练(比如训练隐马尔科夫模型),它更多的是计算短语或者句子的概率,或者说是文本理解。而我们讨论的则是最基础的分词。 上面这段注释,是我之前的想法,可能不是很正确。在我的理解中,基于统计的分词算法是不需要词库的,而这里训练隐马尔科夫模型的样本其实就是分词的词库,而且是做好词性标注的分词词库,也是需要人工去维护的。所以,我下面介绍的统计法是按照我的理解而写出来的,仅做大家的参考,以免误导大家。从定义上来看就是有个系统去扫描海量的文本语料,然后统计字符串(两个字符、三个字符、四个字符等)出现的比例或者概率。但是如果将一段文本进行切分,然后进行统计呢?有一个比较简单有效的语言模型可以适用于此,就是N-GRAM模型。这个模型也通常运用在关键字纠错或者语句相似度(这里的相似度不单单是指极少字符变动的语句,如利文斯顿编辑距离算法)计算上。 我错误的思路我们可以选取N为4,那么我对一段连续的无标点的文本进行拆分,分别拆为两个字、三个字、四个字。还是那句话研究生命科学,那么可以拆为研究、研究生、研究生命、究生、究生命、究生命科、生命、生命科、生命科学、命科、命科学、科学。然后对所有语料进行这种拆分,然后统计比例生成此组概率表,这样就可以确定哪些词通常能组成一个有意义的分词。如果统计比例之后,再回头看看它是如何解决歧义的呢?A研究生、命科学或者B研究生、命、科学,这两种就是歧义的情况,正确的情况是C研究、生命科学。很显然,我们要从此组概率表证明,C成词合理的概率要高于A和B即可。很明显,A的命科学在语料库中概率是远低于生命科学的。等等!!! 命科学在语料库中概率是远低于生命科学 这个念头是自然而然的出现在我的脑海,这是基于我的常识判断的。在常识中命科学肯定不是一个词,所以才会觉得它的概率小,但事实上只要出现生命科学就一定出现命科学,所以命科学的概率不可能小于生命科学的。所以,我之前所有的想法都是错误的:1. 统计法分词不需要基于样本或者词库。2. N-GRAM模型是简单的字符拆分,就像我例子中的那种。其实应该是这样的:1. 统计法中的样本,并不简简单单的等同于基于词库分词算法中的词库。它还有一个重要的因素就是词性标注。2. N-GRAM是一个语言模型,不是我所介绍的拆词方式。 统计法分词的分享——HanLP官网:[HanLP](http://www.hanlp.com/) HanLP是一系列模型与算法组成的NLP工具包,由大快搜索主导并完全开源,目标是普及自然语言处理在生产环境中的应用。HanLP具备功能完善、性能高效、架构清晰、语料时新、可自定义的特点。它提供的功能非常多,有兴趣的可以自行查阅。--- 分词有什么用这里主要说说分词模块在搜索引擎中的作用,这也只是分词用途的一个部分。我有另一篇文章介绍了搜索引擎中的链表操作[《搜索引擎进阶——Lucene链表操作解析 》](https://oomabc.com/articledetail?atclida44bc93b559148e8a30b5a372f632ba3)。链表操作的对象顾名思义就是链表,而分词就是生成倒排链表的依据,其大致过程就是:1. 每份参与索引的文档进行编号,递增序列;2. 索引模块中的分词子模块对文档进行扫描,将文档进行分词,得到Token。Token信息包括分词内容、在文档中的位置、词频等信息。3. 将Token文本一致的文档编号进行递增排列,形成倒排链表。为什么叫倒排,其实是相对于传统关系型数据库的数据检索方式而言。传统数据库通常通过数据记录来定位数据,然后查询对应的属性值。而倒排索引则是根据属性值来定位记录位置。最终分词得到的Token的精度决定了倒排链表的精度,从而影响搜索引擎两大基本指标——查全率和查准率。故而,分词之于搜索引擎的地位就是基石。顺便提一句个人看法,对于百度、谷歌这类全文搜索引擎来说,查准率的优先级会高于查全率;因为目标数据集过于庞大,用户反而最关心的是查准率和排序。而对于垂直类搜索引擎来说,查全率和查准率都很重要,或者说查全率会稍微重要一点,比如小电商、小招聘。总的来说,随之数据集的增加,查全率的重要性会降低,而查准率的重要性会提升,对应的排序效果也会变得越来越重要。

    搜索引擎   分词   中文分词   2019-08-13 浏览(479) 有用(0) 阅读原文>> [原创]
  • 搜索引擎入门——Solr查询参数详解以及如何使用Java完成对接   

    零、前言经过文章[《搜索引擎入门——启动第一个Solr应用 》](https://oomabc.com/articledetail?atclidf9b37293ec184ab6ad4d672327057dd7)的介绍,我们已经成功搭建了一个搜索引擎服务。通过使用Solr提供的rest接口,我们已经能够完成索引重建、更新以及查询的功能。本章主要介绍以下几个方面的内容:+ 查询界面的基本使用:基本关键字查询、二次查询、排序、分页、默认查询字段、返回字段设置等等。+ 查询语句的调试:主要是进行关键字查询得分的调试,可以清楚的看到每一个结果所匹配的条件以及详细得分计算情况。+ 关键字高亮与摘要:搜索引擎常见的功能,对命中的关键字进行高亮展示。+ 高级自定义查询:主要是借助solr封装的一些函数进行字段的简单计算,最终干预文档得分。------ 一、基本查询![图片](https://oomabc.com/staticsrc/img/201907/24/15639473826215ea242bf30ce49149aad6480e98c91a3.jpg)上图是我们项目中使用的一个职位索引的查询页面,这是Solr启动之后我们所要重点关注的查询页面。 普通查询语句 q这个参数可以直接输入关键字,那么它查询的字段就是schema.xml中配置的默认查询字段keyword。关于schema.xml的相关配置可以参考另一篇文章[《搜索引擎入门——聊聊schema.xml配置》](https://oomabc.com/articledetail?atclidadb7b81f31ca4b45b1315b3af89a9c23)。那么,qjava的查询结果与qkeyword:java的查询结果是一样的。这个q里面可以设置任意多组查询条件,比如qpositiontitle:java cityname:上海 functionname:技术,就是搜索上海的技术职能下的java岗位。多组条件可以用AND符号连接,如果都是AND可以用空格代替,系统自动使用defaultOperator配置的连接符。当然我们也可以进行更复杂的查询,类似mySQL一样:q(positiontitle:java AND cityname:上海) OR (positiontitle:php AND cityname:杭州),搜索上海的java或者杭州的php。设置权重q(positiontitle:java AND cityname:上海^100) OR (positiontitle:php AND cityname:杭州^50),通过^符号来指定查询条件的权重,这个语句就表示上海的职位权重是100,杭州的职位权重是50,上海的职位就排在杭州的职位之前了。设置跨度(我暂时先这么叫,具体原理目前还在研究)如果我要搜索关键字“java上海”,使用qkeyword:java上海,我们测试环境的数据结果只有4条。但是在我印象中,即使是测试环境也绝不可能只有这么点数据。原来此时的查询语句默认要求java和上海两个关键字是要在一起的,也就是连起来的。而我们大部分职位java是属于标题或者职位描述,上海是属于工作地点字段,虽然这些字段都copy到keyword,但并不一定是连着的。所以,应该这么查qkeyword:"java上海"~100",将关键字用双引号引起来,然后通过字符~来指定分词结果的跨度。这里大概的意思就是,查询keyword同时包含java和上海的职位,而且java和上海两个关键字的距离不超过100。这个参数是必传的,如果实在没有查询条件,请使用q:。 过滤查询 fqfq是Filter Query的缩写,从字面意思可以看出来,主要的功能就是filter,也就是过滤。fq的查询结果会被缓存起来,下次使用相同的fq时,会直接命中缓存,所以性能很好。但是fq只负责过滤结果集,而无法使自身命中结果参与文档得分的计算。fq可以设置多组,所有fq之间是AND关系;当然也可以像q一样,通过AND和OR来拼接多组条件,然后设置在一个fq上。如果我们要查询上海的java或者杭州的php,但必须是“高级”的,我们这可以这样q((positiontitle:java AND cityname:上海) OR (positiontitle:php AND cityname:杭州)) AND positiontitle:高级。这样查的时候,positiontitle:高级^100可以设置条件权重为100。当然,我们还可以通过q与fq的组合进行查询:q(positiontitle:java AND cityname:上海) OR (positiontitle:php AND cityname:杭州),fqpositiontitle:高级。最终出来的结果和上面仅使用q的时候一样,只是这里的高级不能设置权重(设置了无效)。所以建议,需要反映在文档得分的字段的查询设置在q中,对于那些仅仅需要筛选的字段,都放在fq上。例如我只要看上海的职位,那么就将cityname:上海设置到fq上。fq还有另一个很有用的地方,就是与facet配合使用,来动态生成筛选器。从这个配合使用看了,fq确实是在结果集之上进行了二次过滤。所以多个fq可以对应多个facet,产生多组facet统计结果。关于fact的使用,可以参考另一篇文章[《搜索引擎入门——solr筛选器facet的应用》](https://oomabc.com/articledetail?atclid833939e86efd4c98be5af1e007add093)。 sort这个简单,顾名思义就是排序,也支持多个字段的排序,类似mySQL。sortsalary DESC,headcount ACS表示先按照薪资降序,在薪资一致的情况下按照招聘人数升序。 分页这个类似于mySQL的LIMIT first, limit,Solr通过start和rows两个字段来实现分页,分别对应first和limit。start默认值是0,表示从第一条数据开始,rows表示本次查询要求返回几条数据。 flField List缩写,用于设置需要返回的字段,多个字段之间用英文逗号分隔,预定义字段文档得分用score指定。很多时候我们的document字段很多,达到几百是很常见的,如果我们一次返回50条数据,那么返回的数据量也是很客观的,尤其是有很多字段是大文本的情况下。那么我可以通过fl参数来指定返回哪些字段,只返回需要的字段是一个明智的选择。我通常指返回主键。但是我们如果要返回所有字段,再加上score,总不能将所有字段都列出来吧,有点麻烦。其实你只要这样fl,score,也就是说,这里的字段支持通配符。 dfDefault Field,也就是默认查询字段,本身是定义在schema.xml中的keyword。所以在qjava时,查询的是keyword字段。配合这个参数使用,可以指定默认查询字段,比如qjava&dfpositiontitle,那其查询结果就与qpositiontitle:java一致了。------ 二、查询语句调试我们在搜索功能开发过程中经常会遇到以下两种问题:1. 关键字搜索多个字段,且每个字段的权重不同,但是查询结果的排序与预想的顺序不同。2. 某些关键字查询,明明应该有结果,但事实上的查询结果却是0。上面这两种情况都需要借助Solr的debugQuery功能,来进行调试。 debugQuery设置debugQuerytrue,查询结果中会额外返回本次查询使用的query分析结果(query重新各个阶段的条件),如果有结果返回,还会返回每个结果文档的得分细节。![图片](https://oomabc.com/staticsrc/img/201907/24/156395324956596f08d851d5a41909982b699f1a58174.jpg)上图就是条件qkeyword:java^11 address:杭州^343执行后返回的文档得分信息。name就是文档主键,这里就是positionid的值。后面就是这个文档的命中关键字后的得分计算过程,粗略看可以发现keyword得分11,address得分343,总分354。其中的terFreq、fieldWeight、idf、tf等值就是在相似度计算类中计算的,这里就是HunterOnSimilarity,在schema.xml中有配置。更详细的得分计算过程将会另开一篇文章进行讲解,它涉及到Lucene的相似度(文档与查询关键字的相似度)计算模型——空间向量模型,也就是我们学过的向量夹角计算。----- 三、关键字高亮![图片](https://oomabc.com/staticsrc/img/201907/24/15639542132407e692f14e6a64a39b3ba572dc7d97f90.jpg)那些红色的关键字就是关键字高亮实现的功能,作为全文搜索引擎,Solr当然也提供了这个功能。 highlight模块XML true ((positiontitle:java AND cityname:上海) OR (positiontitle:php AND cityname:杭州)) positiontitle xml true 2上面是Solr关键字高亮查询之后,系统返回的参数。主要的高亮参数如下:+ hltrue,打开高亮功能+ hl.flpositiontitle,设置高亮字段,这个字段必须是分词字段,多个字段用英文逗号分隔。在不在q的查询条件中不重要,只要返回的文档有命中关键字,就有高亮;但是q中必须有关键字查询。+ hl.simple.pre,设置高亮关键字标签的前半部分。+ hl.simple.post,设置高亮关键字标签的后半部分。hl.simple.pre和hl.simple.post参数主要是配合前端展示使用,一般配置为html元素,然后通过class样式进行高亮展示。![图片](https://oomabc.com/staticsrc/img/201907/24/15639548939893af39a82c21347e3b20569a1d7144afe.jpg)----- 四、高级查询下面将通过一个例子来进行edismax的讲解,例子不一定非常合适,但作为功能说明是没有问题的。假设我们职位索引上有以下几个字段:+ cityname:职位工作城市。+ annualsalary:职位平均年薪,单位:元。+ maxshowannualSalary:职位年薪范围的最大值,单位:元。+ minshowannualSalary:职位年薪范围的最小值,单位:元。如果我们要查询上海的职位,那么无论是qcityname:上海还是fqcityname:上海都可以实现。如果我要将结果集中,年薪在50000(包含)到100000(不包含)的职位排序在最前面呢?那么需要在cityname:上海的条件下增加条件薪资条件,但是无论把annualsalary:[50000 TO 100000}^100查询条件放置在q或者fq,都无法实现这个效果,因为两者都是只返回了上海且年薪在50000~100000之间的结果。那要怎么设置查询条件,才能保持cityname:上海结果集范围不变,同时将年薪在50000~100000之间的职位排在最前面呢?这个时候就要借助edismax功能了。 edismaxdismax是Solr提供的一种高级查询功能,帮助用户通过简单的参数实现多字段多权重多场景的复杂查询。而edismax(Extended DisMax)则是在dismax基础上的扩展。本节主要介绍edismax中的bq和bf参数。bq它是在用户主查询的基础上,增加的一个额外的、可选的子查询语句,它只会影响文档的得分,而不会影响文档的范围。所以我们只要将annualsalary:[50000 TO 100000}^100放置在bq参数上即可。如果同时要将1000000以上的职位排在第二档,那么这样设置就行了edismaxtrue&bqannualsalary:[50000 TO 100000}^100 OR annualsalary:[1000000 TO ]^50。bf如果要在上海的结果集中,将maxshowannualSalary大于minshowannualSalary的职位排在前面,因为很多职位这两个字段都是一样的。这是两个字段做比较啊,一般的查询都是key-value的,不存在key-key的使用情况。这个时候我就需要借助bf了,bf也是在主查询之上增加的额外的、可选的子查询,也只会影响文档得分。不过它使用的不是key-value方式,而是Solr自定义的一些数学函数,比如div、map、min、max等。所以这个需求这样设置bfdiv(maxshowannualSalary,minshowannualSalary)^123,它会将minshowannualSalary0的排在最前面,其它maxshowannualSalary大于minshowannualSalary的紧随其后。一般通过bq和bf就能实现大部分的排序需求了。----- 五、Java客户端使用如果我们要实现工程化,就不能只使用Solr提供的管理界面,也不建议自己对rest接口进行封装使用。Solr提供了很多语言的客户端包,java有其对应的客户端包——solr-solrj-4.7.2.jar。代码比较简单:Javapublic static void main(String[] args) throws MalformedURLException, SolrServerException, UnsupportedEncodingException { String solrHost "http://192.168.50.35:8080/solr/position"; //创建连接对象 LBHttpSolrServer solrServer new LBHttpSolrServer(solrHost); //查询条件对象 SolrQuery query new SolrQuery(); StringBuilder queryBuilder new StringBuilder(); queryBuilder.append("cityname:\"上海\"~20^50"); // 城市 上海 queryBuilder.append(" AND annualsalary:{0 TO ]"); // 年薪大于0 query.setQuery(queryBuilder.toString()); query.setFilterQueries("headcount:[2 TO 5]"); // 通过fq设置headcount值在2到5 query.setFields("positionid,positiontitle,score,annualsalary,maxshowannualSalary,minshowannualSalary"); // 设置返回字段 query.setStart(0).setRows(15); // 设置分页// query.setSort("annualsalary", ORDER.desc); // 年薪降序;这里开启了排序,则后面的bf、bq等权重不会生效 // 开启关键字高亮 query.setHighlight(true); query.addHighlightField("cityname"); // 设置高亮字段 query.addHighlightField("address"); // 以下两个方法主要是在高亮的关键字前后加上html代码 query.setHighlightSimplePre(""); query.setHighlightSimplePost(""); // 设置edismax query.setParam("defType", "edismax"); query.add("bq", "annualsalary:[50000 TO 60000}^100 OR annualsalary:[100000 TO 110000]^50"); query.add("bf", "div(maxshowannualSalary,minshowannualSalary)^123"); // 从bf和bq分析,预测排序: // max/min的商,权重最高,所以商越大,排序越靠前; // 如果商相同,则annualsalary在5到6万(不含6w)的排序靠前,其次是10到11w的 // 打印查询条件,通常用于调试 System.out.println("query string " + URLDecoder.decode(query.toString(), "UTF-8")); // 调用接口 QueryResponse response solrServer.query(query, METHOD.POST); // 这里使用了post方式,如果参数很多可以使用post int queryCost response.getQTime(); // 查询耗时 int status response.getStatus(); // 状态码 System.out.println("status " + status + ", cost " + queryCost + "ms"); // 获得结果集 SolrDocumentList documentList response.getResults(); long total documentList.getNumFound(); // 结果总数,用于分页计算 System.out.println("total " + total); // 遍历文档,取出字段:positionid,positiontitle,score,annualsalary,maxshowannualSalary,minshowannualSalary for(SolrDocument doc : documentList) { // 取出字段,默认Object类型,如有需要自行转换 Object positionId doc.get("positionid"); Object title doc.get("positiontitle"); Object score doc.get("score"); Object annualSalary doc.get("annualsalary"); Object max doc.get("maxshowannualSalary"); Object min doc.get("minshowannualSalary"); System.out.println(score + " " + positionId + " / " + title + " " + annualSalary + " : " + max + " / " + min + " " + ((int)(Float.parseFloat(max.toString()) / Float.parseFloat(min.toString())))); }}输出结果:bashquery string qcityname:\"上海\"~20^50 AND annualsalary:{0 TO ]&fqheadcount:[2 TO 5]&flpositionid,positiontitle,score,annualsalary,maxshowannualSalary,minshowannualSalary&start0&rows15&hltrue&hl.flcityname&hl.fladdress&hl.simple.pre&hl.simple.post&defTypeedismax&bqannualsalary:[50000 TO 60000}^100 OR annualsalary:[100000 TO 110000]^50&bfdiv(maxshowannualSalary,minshowannualSalary)^123status 0, cost 21mstotal 6310766.0 42078 / 基金销售 50000.0 : 200000.0 / 40000.0 5716.0 73716 / P6-盒马鲜生-品类采销专家-上海 100000.0 : 500000.0 / 100000.0 5716.0 73900 / P6-盒马鲜生-高级Java开发工程师-上海 100000.0 : 500000.0 / 100000.0 5716.0 66437 / 大数据算法工程师 100000.0 : 500000.0 / 100000.0 5716.0 66439 / 大数据数据仓库开发 工程师 100000.0 : 500000.0 / 100000.0 5666.0 41663 / 客户经理 60000.0 : 300000.0 / 60000.0 5666.0 69337 / 运营管理中心副总/总监 300000.0 : 1500000.0 / 300000.0 5643.0 71928 / 销售专员 50000.0 : 200000.0 / 50000.0 4636.7143 50987 / 房源拓展经理/主管/专员 42000.0 : 200000.0 / 42000.0 4593.0 72425 / Java 100000.0 : 400000.0 / 100000.0 4578.1428 71633 / 销售经理 70000.0 : 300000.0 / 70000.0 4578.1428 66557 / 外汇经纪人 高薪招聘 42000.0 : 180000.0 / 42000.0 4563.5 58909 / 云计算工程师 120000.0 : 500000.0 / 120000.0 4563.5 77355 / 小额房贷资深销售总监(北京) 120000.0 : 500000.0 / 120000.0 4563.5 74745 / 房贷客户经理(上海) 120000.0 : 500000.0 / 120000.0 4从输出结果可以确定之前推测的排序方式是正确的: 从bf和bq分析,预测排序: max/min的商,权重最高,所以商越大,排序越靠前; 如果商相同,则annualsalary在5到6万(不含6w)的排序靠前,其次是10到11w的好了,关于Solr的查询参数介绍,以及Java客户端使用就介绍到这了。----

    Java   搜索引擎   edismax   查询条件   solrj   2019-07-24 浏览(657) 有用(0) 阅读原文>> [原创]
  • 搜索引擎入门——solr筛选器facet的应用   

    前言 搜索引擎的出现,整合了众多网站信息,恰恰起到了信息导航的作用。通用搜索引擎就如同互联网第一次出现的门户网站一样,大量的信息整合导航,极快的查询,将所有网站上的信息整理在一个平台上供网民使用,于是信息的价值第一次普遍的被众多商家认可,迅速成为互联网中最有价值的领域。互联网的低谷由此演变为第二次高峰。大家熟知的搜索引擎Google、百度、雅虎等是通用搜索引擎现如今的杰出代表,他们为互联网的发展做出了重要的贡献。然而,搜索引擎行业也不是一家公司就可以独撑天下的,从百度的上市、yahoo中国的并购一系列动作表明,如今的搜索引擎大战如同门户网站初期的竞争一样激烈。相信,通用搜索引擎在经历过一段时间的角逐后,也将会继续维持几大服务商各自分控一部分市场的局面。通用搜索引擎的性质,决定了其不能满足特殊领域、特殊人群的精准化信息需求服务。市场需求多元化决定了搜索引擎的服务模式必将出现细分,针对不同行业提供更加精确的行业服务模式。可以说通用搜索引擎的发展为垂直搜索引擎的出现提供了良好的市场空间,势必将出现垂直搜索引擎在互联网中占据部分市场的趋势,也是搜索引擎行业细分化的必然趋势。 垂直搜索引擎是针对某一个行业的专业搜索引擎,是搜索引擎的细分和延伸,是对网页库中的某类专门的信息进行一次整合,定向分字段抽取出需要的数据进行处理后再以某种形式返回给用户。垂直搜索是相对通用搜索引擎的信息量大、查询不准确、深度不够等提出来的新的搜索引擎服务模式,通过针对某一特定领域、某一特定人群或某一特定需求提供的有一定价值的信息和相关服务。其特点就是“专、精、深”,且具有行业色彩,相比较通用搜索引擎的海量信息无序化,垂直搜索引擎则显得更加专注、具体和深入。鄙人从事Java方向的搜索引擎开发有七八年了,多多少少积累了一点垂直搜索引擎相关的开发经验和踩坑经验。我涉及的两个垂直领域分别是电商和招聘,因此这一系列的文章会介绍个人在工作过程中遇到的一些需求、问题以及其解决方案。后续所有搜索相关的代码都是基于solr(版本较旧,基于4.7.\)的,不过其思路方法可以通用。1. 筛选器模块2. [关键词解析识别模块](https://oomabc.com/articledetail?atclidcecf525bb9184a10a7f22ef619c4544f)3. [同义词模块](https://oomabc.com/articledetail?atclide738d22188194d3fac7577d3c38a2219) 关于筛选器 筛选器统计拿招聘行业最常用的场景——职位搜索来说,当我们进入一个职位搜索频道,在顶部通常会有一块区域就是筛选器。展示的是全量可见职位对应的属性分布,例如:+ 行业:互联网(265) 房地产(254) 医药(201) ......+ 职能:技术(353) 产品(122) 销售(99) ......+ 地点:上海(313) 北京(125) 杭州(78) ......+ 年薪:15W以下(256) 15-30W(144) 30W以上(111) ......上面列出了当前职位池在行业、职能、地点、年薪四个维度的分布,选项括号里的数值就是对应的分布数量。solr给我们提供的管理界面上可以很方便的实现这个功能:http://localhost:8080/solr/position/select?q%3A&wtxml&indenttrue&facettrue&facet.field{!keycityFacet}cityid&rows0&facet.limit10参数说明:+ facettrue,开启facet统计功能+ facet.limit10,只返回职位数在前十的城市统计结果+ facet.field{!keycityFacet}cityid,这里对城市ID进行分组统计,结果中会给出当前结果集范围内每个城市的职位数;前面大括号内的key指定了这个统计列表的name,默认是字段名cityid。xml 0 5 true true : 10 {!keycityFacet}cityid xml 0 32649 27801 17637 14560 6975 1674 1293 1084 962 951 + rows0,将返回结果条数设置为0,这里只是为了看facet统计结果,所以不需要返回结果。如果要同时返回职能、行业、薪资的统计,只要重复设置facet.field即可:facet.fieldfunctionid&facet.fieldindustryid&facet.fieldannual。注:facet默认是基于当前筛选条件产生的结果集之上,进行统计的。 范围统计我们在索引职位的时候,年薪信息放在字段annualsalary中,单位是元;所以在facet年薪的时候会有个问题,出现的年薪统计会非常多。因为facet默认是值统计。此时有两个解决方案:1. 在索引的时候,就按照预定义的年薪段,提前算好年薪范围,存入annualsalaryrange字段。比如annualsalary200000,对应的annualsalaryrange'15-30W'。然后在facet的时候,facet.fieldannualsalaryrange即可。这样操作起来也很方便,但是缺点是一点算好,其分区就固定了,无法快速调整,触发修改分区算法并重建索引。2. 另一个方法是,在facet的时候,使用条件分组。不再是facet.field,而是facet.query了。facettrue&facet.query{!key15W以下}annualsalary:[0 TO 150000}&facet.query{!key15W以下}annualsalary:[150000 TO 300000}。范围筛选,中括号是闭区间,花括号是开区间。xml 25335 48570 筛选器选择基本的筛选器功能已经实现,而且用比较好的性能实现了筛选器选项的实时数据统计,perfect!!咱可以提测了。通知测试,然后去上个厕所,再去楼下放放风,休息休息。刚从厕所出来,就发现测试早已守株待兔,逮我个正着:先别走,有个严重的bug。一开始筛选器是这样的:+ 行业:互联网(265) 房地产(254) 医药(201) ......+ 职能:技术(353) 产品(122) 销售(99) ......+ 地点:上海(313) 北京(125) 杭州(78) ......+ 年薪:15W以下(256) 15-30W(144) 30W以上(111) ......当选择互联网的时候,就这样了:+ 行业:互联网(265) 房地产(0) 医药(0) ......+ 职能:技术(153) 产品(82) 销售(20) ......+ 地点:上海(113) 北京(105) 杭州(28) ......+ 年薪:15W以下(96) 15-30W(74) 30W以上(61) ......我:咦,行业对应的互联网之外的选择项怎么都是0了。回到上面介绍facet参数是的一句话注:facet默认是基于当前筛选条件产生的结果集之上,进行统计的。。所以,当选择互联网的时候,行业筛选器产生的统计都是互联网职位的统计,自然不会有其它行业的数据(我们一个职位只会属于一个行业)。当前的筛选条件只有行业的情况下,统计职能、地点、年薪都可以基于当前结果集,唯独行业不行。此时我的第一个念头就是,统计行业的时候我把行业条件删除;然后统计其它的时候将行业条件拼上。然后将两次统计结果进行合并,完美解决。等等,如果选择了行业、职能、地点甚至更多的时候,那不是在统计每一项的时候都要删除自身条件,那就刺激了,性能肯定急剧下降。回忆到,当选择了行业选项时,我solr中的查询语句是放在q字段上的qindustryid:101(暂且认为互联网的industryid101)。修复这个bug的诉求就转为统计行业的时候,不需要industryid:101条件生效,同时统计其它信息的时候,又要它生效。兔羊兔星谱,萨姆·泰姆斯奶味。作为开源搜索引擎框架,Solr早已考虑到这一切。使用过solr的同学肯定都知道两个最基本的条件筛选字段q与fq:+ q(查询器):参与score计算,可以通过^111设置查询语句的权重值,结果不会缓存,支持关键字命中高亮+ fq(过滤器):不参与score计算,无法设置查询语句的权重值,通常仅用于条件过滤;solr会对fq查询语句的结果进行缓存。相关缓存时间和缓存窗口值在solrconfig.xml中可配置。然鹅,fq还有一个牛叉的功能就是与facet联动实现我们上面提出的诉求。 筛选器联动过滤统计我们将industryid:101查询语句从q移到fq中,然后给这组条件加个标签,完整的就是q{!tagindustry}industryid:101。然后在统计行业的时候,将这个标签的查询语句排除即可:facet.field{!exindustry}industryid。这样一来,facet行业的时候,自动回跳过已选行业的条件语句,而其他统计则不受影响。说明:+ {!tagindustry}:将此组条件语句命名为industry+ {!exindustry}industryid:在统计industryid的时候,排除别名为industry的fq查询语句。如果要排除多个查询语句,用逗号隔开{!exindustry,function,city !tagindustryFacet}industryid。欧了,提测一波走起。一开始筛选器是这样的:+ 行业:互联网(265) 房地产(254) 医药(201) ......+ 职能:技术(353) 产品(122) 销售(99) ......+ 地点:上海(313) 北京(125) 杭州(78) ......+ 年薪:15W以下(256) 15-30W(144) 30W以上(111) ......当选择互联网的时候是这样的:+ 行业:互联网(265) 房地产(254) 医药(201) ......+ 职能:技术(153) 产品(82) 销售(20) ......+ 地点:上海(113) 北京(105) 杭州(28) ......+ 年薪:15W以下(96) 15-30W(74) 30W以上(61) ......完美实现了所见即所得,用户随便切换,点击的永远都是有结果的功能,而且性能还很高。当我再次从厕所出来的时候,发现测试MM投来了异样的眼光。\\。 筛选器的其它高级应用参考 [https://wiki.apache.org/solr/SimpleFacetParameters](https://wiki.apache.org/solr/SimpleFacetParameters)

    Solr   Facet   Java   搜索引擎   2019-05-06 浏览(442) 有用(0) 阅读原文>> [原创]
  • 搜索引擎进阶——关键字预处理模块   

    前言在搜索引擎的两个阶段会用到分词功能,分别是索引和查询。先说一下个人在垂直搜索引擎常用的索引分词设置(针对IK分词器)。无论采用何种分词设置,都会有一定的局限性或者说缺陷。因此在合适的阶段选择适合业务场景的分词方式才是最重要的。 索引阶段IK分词器提供了两种分词模式,通过布尔变量useSmart来设置。我在索引阶段设置useSmartfalse,其含义就是采用最小粒度分词,即会分出最多的可能的词汇(包括分词歧义词汇)。比如短语“中华人民共和国”的分词结果就是:中华人民共和国、中华人民、中华、华人、人民共和国、人民、共和国、共和、国。可以看出来,这个模式下分词器会将词库中有的词全部分出来。其中“华人”这个词在短语中属于歧义词,在这个语境中是不合适的。之所以选择这个模式,是因为在索引的时候尽可能的建立更多分词的倒排索引关系链,这与全文检索的“一次索引,多次查询”的特点有关。对于这个短语来说,除了“华人”之外的其它分词能搜索到这个短语,都是合理的场景。 查询阶段我在查询阶段(也就是用户输入关键字查询结果中的分词阶段),设置了useSmarttrue。其含义是IK分词器会用其智能分词功能给你最合适的分词结果,一般来说是词语最少的结果,但是它能最大程度保留原短语的语境含义。比如短语“中华人民共和国”的分词结果就是:中华、人民共和国。这两个词就最大程度保留了语境含义,而且其输入能完美映射到索引阶段。对于,索引中出现“中华”和“人民共和国”两个词语相距很远的情况,可以通过设置查询跨度来过滤。"中华人民共和国"~2,这里的2是指两个双引号之间的短语,各个分词的起始位置之间的最大允许间隔。 在Solr的schema.xml的配置xml ----- 关键字查询场景我们总是希望关键字查询在不失查准率的前提下,尽可能的承载更多的应用场景。+ 在关键字中输入职位ID(一串5位以上的数字),希望精准搜索到职位+ 输入“java 杭州 -阿里”,希望搜索出杭州的java职位,但是不要看阿里的+ 在关键字可以搜索更多字段的情况下,我输入“上海”,只希望搜索到工作地点是上海,而不是工作描述中出现上海的职位+ 输入“58”希望能搜索出所有五八同城的职位,在这个结果下可以多出一个ID是58的职位;类似的还有2345、360等+ 输入“包”,希望搜索出分类是包的商品,而不是那种“xxxx[包邮]”或者“xxxx上衣,与xx包更配”这种 职位ID搜索这是一个再简单不过的应用场景,在关键字输入框输入职位ID,根据职位ID查询到指定的职位。很显然我们可以规定通过“”来表示职位ID,例如“15006”表示搜索职位ID是15006的职位。当然也可以不需要额外的标记。需要根据职位ID搜索职位的场景,往往是不会有附带其它搜索需求的,因此只会出现一个职位ID。所以,我们只要判断关键字输入是否是数字,来确定是否是作为职位ID去搜索。如果这个输入框可以输入多个维度数据的ID,那么可以用“或”来查询,例如可能是职位ID、雇主ID等等。 关键字排除这是一个无论通用搜索引擎或垂直搜索引擎都会支持的一个功能。搜索有个约定俗成的规则就是,当我们需要搜索多组关键字的时候需要用至少一个空格进行分割。 例如我们在百度搜索“java-百科”,结果出现的就是同时包含“java”和“百科”的条目;但是当我们搜索“java -百科”,这里就是两组关键字“java”和“-百科”,也就是搜索“java”但不包含“百科”的条目。那我们的垂直搜索引擎要满足这个功能也比较简单,就是通过正则表达式将特殊标记字符以及后续的若干个空格,合并为一个特殊标记字符:java String word "java - 阿里"; word word.replaceAll("-\\s+", "-");然后将关键字进行空格切分,根据是否有特殊标记字符进行逻辑处理即可:java String[] ws word.split(" "); for (int i 0; i -1) { //这里是其它搜索模块的标记,标记邮箱 if (w.startsWith("@")) { wb.setEmail(w.substring(1)); } else { wb.setEmail(w); } } else if (w.indexOf("!") -1) { //标记手机号 if (w.startsWith("!")) { wb.setPhone(w.substring(1)); } else { int i1 w.indexOf("!"); String temp w.substring(0, i1); wb.addToWord(temp); wb.setPhone(w.substring(i1 + 1)); } } else { wb.addToWord(w); } }最后将关键字解析之后的结果拼接成solr支持的查询条件即可:javascript positiontitle:"java" AND NOT companyname:"阿里" 简单词性识别这块的需求相对来说应用场景会比较多,而且实现起来比前面两个场景会稍微复杂一些。我的思路就是:1. 当关键字出现地点(招聘场景)、分类(电商场景)、品牌(电商场景)、公司名(招聘场景)等词汇的时候,用户希望命中的是特定字段而不是全文。2. 搜索引擎在索引阶段建立倒排索引的时候,通过分词器快速的获得分词是否出现以及出现位置等关键信息。那么我也可以通过这个思路,从关键字中分词出是否出现以上类型的关键字,然后将其筛选出来做后续处理。3. 根据不同的细分情况,来决定特殊关键字筛选出来之后,需不需要在原关键字中将其保留。针对上述的需求和思路,我写了一个相对简单的关键字预处理模块,大致的功能如下: 无限制分词这个就比较简单了,只要在建立分词字典树的时候给分词标记地点属性即可。然后在筛选出地点关键字的时候,将其从原关键字删除,最后将地点关键字拼接到地点筛选字段上。搜索“java 上海”,拼接的查询语句如下:javascript positiontitle:"java" AND areaname:"上海" 闭区间分词当用户输入“58”、“360”等关键字的时候,希望筛选出五八同城或者奇虎360两家雇主的职位。但是输入“15820”或者“13604”时,只希望出来职位ID的职位。或许我们可以这么做,将输入进行判断,如果是数字且是58,则搜索五八同城职位。360同理。但是用户输入“58 java”的时候,你觉得用户想查询的是什么职位呢?很显然,更符合常理的是返回五八同城在招的java职位,但是不能直接用数字判断法了。所以我们的关键字分析模块必须能区分“15820”与“58 java”(或者“java 58”)两个关键字中“58”的上下文关系。为此,我定义了一个概念叫闭区间,“58”就是一个闭区间配置。何谓闭区间?就是关键字左右两边只能是无字符和空格这两个情况。通过[58]来配置,然后在建立字典树节点的时候记录该信息,并标记其转换后的值是雇主ID。javascript[58] $COMPANY:29008上面这个配置的含义就是,当用户输入的58属于闭区间(“58 java”)匹配时,会将其识别出来,然后删除其在原关键字的内容,在拼接查询语句的时候将其映射到雇主ID为29008的职位上:javascript positiontitle:"java" AND companyid:29008 半开闭分词再来看下前面提到过的场景输入“包”,希望搜索出分类是包的商品,而不是那种“xxxx[包邮]”或者“xxxx上衣,与xx背包更配”这种。我们通过上面两种“无限制分词”或“闭区间分词”都可以完成这个功能,只要简单的将包映射到其分类即可。但是当用户输入“背包”的时候,是不会定位到包这个分类下的。那么就可能搜索出“秋季薄呢子大衣,与双击背包更搭配”这类商品,实际上是个上衣分类。如果你有类似的场景需求,那么可以考虑用半开闭区间的转换设置。javascript包] $CATEGORY:100101这个配置的含义是关键字“包”后面没有字符或者紧跟的是空格的时候,会将其认为是搜索分类“包”,然定位到分类下进行搜索。这显然是一个更符合多数人的场景需求。这时候你输入“黄色 手提包”,预处理模块会将“黄色”定位到颜色,“手提包”定位到包,这时候可以在原关键字删除“黄色”保留“手提包”(这个看具体需求场景):javascript productname:"手提包" AND productcolor:"黄色" AND category:100101 其它功能这个关键字转换模块,除了配置以“$”开头的特殊转换之外,还可以配置正常的关键字转换。例如我们的职位命名中,“高级”和“工程师”直接往往会有很多修饰词,而用户喜欢输入“高级工程师”而不是“高级 工程师”,那么我就增加一条配置高级工程师 高级 工程师,该模块就会修改用户的输入。再扩展一下就是敏感词过滤功能:+ 将敏感词词库加载在字典树的时候,将转换之后的关键字统一改为“\\”,那么通过这个模块之后,整个文本中的敏感词都将变为星号。+ 还可以通过模块是否识别了字典树中定义的敏感词,来判断输入是否有敏感词。在词库量很大的情况下,这种基于字典树的分词方式性能上会比KMP或者正则高很多很多。 -------- 代码实现这里只给出了部分源代码,重点是说明我实现该功能时的思路。最主要的是,当时代码写的比较随便,注释也很少,结构也相对混乱,所以就忽略了一些代码。等什么时候有时间重写了,会重新贴出来。 字典树节点Node主要是维护分词转换的配置。当该节点可以成词的时候,储存了当初的配置信息,包括源关键字、目标关键字、是否保留、转换设置类型等。javapublic class Node { //当前字符 private Character selfChar; //允许的下一个词的集合 private Map subNodes new HashMap(16, 0.95f); //是否词尾;true的时候,会有后续一系列信息 private boolean allowEnd false; //当前词保存的关键字 private String word; //其他转换条件 private List others new ArrayList(); private Set othersFilter new HashSet(); //用于去重复,不要重复添加 //是否在源关键字保留,false:不保留 private boolean isKeep false; public boolean hasOthers(int index) { return others.size() index; } public void addOthers(String word) { if(StringUtils.isNotBlank(word) && !othersFilter.contains(word)) { others.add(word); othersFilter.add(word); } } public String getOther(int index) { return others.get(index); } public List cloneOthers() { List rs new ArrayList(); if(hasOthers(0)) { for(String s : others) { rs.add(s); } } return rs; } / 是否允许未到词尾即可提取 true : 不可以从“包邮”中提取“包”,只能从“包 红色”中提取“包” false : 可以从“包邮”中提取“包” / private boolean noNext false; //同理noNext private boolean noPrev false; public Node() { } public Node(Character ch) { this.selfChar ch; } public Node push(Character ch) { if(subNodes.get(ch) null) { subNodes.put(ch, new Node(ch)); } return subNodes.get(ch); } //省略了一些getter、setter} 转换处理器ConvertorHanlder转换器接口:javapublic interface IConvertorHandler { / 转换器核心方法; @param old 原始关键字命中分词部分 @param word 目标设置,转换后的字符串 @param qwr 结果存储对象;意味着该方法有副作用 / public boolean deal(String old, String word, QueryWordConvertResult qwr); //转换器ID public String ID(); //是否保留原始关键字;true表示保留 public boolean isReserved();}转换器抽象类:java//主要是处理$开头的那类转换public abstract class AbstractHandler { //正则对应关键字长度;比如$COMPANY中COMPANY长度就是7 protected int regLen 0; //正则匹配 protected String regex; protected String handlerId; public AbstractHandler() { } //是否终止处理 public abstract boolean isReturn(String word);}默认转换器:javapublic class DefaultHandler extends AbstractHandler { //用于初始化转换器相关设置 public DefaultHandler(String defaultRegex, String id) { regLen defaultRegex.length() + 2; regex "^\\$" + defaultRegex + "\\:."; handlerId id; } //对应的终止逻辑 public boolean isReturn(String word) { if(word null word.isEmpty()) { return true; } return false; }}实现一个地点转换器:javapublic class AddressHandler extends DefaultHandler implements IConvertorHandler { //初始化转换器对应的正则配置 public AddressHandler() { super("ADDRESS", "address"); } public boolean deal(String old, String word, QueryWordConvertResult qwr) { //不处理的情况 if(isReturn(word)) { return false; } //word配置了地点转换,则进入计算 if(Pattern.matches(regex, word)) { ParamBean pb new ParamBean(); //ADDRESS之后的就是目标关键字 pb.setCode(word.substring(regLen)); //保留原始关键字 pb.setWord(old); qwr.getCitys().add(pb); return true; } return false; } public String ID() { return handlerId; } //这里设置了,不在原关键字中保留命中的地点 public boolean isReserved() { return false; }} 分词器Analyzer持有字典树根节点和一系列转换器。负责字典树的创建和加载,转换器初始化(遇到相同关键字的转换时,可能会有优先级关系)。javapublic class Analyzer { //字典树根节点 private Node root; //转换处理器 private List handlers; private Set handlerIds; private IConvertorHandler matcher; private static IConvertorHandler NULLHANDLER new NullHandler(); public Analyzer() { root new Node();// loadExternalWord("-", "-"); handlers new ArrayList(2); handlerIds new HashSet(2); initHandlers(); } //初始化处理器 public void initHandlers() { loadIConvertorHandler(new CategoryHandler()); loadIConvertorHandler(new CompanyHandler()); loadIConvertorHandler(new AddressHandler()); loadIConvertorHandler(new SchoolHandler2()); loadIConvertorHandler(new GenderHandler()); loadIConvertorHandler(new DegreeHandler()); } public void loadIConvertorHandler(IConvertorHandler handler) { if(!handlerIds.contains(handler.ID())) { handlers.add(handler); handlerIds.add(handler.ID()); } } //对于某个命中的分词,进行全部处理器的顺序处理 public boolean handleAll(String old, String word, QueryWordConvertResult qwr) { for(IConvertorHandler h : handlers) { //目前设置的是,遇到第一个处理成功的处理器,就直接跳出;忽略后续的处理器 if(h.deal(old, word, qwr)) { matcher h; return true; } } matcher NULLHANDLER; return false; } public void loadExternal(String word) { String sameWord word.split(":")[1]; word word.split(":")[0]; loadExternalWord(word, sameWord); } public void loadExternalWord(String word, String sameWord) { if(word null sameWord null) { return; } //统一小写处理 word word.toLowerCase(); Node temp null; temp root; boolean noNext false, noPrev false; for(int i 0; i 1) { temp.addOthers(v); } else { //第一个关键词作为默认的目标词 temp.setWord(v); } } } } //处理关键字,返回处理结果 public QueryWordConvertResult replace(String test, boolean isMax) { if(StringUtils.isBlank(test)) { return new QueryWordConvertResult(); } test test.trim().toLowerCase(); int index 0; int len test.length(); QueryWordConvertResult qrs new QueryWordConvertResult(); //匹配词库单字过程中,当前匹配点 Node current null; List tas new ArrayList(); boolean hasNext true; boolean hasPrev true; int wordFirstIndex 0; StringBuilder sb new StringBuilder(""); while(index len - 1) { subIndex ++; break; } } if(canBeWordEnd && isMax) { tas.add(new TestAna(sb.toString(), null, hasPrev, hasNext)); sb new StringBuilder(""); hasPrev hasPrev(test, wordFirstIndex); hasNext hasNext(test, subIndex - 1); tas.add(new TestAna(temp, lastNotNull, hasPrev, hasNext)); } if(!canBeWordEnd) { sb.append(temp); } index subIndex; } if(sb.length() 0) { tas.add(new TestAna(sb.toString(), null, false, false)); sb new StringBuilder(""); } StringBuilder afterReplace new StringBuilder(""); for(TestAna ta : tas) { if(ta.getNode() null) { afterReplace.append(ta.getSrc()); } else { Node n ta.getNode(); //字典树节点的开闭设置 boolean rulePrev n.isNoPrev(), ruleNext n.isNoNext(); //转换器规定,是否允许前置,后置]表示不允许后置;[表示不允许前置 //A:当设置了不允许后置,才检查TestAna是否有后续关键字,两者不一致,则continue //B:当设置了不允许前置,才检查TestAna是否有前置关键字,两者不一致,则continue //A B 有一者定义了,但是不满足,则conitnue if((rulePrev && ta.isHasPrev()) (ruleNext && ta.isHasNext())) { afterReplace.append(ta.getSrc()); continue; } String src ta.getSrc(); List all n.cloneOthers(); all.add(n.getWord()); for(String s : all) { //保留原始关键字 if(handleAll(src, s, qrs) && matcher.isReserved()) { afterReplace.append("" + src); } else if(matcher.isReserved()){ afterReplace.append(" " + s); } } } } qrs.setNewWord(afterReplace.toString()); return qrs; } //前面是否还有空格之外的其它字符 public boolean hasPrev(String text, int index) { if(index text.length() - 1) { return false; } if(text.charAt(index + 1) ' ') { return false; } return true; }}Analyzer这个类出现的比较早,目前还没有优化过代码,因此看起来比较乱,后续有时间会重写这个处理类。---

    Solr   Java   分词   字典树   搜索引擎   2019-07-24 浏览(305) 有用(0) 阅读原文>> [原创]
  • 搜索引擎进阶——IK扩展之动态加载与同义词   

    前言 IKAnalyzer是一个开源的,基于java语言开发的轻量级的中文分词工具包。他最初是由林良益老师团队开发并维护的。 IK对应Lucene版本为4.7.2,其实IK针对不同版本的Lucene可以进行定制化的修改以达到适用的目的。 词库动态加载的关键类是org.apache.lucene.analysis.Tokenizer和org.apache.lucene.analysis.util.TokenizerFactory。 同义词扩展的关键类是org.apache.lucene.analysis.synonym.SynonymFilter和org.apache.lucene.analysis.util.TokenFilterFactory。---![图片](https://www.oomabc.com/staticsrc/img/201809/14/1536859583364974be33e584945cf80c52e29ab816a99.jpg) -------- 必要信息解释Term是一个最小搜索单元,Lucene中有个Term和对应的TermQuery;Token应该是分词过程中记录一些分词信息的对象。 然后我特意下载lucene-core-4.7.1进行查看,看到Token这类上面是这么写的:![图片](https://www.oomabc.com/staticsrc/img/201809/14/1536859689260271527901b7f487e83cd4bed7aa909bf.jpg) 我用非常蹩脚的英语水平,大致翻译一下主要内容就是:Token是一种在对文本进行分词时产生的对象,包含分词对象(Term)的词语内容,词语在文本中的开始、结束位置,和一个词语类型(关键字、停用词)字符串。开始、结束位置这两个参数,可以在做文本高亮或者摘要高亮的时候使用。从Lucene的2.9版本开始,Token这个类就不再建议使用了,推荐用Attuibutes这个接口对应的实现类代替。新版本取得分词信息方式如下:javaAnalyzer analyzer new StandardAnalyzer(Version.LUCENE47);String text "利用 Lucene 进行搜索就像建立索引一样也是非常方便的。";TokenStream tokenStream analyzer.tokenStream("keyword", text);tokenStream.reset();while(tokenStream.incrementToken()) { CharTermAttribute charTermAttribute tokenStream.getAttribute(CharTermAttribute.class); System.out.println(charTermAttribute.toString());}至于Term,源码是这样注释的:![图片](https://www.oomabc.com/staticsrc/img/201809/14/1536859763338b92ddbf18f794ef1bdff1b414aad8ac2.jpg) Term表示文本中的一个词语,是搜索的最小单元。它有两个元素组成:词语的内容和文本所在的域。Term不仅仅表示字符串词语,还可以代表日期型值、邮箱地址、URL。对于Lucene这全文检索工具包来说,每次查询都需要制定一个域(Field),因此: Term就是一个包含制定Field和目标词语的一个对象。Term query new Term("keyword", "Lucene");这个Term(query)就是表示需要查询在“keyword”这个字段(Field)中出现过“Lucene”这个词语的文档。 Token是一个在分词过程中产生的对象。Tokenizers and TokenFilters should try to re-use a Token instance when possible for best performance。对于词语“Token ”,对应的Token对象就包含了这个词语的自身内容,在这句话中的开始位置、结束位置以及一个可以储存其他信息的payload对象。--- 分词器扩展之词库动态加载solr分词器在配置文件schemal.xml中的配置标签是,因此它是org.apache.lucene.analysis.util.TokenizerFactory的派生类。IKTokenizerFactory是一个工厂类,需要重写父类的create方法来生成Tokenizer的派生类对象实例。前面介绍过,Token是分词过程产生的包含分词细节信息的一个最小单元,暂且称之为‘词元’。而TokenStream就是词元流,是一系列词元的集合,且是连续(sequence )、可枚举(enumerates)的。Tokenizer继承了TokenStream,可以将java.io.Reader以及派生类对象实例转为词元流,目的就是为了将词库文件进行分词,并得到连续的词元集。TokenStream还有一个重要的派生类TokenFilter,它的输入不是Reader,而是另一个TokenStream。根据Filter的后缀和其输入类型,我们就可以猜的,它是一个链式调用中用的对象。IK的IKTokenizer只是进一步继承了Tokenizer,为了将自己定义个一些分词组件集成到solr中。比如,IK分词器核心类IKSegmenter。这次词库动态加载的核心就是IKTokenizer的工厂方法类IKTokenizerFactory。当然,你可以自己重新写一个自己的Tokenizer工厂类和Tokenizer派生类,来实现这个词库动态加载功能。但是为了功能内聚以及一致性,我们将分词器的动态加载和更新放在了IKTokenizerFactory中,随着IKTokenizerFactory的初始化而第一次载入词库。词库的加载实现原理非常简单,通过调用IK提供的单例org.wltea.analyzer.dic.Dictionary中的方法即可。 Dictionary.getSingleton().disableWord(word)可以从词库中删除指定的分词定义。 Dictionary.getSingleton().addWord(word)提供的是增加分词功能。 我的代码示例,仅供参考:java //默认从启动时间10分钟之前的数据开始更新;以后,都是从上一次结束的时间开始更新 //这里将分词词典和同义词词典的分词定义都加载到了分词器中 //当时为了方便,直接通过记录更新时间和定时扫描的方式来更新词库内容,其实比较合理的做法就是触发式的,不会造成扫描任务的资源浪费,原因在后面会稍作解释 private static long dicUpdateTime System.currentTimeMillis() - 600000; private static long sameUpdateTime System.currentTimeMillis() - 600000; public void updateDic() { long minAddTime dicUpdateTime; DicKeywordDao dicKeywordDao new DicKeywordDao(); dicKeywordDao.setUpdateTime(minAddTime); dicUpdateTime dicKeywordDao.maxTime(minAddTime); if(dicUpdateTime minAddTime) { dicUpdateTime minAddTime + 1000; } System.out.println("update dic at : " + DateFormatUtil.formatLong(minAddTime) + ", next time at : " + DateFormatUtil.formatLong(dicUpdateTime)); //遍历符合条件的所有分词关键字定义 while(dicKeywordDao.hasNext()) { List list dicKeywordDao.more(); if(list ! null) { for(DicKeyword k : list) { String w k.getKeyword(); if(k.getIsDic() -1) {//删除分词 System.out.println("\tdelete word : " + w); Dictionary.getSingleton().disableWord(w); } else {//加载新的分词,已存在的分词不会影响最终结果 System.out.println("\tadd word : " + w); Dictionary.getSingleton().addWord(w); } } } } minAddTime sameUpdateTime; //加载同义词词库 SameWordDao sameWordDao new SameWordDao(); sameWordDao.setUpdateTime(minAddTime); sameUpdateTime sameWordDao.maxTime(minAddTime); if(sameUpdateTime minAddTime) { sameUpdateTime minAddTime + 1000; } while(sameWordDao.hasNext()) { List words sameWordDao.more(); if(words ! null && words.size() 0) { for(SameWord w : words) { loadWord(w); } } } } / 重载分词词库 / private void reLoadDic() { Dictionary.reload(DefaultConfig.getInstance()); DicKeywordDao dicKeywordDao new DicKeywordDao(); dicUpdateTime dicKeywordDao.maxTime(-1); while(dicKeywordDao.hasNext()) { List list dicKeywordDao.more(); if(list ! null) { for(DicKeyword k : list) { String w k.getKeyword(); if(k.getIsDic() -1) { Dictionary.getSingleton().disableWord(w); } else { Dictionary.getSingleton().addWord(w); } } } } //动态数据库加载 SameWordDao sameWordDao new SameWordDao(); sameUpdateTime sameWordDao.maxTime(-1); while(sameWordDao.hasNext()) { List words sameWordDao.more(); if(words ! null && words.size() 0) { for(SameWord w : words) { loadWord(w); } } } } //加载同义词;同义词是一组词,多个同义词会用英文逗号隔开存储在数据中,在下个段落会介绍 private void loadWord(SameWord w) { String[] kws w.getKeyword(); for(String kw : kws) { if(StringUtils.isNotBlank(kw) && kw.length() 1) { Dictionary.getSingleton().addWord(kw); } } } 关于词库加载和分词过程的同步问题Dictionary类中有一个DictSegment的实例,它是分词器的字典树。由于Dictionary是单例,因此它持有的DictSegment实例对象(字典树根节点,所有分词匹配过程都是从根节点开始)也是间接的单例。词库加载和删除实际都调用了DictSegment的方法:java / 加载填充词典片段 @param charArray 词典输入的字符数组 @param begin 下一个分词扫描字符的开始位置 @param length 下一个分词扫描字符的长度 @param enabled 1:表示有效分词;0:表示删除分词 / private synchronized void fillSegment(char[] charArray , int begin , int length , int enabled){ //获取字典表中的汉字对象 Character beginChar new Character(charArray[begin]); /Character keyChar charMap.get(beginChar); //字典中没有该字,则将其添加入字典 if(keyChar null){ charMap.put(beginChar, beginChar); keyChar beginChar; }/ //搜索当前节点的存储,查询对应keyChar的keyChar,如果没有则创建 DictSegment ds lookforSegment(beginChar , enabled); if(ds ! null){ //处理keyChar对应的segment if(length 1){ //词元还没有完全加入词典树 ds.fillSegment(charArray, begin + 1, length - 1 , enabled); }else if (length 1){ //已经是词元的最后一个char,设置当前节点状态为enabled, //enabled1表明一个完整的词,enabled0表示从词典中屏蔽当前词 ds.nodeState enabled; } } }这个方法使用了线程同步关键字synchronized,同时方法中进行子字符扫描时调用的两个方法内部也都有方法快同步。所以频繁的更新词库,会影响不同的索引线程和查询线程对同一个DictSegment实例对象的访问,从而影响性能。然后再加一个定时器进行扫描即可:java //初始化构造器 public IKTokenizerFactory(Map args) { super(args); assureMatchVersion(); useSmart getBoolean(args, "useSmart", false); dicPath get(args, "dicPath"); synchronized (isThreadStart) { if(!isThreadStart) { isThreadStart true; ScheduledExecutorService executor Executors.newScheduledThreadPool(4); executor.scheduleWithFixedDelay(new Runnable() { public void run() { updateDic(); } }, DICUPDATESECONDS, DICUPDATESECONDS, TimeUnit.SECONDS); executor.scheduleWithFixedDelay(new Runnable() { public void run() { reLoadDic(); } }, 0, DICRELOADHOUR, TimeUnit.HOURS); } } }--- 分词器扩展之同义词扩展 搜索引擎在商业应用中,经常会碰的的问题就是查全率低。一方面是互联网社会,新词产生速度比以往任何时候都快,另一方面是垂直领域的分词器的缺乏。 我目前所在的招聘行业,职位搜索是非常常用的功能。例如搜索关键字“阿里”,没问题,我可以用这个关键字去搜索职位对于的企业名称或者职位标题,基本可以得到满意的查全率。例如搜索关键字“上海”、“北京”,可以用关键字去搜索职位工作地点或者职位标题,也可以得到不错的查全率。 但是,问题来了,如果用户搜索关键字“BAT”呢?你可以这样做,对所有“阿里”、“腾讯”、“百度”的职位建立索引的时候,增加BAT标签,虽然这么做有点麻烦,但是搜索“BAT”的确可以搜索到对应的结果了。 但是,我搜索“一线城市”呢?你也可以向上面一样来实现这个功能,但是是不是有点麻烦,后面我要搜索“一线互联网”呢?搜索“ATM”呢?搜索“alibaba”呢?搜索“tencent”呢?总不能每次都加一个标签,然后重建索引吧。既然,重建索引不现实,那么我们就在Query阶段实现同义词的扩展。这里我们定义同义词的格式如下:1. “阿里”,“alibaba”是一组同义词,表示“阿里”和“alibaba”两个关键词在各自搜索时,每次都返回两个词的结果并集。2. “BAT”,“阿里腾讯百度”是一组同义词,表示搜索“BAT”的时候会返回“BAT”、“阿里”、“腾讯”和“百度”四个关键词结果的并集;但是单独搜索“阿里”、“腾讯”和“百度”三个关键词中的任意一个,都不会返回另外两个的结果或者“BAT”的结果,除非你配置了其他同义词组。 接下来就是同义词在IK分词器中的实现了由于同义词是发生在实际分词器工作结束之后,query执行之前,是属于对TokenStream的二次加工。前面我们了解了TokenFilter的输入正是TokenStream,因此同义词扩展类就是TokenFilter的派生类SynonymFilter,它是Lucene原生支持的。IK通过继承TokenFilter的工厂类TokenFilterFactory,来进行对SynonymFilter对象实例的操作,从而实现同义词自定义扩展和更新。这个工厂类就是org.wltea.analyzer.lucene.IKSynonymFilterFactory。我会直接给出这个类扩展之后的源码,然后在注释中对关键点进行解释。javapublic class IKSynonymFilterFactory extends TokenFilterFactory implements ResourceLoaderAware { //构造函数,args定义的是schema.xml中配置的参数 public IKSynonymFilterFactory(Map args) throws IOException { super(args); expand getBoolean(args, "expand", true); // synonyms get(args, "synonyms"); ignoreCase getBoolean(args, "ignoreCase", false); isAutoUpdate getBoolean(args, "autoupdate", false); isAutoUpdate false; } // 这是整个扩展的核心,维护一个同义词扩展的关系映射对象 private static SynonymMap map; private boolean ignoreCase; private boolean expand; boolean isAutoUpdate; Analyzer analyzer null; // 包访问权限,共用 private static Boolean isUpdateStart false; private long RELOADSECONDS PropertieUtil.getLongProp("resource", "synReloadSeconds"); //实现了org.apache.lucene.analysis.util.ResourceLoaderAware提供的接口,目的是为了让solr在加载类的时候,通过org.apache.lucene.analysis.util.ResourceLoader对象来加载该工厂类 public void inform(ResourceLoader loader) throws IOException { // IKAnalyzer analyzer new IKAnalyzer(); // max words final Analyzer analyzer new Analyzer() { @Override protected TokenStreamComponents createComponents(String fieldName, Reader reader) { WhitespaceTokenizer tokenizer new WhitespaceTokenizer(Version.LUCENE47, reader); @SuppressWarnings("resource") TokenStream stream ignoreCase ? new LowerCaseFilter(Version.LUCENE47, tokenizer) : tokenizer; return new TokenStreamComponents(tokenizer, stream); } }; this.analyzer analyzer; try { //初始化同义词内存对象 map loadSolrSynonyms(true, analyzer); synchronized (isUpdateStart) { if (!isUpdateStart) { isUpdateStart true; //启动一个线程,定时加载同义词词库内容 ScheduledExecutorService executor Executors.newScheduledThreadPool(4); executor.scheduleWithFixedDelay(new Runnable() { public void run() { try { map loadSolrSynonyms(true, analyzer); } catch (IOException e) { e.printStackTrace(); } catch (ParseException e) { e.printStackTrace(); } } }, RELOADSECONDS, RELOADSECONDS, TimeUnit.SECONDS); } } } catch (ParseException e) { e.printStackTrace(); throw new IOException("Exception thrown while loading synonyms", e); } } / 加载同义词词典 @param loader @param dedup @param analyzer @return @throws IOException @throws ParseException / private SynonymMap loadSolrSynonyms(boolean dedup, Analyzer analyzer) throws IOException, ParseException { // 不需要同义词词典,直接数据库加载 / dedup:是否可以重复加载;true表示不能重复加载 expand:表示是否是同级别定义; true就是上面定义的1; false就是带方向的定义,类似定义2。不过方向需要自己实现,默认是逗号隔开的多个关键词,第一个是主关键词,所有关键词都会映射到第一个,但是第一个只会映射到自己。 / SolrSynonymParser parser new SolrSynonymParser(dedup, expand, analyzer); if (isUpdateStart) { // 动态数据库加载 SameWordDao sameWordDao new SameWordDao(); while (sameWordDao.hasNext()) { List words sameWordDao.more(); if (words ! null && words.size() 0) { for (SameWord w : words) { addSynWord(parser, w.getKeyword()); } } } } return parser.build(); } @Override public TokenStream create(TokenStream input) { if (map.fst null) { return input; } else { //重新创建实例对象,以便获得最新的同义词结果; //上层可以设置缓存时间,以提高性能 return new SynonymFilter(input, map, ignoreCase); } } public static Boolean isUpdate false; private void addSynWord(SolrSynonymParser parser, String[] list) throws IOException { if (list null list.length left new ArrayList(); List right new ArrayList(); //循环同义词定义,加载同义词 //参考:org.apache.lucene.analysis.synonym.SolrSynonymParser.SolrSynonymParser(boolean, boolean, Analyzer) //参考:org.apache.lucene.analysis.synonym.SynonymMap for (String w : list) { if (StringUtils.isBlank(w) w.length() 0 w.split("").length 1) { w w.toLowerCase(); //分割字符串之后,并放入同义词输出对象集合中,相当于expandfalse List temp getCharsRef(w); if (temp ! null) { right.addAll(temp); } } else { w w.toLowerCase(); // CharsRef temp SynonymMap.Builder.analyze(analyzer, unescape(w).trim(), new CharsRef()); CharsRef temp new CharsRef(unescape(w).trim()); //如果单纯是关键词,则同步加入输入和输出集合 //相当于expandtrue left.add(temp); right.add(temp); } } //循环配置同义词输入输出关系 for (CharsRef l : left) { for (CharsRef r : right) { parser.add(l, r, false); } } } //处理自定义格式的同义词配置 private List getCharsRef(String word) { List rs new ArrayList(); String[] wds word.split(""); for (int i 0; i 0) { StringBuilder sb new StringBuilder(); for (int i 0; i s.length(); i++) { char ch s.charAt(i); if (ch '\\' && i s.length() - 1) { sb.append(s.charAt(++i)); } else { sb.append(ch); } } return sb.toString(); } return s; }}以上就是我在使用solr和IK时,为了实现某些功能而做的一些扩展,仅供大家参考。如果有误,纯属意外!

    搜索引擎   IK   分词器扩展   Solr   Java   2019-07-24 浏览(3760) 有用(0) 阅读原文>> [原创]
  • 搜索引擎进阶——Lucene链表操作解析   

    说到搜索引擎,大家都不会陌生,尤其是互联网从业者更是如此。而大部分程序员都能对其基本原理说个七七八八,比如分词、倒排链表、空间向量模型、余弦定理、Top-N......。而且对于全文检索的两个过程索引和查询也都知道个大概。+ 索引:对数据进行分词,然后按照分词结果生成倒排链表(包含词频、位置等信息),最后生成索引文件。+ 查询:对查询语句进行分词,综合其他查询条件生成查询树并优化;对查询树进行倒排链表匹配,将匹配到的链表按照查询语义进行操作(交集、并集、差集等);最后按照打分规则进行排序并分页返回结果。当然真正的实现细节会复杂许多,比如数据结构、数据类型定义、索引存储、数据压缩、相关链表操作算法、跳跃表、打分模型、内存索引切换等等,都是需要考虑的地方。 链表操作前面介绍的那些内容中,有一个是非常重要而且相对来说比较容易看懂和说明白的就是链表操作。何为链表操作?每个Term后面都挂有一个链表,链表的元素主要包含的内容有元素的DocId(这是Lucene给每个文档的自增编号)、Frequency(这是分词在对应文档中出现的频率)。实际上,每个链表元素就对应一篇当初索引的文档,所以链表操作就是对这些文档进行交集、差集、并集的操作。例,有如下几篇文档: A:机器学习最通俗的解释就是让机器学会决策。 B:支持向量机(SVM)是90年代中期发展起来的基于统计学习理论的一种机器学习方法。 C:随机森林的基本单元是决策树。 D:分类和回归是机器学习解决的两大主要问题。 E:古典决策理论盛行于20世纪初到50年代期间。 F:分类树(决策树)是一种十分常用的分类方法,是一种有监督的机器学习方法。现在我们只考虑其中几个分词,而且暂时忽略分词的歧义性,那么简易版倒排链表就是: 机器学习:A B D F 决策:A C E F 此时,我们搜索机器学习,通过倒排链表就马上知道其结果是A B D F。搜索决策得到的结果就是A C E F。搜索机器学习和决策,得到的就是两个链表的交集A F。搜索机器学习或者决策,结果就是链表并集,A B C D E F。搜索机器学习但是不要决策,则结果就是差集,B D。 Lucene中的实现上文中提到,链表元素中有一个是DocId,它是Lucene提供的内置的自增ID,因此是一个有序的链表。基于此前提,Lucene提供了一个底层的链表操作接口,这里是一个abstract类——DocIdSetIterator。他提供的重要的接口:+ abstract int docID():返回链表当前指针指向的元素的DocId。 特别地,如果未调用过nextDoc()和advance(int target)方法,则返回-1。如果指针已经超出链表范围,则返回内置常量NOMOREDOCS(Integer.MAXVALUE)。+ abstract int nextDoc() throws IOException:链表指针向后移动一个元素并返回元素的DocID,同样的,如果链表的当前指针没有下一个元素,则返回NOMOREDOCS。+ abstract int advance(int target) throws IOException:将链表指针指向到下一个大于等于指定的DocId的元素上。如果target比当前元素的DocId小,则不进行任何操作,同样的,没有更多元素的时候会返回NOMOREDOCS。本文章将要介绍的,就是针对上面定义的元素进行的链表操作。为了更清晰的进行叙述,部分代码进行简化和重新编写,并增加中文注释,其核心思路和Lucene基本一致。 链表接口链表类和链表元素类都将实现这个接口,这样的好处就是,链表和元素都可以看做是相同的元素,可以迭代操作:javapublic interface IDataArray { / 空数据 / public static final Long NOMOREDATA Long.MAXVALUE; / 计算下一个符合条件的文档,即数值型主键 / public long nextDoc(); / 当前指针指向的元素对应的值 / public long dataID(); / 数值跳跃,跳跃到大于等于指定数值(dataID)的数值,并返回 @param dataID 指定数值 / public long advance(long dataID);} -------- 交集操作 DataConjunction顾名思义就是,求若干个(N)链表中都出现过的元素集合。主要是定义一个类,实现IDataArray接口,其算法主要有以下几个步骤:1. 定义一个IDataArray类型的数组,存放所有需要求交集的链表;按照链表的dataID()方法返回值由小到大排序2. 定义一个lastData,代表交集操作的某一次返回值。是执行nextDoc()或者advance()方法之后的值,通过dataID()方法返回。3. 对象中有方法,advance(int i),可以将doc跳到大于等于i的值4. nextDoc()方法,将doc后移要点:所以,我们定义的交集操作类在初始化的时候要保证两点:每个链表的指针要指向第一个元素,链表数组要按照各自链表的第一个元素升序排列。javapublic class DataConjunction implements IDataArray { //存放需要进行交集操作的各个链表 private IDataArray[] arrays; //默认值-1,当前结果元素 private long lastData -1; / 构造函数,将待处理链表(数组)传入 / public DataConjunction(IDataArray[] arrays) { this.arrays arrays; //数组长度大于1才需要进行处理 if(arrays.length 1) { for(IDataArray array : arrays) { //初始化每个链表的指针位置,使之指向表头,否则就终止 if(array.nextDoc() NOMOREDATA) { lastData NOMOREDATA; return; } } //将数组,按照链表的第一个数值,从小到大排列 Arrays.sort(arrays, new Comparator() { @Override public int compare(IDataArray o1, IDataArray o2) { if(o1.dataID() o2.dataID()) { return 0; } if(o1.dataID() o2.dataID()) { return 1; } else { return -1; } } }); //获取第一个符合条件的数值 if(doNext() NOMOREDATA) { lastData NOMOREDATA; return; } } } @Override public long dataID() { return lastData; } @Override public long advance(long dataID) { //内部调用计算 while(nextDoc() ! NOMOREDATA) { if(lastData dataID) { return lastData; } } return NOMOREDATA; }}上面代码中,提到了一个方法doNext(),它是真正执行nextDoc()操作的方法,目的是找到下一个符合要求(交集)的元素,并用lastData保留该元素的dataID()返回值。下面我们来看下doNext()方法的具体内容:java/ 执行一次计算 /private long doNext() { int first 0; //最后一个元素的第一个数 long doc arrays[arrays.length - 1].dataID(); IDataArray firstArray; / 循环结束的条件 1、有一个元素的链表结束,即返回 NOMOREDATA 2、firstArray的dataID doc ? 元素按照链表第一个元素,升序排列 / while((firstArray arrays[first]).dataID() doc的情况会不会出现?3. 循环终止之后,如何保证doc是交集结果? 为什么将最后一个链表的指针元素值,作为doc初始值?从上面的要点说明中可知,arrays本身是按照每个链表的dataID()来升序排列的,因此如果在为移动链表指针的情况下,第一个可能的交集结果,一定是最后一个链表的dataID()返回值,因为它前面链表的dataID()返回值都小于或者等于它,小于的当然不可能是交集结果。 while的终止条件为什么只有小于由于我们对arrays本身的约定,因此firstArray.dataID()一定不小于后续遍历的dataID(),而在循环体里面执行了doc firstArray.advance(doc),所以doc当前值,一定是大于或者等于下一个遍历链表的dataID()。也就是,每次的while条件中,(firstArray arrays[first]).dataID()总是小于等于doc,所以,不可能出现大于的情况。所以,循环终止的条件就是等于,也就是找到了某一个交集结果。 循环终止之后,如何保证doc是交集结果我们每次循环都是从当前数组的最后一个链表开始,记为tail(这里的tail可以不是实际上的最后一个链表,严格的说是当前doc值最后一次变动的链表)。在遍历终止的时候,终止的那个链表记为break,此时它的上一个链表就是tail,而且tail.dataID() break.dataID()。特别要注意的是,此时的break链表是没有经过advance()操作的,因为它压根没进入循环。break之后到tail之间的链表记为between[],则根据arrays的约定和advance()操作的原理可以确定,between[].dataID() break.dataID() && between[].dataID() 图文说明1、初始有7个链表![图片](https://oomabc.com/staticsrc/img/201903/19/15529811669211de2ecb2754045b88ed7f92a52888e43.jpg)2、初始化排序![图片](https://oomabc.com/staticsrc/img/201903/19/15529811888716fcbe1d9aceb45eeb92f2cb97db56ae4.jpg)3、初始化赋值data,也就是代码中的doc。初始 first 0, data 11,此时需要对 first 位置的链表进行advance操作,入下图,将 first 位置的链表的指针之下下一个不小于11的值,也就是11。![图片](https://oomabc.com/staticsrc/img/201903/19/1552981212458e1d6022356ce4a4e8379f044476de4b4.jpg)4、此时 first 1,data 11。发现 docID 返回值 1 小于 data,所以进行advance操作。first后移一位。![图片](https://oomabc.com/staticsrc/img/201903/19/1552981226518e74bff72da2140819c82fea52823cc7d.jpg)5、此时 first 2,data 11。发现 docID 为 1 小于 data, 所以进行advance操作,first 更新为3 。![图片](https://oomabc.com/staticsrc/img/201903/19/1552981239974d3fe28488a5140f894af9933f98cfdc2.jpg)6、first的值分别为3、4、5的操作都是一致的,这里略过。first 继续后移一位,此时first 6, data 11。此时docID 不小于 data,跳出循环。我们发现 first7 的链表就是当前data值的最初赋值的链表。此时first 6就是跳出循环的链表,它与first7的链表直接的dataID返回都是11,实际上这里并没有中间链表。那么,data 11,就是我们的第一个交集结果,此时通过dataID()就可以获取该值。![图片](https://oomabc.com/staticsrc/img/201903/19/15529812522334b00a8fc28f548f2b92171ee400fa01c.jpg)7、后续的操作就是重复上面的步骤即可,直到某一个链表返回NOMOREDATA。 -------- 并集操作 DataDisjunction并集,顾名思义就是在任何一个链表中出现过的元素就算结果集中的一员。只不过,这里增加了一个参数,最小满足链表数minMatchNum。当minMatchNum 1的时候,就是传统意义的并集,如果minMatchNum 1,就是查询条件OR的时候,至少要满足几个条件的场景。在交集操作介绍中,我们定义数组来存储参与计算的链表,本节并集操作定义了一个二叉堆来存储各个链表,来提示操作的性能。关于二叉堆,之前的文章有详细的介绍[《应用算法学习(一)—— TopN算法》](https://oomabc.com/articledetail?atclid362126dec078413d8de2aa7493445529)。关于二叉堆的定义和特性以及相关通用操作就不再赘述。这里直接给出相关代码,并在新增的方法上加以说明。javapublic class DataQueue { //数组存储,模拟二叉堆,数据类型就是一开始定义的链表元素接口 private IDataArray[] items; //上限 private int maxSize; //当前大小 private int size; public DataQueue(int size) { if(size 1; //父节点位置 while(j 0 && node.dataID() 1; //迭代父节点的父节点,以此类推 } items[i] node; //要插入的数据放入合适位置 } public void downHeap(){ int i 1; / 刚插入的数据,分别和它的两个子元素比较 / IDataArray node items[i]; // 第一个元素,也就是刚插入的元素 int j i 如果堆顶元素的链表没有下一个元素,则从堆中弹出链表 然后将堆进行重排 / public final boolean topNextAndAdjustElsePop() { return size 0 && checkAdjustOrPop(items[1].nextDoc() ! IDataArray.NOMOREDATA); } public final boolean skipToAndAdjustElsePop(long data) { return size 0 && checkAdjustOrPop(items[1].advance(data) ! IDataArray.NOMOREDATA); } private boolean checkAdjustOrPop(boolean hasResult) { if(hasResult) { //有数据 } else { //pop items[1] items[size]; items[size] null; size --; } if(size 0) { downHeap(); } return hasResult; }}对应于交集操作有个doNext()方法,并集操作的advanceAfterCurrent()也是执行实际操作的方法,它负责寻找下一个满足并集要求的元素。它的执行思路是:1. 获取堆顶链表的当前元素值,作为备选值 currentData,定义 matchs 1,记录匹配的链表熟。2. 堆定链表指针后移,此时需要重新维护堆的特性,进行沉降动作。3. 判断最新的堆定链表的当前元素是否与currentData一致,不一致则跳到 4;一致,则 matchs ++ ,然后跳到 2。4. 判断 matchs minMatchNum,true则返回;否则判断堆中剩余元素数量是否不小于minMatchNum,小于则返回false,否则跳转到 1 。所以,方法返回true表示有结果,否则表示没有任何结果满足并集要求。 初始化javapublic class DataDisjunction implements IDataArray { //倒排链表最小堆 private DataQueue dataQueue; //并集最小满足数 private int minMatchNum 1; //当前值 private long currentData -1; public DataDisjunction(IDataArray[] arrays, int minMatchNum) { //构建一个指定大小的二叉堆排序对象 dataQueue new DataQueue(arrays.length); if(arrays.length 0) { for(IDataArray array : arrays) { if(array.nextDoc() ! NOMOREDATA) { //每个元素进行各自的下一个结果计算,并添加到二叉堆进行排序 dataQueue.insert(array); } } } this.minMatchNum minMatchNum; }} 实现接口java@Overridepublic long nextDoc() { //如果当前堆中的元素数量小于最小的要求满足数,或者没有更多的结果,则设置当前数值为没有结果 //advanceAfterCurrent方法中计算下一个结果 if(dataQueue.size() dataID) { return currentData; } } return NOMOREDATA;}/ 计算下一个符合条件的数值 /protected boolean advanceAfterCurrent() { do { currentData dataQueue.topArrayData();//获得堆顶元素的链表的当前数 int matchs 1; do { if(!dataQueue.topNextAndAdjustElsePop()) { if(dataQueue.size() 0) { break; } } //下一个堆顶元素的当前数值,不等于当前数值,则退出 if(dataQueue.topArrayData() ! currentData) { break; } matchs ++; } while(true); //计算得到符合要求的结果,返回true,结果储存在【currentData】 if(matchs minMatchNum) { //matchs,这里可以记录该数满足的链表数量,用于二次排序:按照满足链表数量排序 return true; } if(dataQueue.size() 图文说明1. 初始链表如下,二叉堆已经初始化完成,要求 minMatchNum 3,此时currentData 1, matchs 1![图片](https://oomabc.com/staticsrc/img/201903/19/1552981327086c7c5d7b3c0cb44c7911ed9e4ff5d77d3.jpg)2. 堆顶链表指针后移,调整堆,此时 currentData 不变, matchs 变为 2![图片](https://oomabc.com/staticsrc/img/201903/19/155298135399427972eec5cbc41d7b908b226e3d13da3.jpg)3. 堆顶链表指针后移,调整堆,此时 top.dataID ! currentData,而且matchs minMatchNum,所以return true。至此,一个完整的nextDoc()操作已经完成。![图片](https://oomabc.com/staticsrc/img/201903/19/1552981435801fb44212c976b45969ea5a511093a3905.jpg) -------- 差集操作链表的差值操作直接在代码中进行说明:javapublic class DataReqExclude implements IDataArray { //必须满足的 private IDataArray reqArray; //排除的链表 private IDataArray excludeArray; private long doc; public DataReqExclude(IDataArray reqArray, IDataArray excludeArray) { this.reqArray reqArray; this.excludeArray excludeArray; this.doc NOMOREDATA; if(this.excludeArray ! null) { this.excludeArray.nextDoc(); } } @Override public long nextDoc() { if(reqArray null) { return NOMOREDATA; } doc reqArray.nextDoc(); if(doc NOMOREDATA) { reqArray null; return doc; } if(excludeArray null) { return doc; } return doc toNonExcluded(); } @Override public long dataID() { return doc; } @Override public long advance(long dataID) { while(nextDoc() ! NOMOREDATA) { if(doc dataID) { return doc; } } return doc; } / 得到下一个不用排除的值,直到结束 @return / private long toNonExcluded() { //排除的数值 long exclData excludeArray.dataID(); //需要的数值 long reqData reqArray.dataID(); do{ // 1、需要的数值比排除的数值小,则直接返回需要数值 if(reqData exclData) { // 2、将排除数值,跳转到下一个大于等于 需要数值[reqData]的值 exclData excludeArray.advance(reqData); if(exclData NOMOREDATA) { // 3、如果没有排除数值,则返回需要数值 excludeArray null; return reqData; } // 4、跳转结束,需要数值小于排除数值,则说明需求值不用被排除,符合结果,返回需要数值 if(reqData 关于测试在测试的时候,我们还可以再定义两个类LongDataArray和IntegerDataArray,分别实现IDataArray接口。 并集测试因为我们的LongDataArray和IntegerDataArray以及并集、交集、差集操作类都是实现了同一个接口,因此可以嵌套测试。javapublic static void main(String[] args) { LongDataArray a1 new LongDataArray(new Long[]{2L, 5L, 9L, 6L, 11L, 17L, 15L, 22L, 209999999999L}); LongDataArray a2 new LongDataArray(new Long[]{5L, 22L, 20L, 209999999999L, 24L, 11L, 17L, 2L, 8L}); LongDataArray a3 new LongDataArray(new Long[]{1L, 4L, 209999999999L, 5L, 9L, 7L, 17L, 22L, 11L}); LongDataArray a4 new LongDataArray(new Long[]{11L, 17L, 15L, 5L, 22L, 25L, 30L, 209999999999L, 32L, 28L}); LongDataArray a5 new LongDataArray(new Long[]{5L, 22L, 26L, 11L, 14L, 209999999999L}); //以下两行测试代码,相当于把 a1,a2,a3,a4,a5在同一个DataConjunction中进行测试 DataConjunction conjunction new DataConjunction(new IDataArray[]{a1, a2, a3, a4}); DataConjunction dataConjunction new DataConjunction(new IDataArray[]{conjunction, a5}); long data -1; long begin System.nanoTime(); while((data dataConjunction.nextDoc()) ! IDataArray.NOMOREDATA) { System.out.println(data); } System.out.println("cost : " + (System.nanoTime() - begin) / (float) 1000000 + " ms"); }输出:bash51122209999999999cost : 0.289 ms 并集其测试代码可以自行编写,如果minMatchNum与链表数量相等,其实结果和并集一样。 差集测试代码自行编写。

    链表   交集   并集   差集   Lucene   Java   搜索引擎   2019-08-13 浏览(728) 有用(0) 阅读原文>> [原创]
  • 搜索引擎进阶——solr自定义function   

    本章要介绍的内容是solr中的自定义排序规则,或者说自定义得分函数。看懂本章内容,最好了解过以下知识点:1. solr的基本查询功能2. solr的edismax高级复合查询3. edismax中bf的作用关于solr内置function的用法可以参考官方文档《[Function Queries][solrLink]》,后续如果有机会,我会另出一篇文章加以阐述。---- 需求背景本来搜索服务提供的是一个职位搜索功能,面向的用户是猎头。所以,有一个需求就是按照猎头对每个职位的一个偏好预测值(记为V)进行职位综合排序。每个猎头对于不同的职位都有一个偏好预测值,记为H1V1。这个值由AI团队根据猎头所有行为记录进行统计计算,然后搜索团队要在猎头某一次搜索的结果内进行偏好预测值排序。几万猎头和几万职位的预测值是一个非常庞大的数据集。功能实现方式:1. 在职位索引增加一个动态字段,然后在建索引的时候猎头ID命名动态字段,对应的值就是这个猎头对当前职位的偏好预测值。dmdouble10002100,表示猎头10002对当前职位的偏好预测值为100。然后在搜索的时候,通过猎头id指定字段进行sort即可。2. 自定义一个function,通过solr提供的功能,在搜索时进行实时预测值查询,然后内置排序。方法1确实是一个最简单的方式,非常好理解,就是增加一个动态排序字段,然后sort即可。但是问题是数据量会非常大,而且意义不大。如果有10000个职位,30000个猎头,那么笛卡尔积就是3亿的偏好预测值,平均每个职位上要大约增加30000个动态字段,一个document会变得非常臃肿。当然,可以进行无效数据的预处理等方式进行优化,但是最后的数据依旧会庞大无比,关键是大部分都是无效数据。所以,我采用的是方法2。![图片](https://oomabc.com/staticsrc/img/201812/18/15451202135725418a931c2544f98978a1ed52005d528.jpg)--- 功能实现我这里先介绍功能的具体实现,至于底层原理待我搞的完全清楚之后再进行解释,以免耽误大伙。 ValueSource提供运行时获取document对应字段值的能力。 PositionSortValueSource这是一个自定义的类,继承了ValueSource。内部维护了几个对象:+ 一个获取职位ID的ValueSource对象,用于在运行期获取对于职位ID。+ 一个获取职位本身价值分的ValueSource对象,用于在运行期获取职位的价值份。+ 一个当前用户(猎头)对每个职位的偏好预测值map,可以获取用户对每个职位的预测值。javapublic class PositionSortValueSource extends ValueSource { // 职位ID的reader对象,获取职位ID private ValueSource valueSource null; // 职位价值分的reader对象,运行时获取价值分 private ValueSource defaultSortValueSource null; //保存当前猎头,对每个职位的偏好预测值,key是职位ID; private Map sortMap new HashMap(0); public PositionSortValueSource(ValueSource valueSource, ValueSource defaultSortValueSource, Map sortMap) { super(); this.valueSource valueSource; this.defaultSortValueSource defaultSortValueSource; this.sortMap sortMap; } @Override public FunctionValues getValues(@SuppressWarnings("rawtypes") Map context, AtomicReaderContext readerContext) throws IOException { //获取职位ID final FunctionValues positionIdValue valueSource.getValues(context, readerContext); //获取职位对应的职位价值份 final FunctionValues defaultSortFunctionValues defaultSortValueSource.getValues(context, readerContext); return new FloatDocValues(this) { @Override public float floatVal(int doc) { Long positionId StringTools.getLong(positionIdValue.strVal(doc), -1L); if (positionId 标签之间添加如下配置:。name就是你将要暴露出去的函数名,class就是上面定义的PositionSortSoruceParser的签名路径。建议将这行配置添加在最末尾,方便查找。 2、拼装查询语句很简单,只要在q参数中进行使用即可:val:"positionDefaultSort('10010')"。这样就会根据猎头10010这个猎头对每个职位的偏好预测值对职位进行排序了。如果有更复杂的需求,也可以用这个方式进行处理,不过需要考虑性能和内存的影响。---- 其它关联的数据结构本次功能设计其它solr、lucene的数据结构,给出相关说明,但是具体的使用入库需要后续搞清楚之后再细化。仅供参考。 NamedList这是solr提供的一个存储有序键值对的数据结构的容器类型的类,它有几个特点:1. 键可以重复2. 键值对是有序的3. 每个元素可以通过数值下标访问4. 键值皆可为null这个数据结构对外暴露的接口有点像常用的Map(不过key是固定的String类型,value是泛型),可以通过add方法添加键值对,类似map.put。也可以根据指定的key通过gei方法获得对应的值。不过,它也可以通过添加键值对的顺序(下标,类似list)来分别获得键和值。不过,这个数据结构为的是提供一个根据元素索引来实现高速访问的功能,而不是像map一样根据key。因为它内部的数据结构是一个protected final List nvPairs;,而且将键值依次存储:java / Adds a name/value pair to the end of the list. / public void add(String name, T val) { nvPairs.add(name); nvPairs.add(val); }[solrLink]: http://lucene.apache.org/solr/guide/66/function-queries.html

    ValueSource   排序   Solr   Java   搜索引擎   2019-07-23 浏览(1384) 有用(0) 阅读原文>> [原创]
  • 应用算法学习(一)—— TopN算法   

    零、应用场景最早接触这个算法,是在看Lucene实现原理相关代码的时候。搜索返回查询结果就是一个很典型的TopN算法应用,获取综合分数最高的前N个结果。搜索场景,通常数据量会在百万级、千万级甚至更多,因此,获取分数最高的前N个结果的性能好坏直接影响搜索体验。获取前N个得分最高的结果,可以有不同的方法:1. 直接对数据(Item)集进行排序,然后截取前N个Item;那么,排序算法会对性能有较大影响。例如快排的时间复杂度在O(n)到O(nn)之间,平均复杂度是O(nlog(n))。2. 对所有Item进行一次遍历,对于遍历每个Item的时候,始终有一个临时结果集来保存当前情况下的可能结果集,当遍历结束时,临时结果集就是最终结果,只要按顺序输出即可。本身遍历比较简单,那么选择临时结果集的数据结构就是算法的关键。我们对临时结果集的数据结构有几个要求: 1. 数据结构本身可以有序输出Item。 2. 可以快速新增一个Item,而且可以保持i中的特性。 3. 可以快速判断是否需要替换Item,且替换之后可以保持i中的特性。--- 一、算法简介Lucene中使用的最小二叉堆,就是满足了上面第二点中提出的要求(堆特性)。 最小二叉堆:父节点不大于其两个子节点,两个子节点直接的大小比较没有要求。堆顶是所有节点中最小的,但是最终整个堆返回的就是前N个最大值。解释: 堆顶最小的目的是,在遍历时,如果发现某个Item的值大于堆顶(找出前N个最大的要求就是,用某个Item替换掉临时结果集中最小的,堆顶始终最小的话就可以很方便判断Item是否可以入堆,而且直接删除被替换的堆顶),则可以替换掉当前堆顶,然后执行节点沉降,以便保持特性。它的时间复杂度为 O(nlog(n))。 主要过程1. 遍历目标集,每次遍历的数据节点记为Item。2. 当前已遍历的Item数量m,m < N时,直接入堆,通过节点升顶保持特性。3. m > N 时,如果Item > root,则替换,然后节点沉降。因为此时root可能已经不是最小值。4. 遍历结束时,堆中保存的就是前N个最大的Item,然后进行依次出堆即可,每次出堆只是弹出堆顶,都需要节点沉降操作。--- 二、算法细节 数据结构和概念基础Item定义:java/ 抽象节点 只定义个方法,返回节点用于比较的值 /public interface ITopNBean { double value();}TopN二叉堆数据结构:java/ 在一堆数中找出前N个最大的数,采用二叉堆 此为最小二叉堆,即最顶层的元素最小,当超过size的数大于最小元素时,需要重排。也就是说,这里的最小堆算法是获取前size个最大的元素 同理,获取前n个最小的数据,那么就是最大二叉堆,堆顶是最大的元素 模仿Lucene中的获得评分前N的DocumentID /public class TopNCreator { private ITopNBean[] heap; //存储数据 private int size; //已存数据个数,也代表指针位置 private int maxSize; //取前maxSize大的数,就是前面的 N //用于空节点对比,删除节点 private ITopNBean nullBean new NullBean(-1); //初始化构造函数 public TopNCreator(int maxSize) { super(); this.maxSize maxSize; heap new ITopNBean[maxSize+1]; size 0; }}用数组模拟堆,记为heap,根节点从下标1开始,方便用size直接作为下标和数量来使用;每次扫描的节点,记为element;当前已扫描的节点数量为size;要求返回的前N个,这里N记为maxSize;堆顶最小元素记为minElement;获取堆顶元素的方法记为top()。java / 返回top 最小数据保存在根节点 @return / public ITopNBean top(){ if(size 0){ return heap[1]; }else{ return nullBean; } } 节点入堆当size < maxSize,直接将element追加到数组最后,这里是先size ++,然后将element放到heap[size]位置。此时,新入堆的元素处于堆底,因此需要进行节点升顶操作来保持堆的特性。当size > maxSize,如果 element.value() > top().value(),直接设置heap[1]element。此时堆顶(heap[1])可能已经不是最小了,因此需要从根节点开始,进行与子节点的比较。发现子节点比父节点下,则进行位置交换,完整的过程就是节点沉降。当size > maxSize,如果 element.value() < top().value(),则该节点不可能是前maxSize个最大的数,则直接略过。java / 插入数据 @param element @return / public boolean insert(ITopNBean element){ //未达到指定数据数量 if(size 0 && element.value() top().value()){ //新数据大于最小的元素才进入,并调整数据顺序 heap[1] element; //替换头部元素(也就是最小的元素)为当前元素(因为当前元素比头部元素大) adjustTop(); //调整头部元素 return true; }else{ return false; } } public final void adjustTop(){ downHeap(); } 节点升顶此方法针对的节点是堆尾的刚插入的节点,这个节点的位置可能是不正确的,因为此时的堆是无法满足堆的特性的。我们将这个位置可能不正确的节点称为失位节点,记为node。此方法的目的就是为这个node找到合适的位置j,这个位置一定是它的上层节点。那么,只要将node与父节点进行大小比较。我们记node起始位置为i,如果比父节点j小,则将父节点放置在i上,那么j有可能是node的正确位置,所以i设置为j,然后j变为j的父节点。接下来,继续将node与j节点进行比较,逻辑同前面一致。当跳出循环比较之后,此时的i就是node的正确位置,令heap[i]node即可。上面描述了节点升顶的细节过程,下面给出示例代码,更直观的了解一下:java //节点升顶 public final void upheap(){ int i size;//失位节点的原始位置 i,它最终的正确位置依旧用i标记 ITopNBean node heap[i]; //将失位节点保持在node变量上;node的最终正确位置,依旧用i标记 int j i 1; //i 父节点位置 j,通过移位操作 //有父节点,并且失位节点node小于父节点,则要交换位置 while(j 0 && node.value() 1; //重新计算i的父节点,依旧记为j } heap[i] node; //将失位节点放入合适位置 } / 存入数据 @param element / public void put(ITopNBean element){ size ++; heap[size] element; upheap(); } 节点沉降这个操作是发生在堆顶节点发生变更之后,因为此时堆已经无法满足其基本特性了,所以需要将堆顶节点与其子节点进行对比来决定是否需要交换位置。说白了就是为堆顶节点(失位节点)找到一个合适的位置。记失位节点为node,其当前位置为i,i也是node的最终正确位置;i的父节点分别为j、k;最终与i进行比较的是j(j是两个父节点较小的一个)。对比node和j节点的大小,如果j节点较小,则将j节点放置在i位置上,此时j可能就是node的正确位置。同样,更新i和j的值,进行下一轮的对比操作。java / 节点沉降 往下沉降,替换了头部的数据后需要根据二叉堆的规则重排数据 保证根数据是最小的数据 / public void downHeap(){ int i 1; / 刚插入的数据,分别和它的两个子元素比较 / ITopNBean node heap[i]; // node表示失位节点,i是它初始的位置 int j i 出堆返回堆顶元素,将堆尾元素放置到堆顶,清空堆尾元素,然后执行堆顶沉降操作。java / 排放数据,从最小的元素开始排放,会删除该元素 @return / public ITopNBean pop(){ if(size 0){ ITopNBean result heap[1]; //第一个元素(堆顶)作为结果返回,因为第一个元素最小 heap[1] heap[size]; //堆尾元素放置到堆顶 heap[size] new NullBean(-1); //最大的元素清空 size --; //指针前移 downHeap(); //堆顶沉降 return result; }else{ return nullBean; } } 测试代码java/ @param args / public static void main(String[] args) { TopNCreator find new TopNCreator(5); int[] source { 44, 65, 23, 45, 55, 78, 21, 32, 43, 876, 1, 66, 13, 35, 38, 96, 437, 55, 980, 21, 1010, 1001, 1334, 42, 2354, 7788, 344, 333, 557, 5454, 7664, 1235 }; int maxNum 10; long b System.currentTimeMillis(); maxNum source.length; for (int i 0; i maxNum; i++) { // int a(int)(Math.random()maxNum); int a source[i]; find.insert(new IntegerBean(a)); // System.out.println(find.insert(a)+":"+a); } System.out.println(""); / find.print(); / int max find.getSize(); for (int i 0; i max; i++) { System.out.println(find.pop()); } System.out.println("cost : " + (System.currentTimeMillis() - b)); }实现ITopNBean接口的对象,都可以直接进行TopN的排序。![图片](https://oomabc.com/staticsrc/img/201809/20/15374302172273f9717808ada40d68a59ea5cb9f46ca5.jpg)

    topN   二叉堆   Lucene   搜索引擎   2018-09-20 浏览(2319) 有用(0) 阅读原文>> [原创]
  • blogTest
    分享文章
     
    使用APP的"扫一扫"功能,扫描左边的二维码,即可将网页分享给别人。
    你也可以扫描右边本博客的小程序二维码,实时关注最新文章。