门外汉解读Java中常用的算法
个人从事solr搜索引擎企业级开发已经有七八年,加上自身比较喜欢应用算法,所以整个工作过程前前后后接触了不少算法。这里会将工作中实际应用到的一些算法记录下来,包括TopN二叉堆、Lucene底层链表算法、自定义分词器扩展、关键字匹配扩展。有些只能算是应用技巧或者优化,我也一并记录在这里。
  • 应用算法学习(一)—— 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 浏览(2637) 有用(0) 阅读原文>> [原创]
  • Amazon 的推荐算法是否特别优秀   

    现在在京东、易迅、亚马逊等看到的主流推荐算法,一般都是基于物品自身相似性(不依赖于用户数据,没有冷启动问题)、基于用户浏览、喜欢、购买等数据的协同过滤推荐(用户纬度和商品纬度)。其实这些推荐算法的核心思路,是很朴素的。 一、基于物品自身相似度。例如衣服A和衣服B,对于它们在分类、价格段、属性、风格、品牌定位等等其他属性纬度的表现,来计算它们之间的相似度,如果相似度高,那么在有用户浏览A的时候,就可以推荐B(实际当然没这么简单)。因为衣服的这些属性是不依赖于用户的,所以解决了系统的冷启动问题,正是不依赖与用户的行为数据,因此比较死板,完全没有个性化的推荐。这个算法的思路很多人都清楚,但是越是简单的算法,要达到好的效果就越是难,特别是推荐这种转化率非常低的算法。商品有几十个属性,对不同分类的商品,并不是所有的属性都是有必要纳入相似度计算的,已经纳入的属性但是重要性也是有区别的,这样一来,光光给不同类别商品筛选必要属性以及设置这些属性在相似度计算中的权重值,就是一项非常浩大的工程了。亚马逊的推荐系统在全球行业中也是最早的,相信他们在这个问题上肯定有自己一套迅速有效的方法。当然要我来说具体是怎么样的,我怎么可能知道呢^^,知道了也不告诉你。 二、基于用户纬度的协同过滤。采集用户的购买(浏览、收藏都行)商品数据,把用户购买的商品列出来,当作用户的属性纬度。例如用户A购买了商品1、2、3、4、5,用户B购买了商品1、2、5、6,那么可以简单的将12345和1256分别作为A和B的属性特征字符串,计算A和B的相似度,经过简单的聚类将用户聚成几个类别(邻居)。假设A和B同属于一个聚类,那么可以称A和B有比较相似的偏好,继而可以将A买过而B没买过的其他商品推荐给B。在这一个流程里,可以发挥的地方有很多:1. 用户的行为数据需要去噪音(买了多少商品以下的用户不考虑,有代购的不考虑,如何精准的判断代购,商品时效性的考虑,数据的时间跨度等等);2. 计算相似度的时候跟第一点中提到的一样,并不是所有商品对用户的描述度都是一样的。可能价格低的重要程度就没有昂贵的商品重要。3. 通过聚类计算邻居的时候,聚类算法又是另一门学科了,或者选择分类算法。然后聚类的门槛选择都是需要很长时间的测试、观察、修改的,需要时间的积累。4. 浏览、购买、收藏等历史数据是不是可以协同过滤。现在很多网站给出的推荐,都不是单一推荐算法的,一个算法的输出可以作为另一个算法的输入,可以是多个算法的输出综合筛选,这也是一个需要长时间积累的地方。 三、基于物品纬度的协同过滤。其实我觉得是和第二点很相似,就是将用户作为商品的属性纬度来看。例如商品A被用户1,2,3,4,5,6购买过,商品B被用户1,3,4,5,7购买过,那么将123456作为商品A的特征属性数据,13457作为商品B的特征数据,然后计算商品A和B的相似度(这里的相似度却别于第一点提到的相似度,似乎叫“相似度”不是很合适)。因为我们有理由认为同一个人群买了A,又买了B,那么A和B一定有某种关联。在这个流程里面可以发挥的地方基本和第二点中提到的差不多。 四、强关联规则的应用。重点是同一次购买记录(当然也不是必然的,看自己的选择)。首先收集数据就需要把一单购买一种商品的过滤掉。然后一次对每一条记录中进行成对提取统计,简单的就是两两统计次数,这种提取出来的都是两个商品被同时购买的次数,适用于一对一推荐。还有一种是通过FPTree算法(似乎是这个名字吧,因为我们公司是一对一的需求,所以这个算法我没怎么研究,是我自己写的两两统计),不光是一对一推荐,可以一对二,二对一。在这个流程里面,关联规则(关联规则百度百科)挖掘算法非常重要,其中置信度和支持度也是需要不断调整的地方。 五、所有推荐系统之间的数据共享、数据的定时自动更新、自动学习。总的来说,推荐算法大部分都是很朴素的,但是需要运用的好,没有长时间的积累是做不到的。仅仅是聘请一些算法工程师,运用一些算法框架,想取得好的推荐效果,基本是不可能的。只有算法与具体业务相结合才能产生化学反应。转自个人的知乎回答![图片](https://oomabc.com/staticsrc/img/201809/13/153683286545703f69110d6954d1e9251c5ec81672b47.jpg)

    亚马逊   协同过滤   推荐算法   2018-09-14 浏览(1568) 有用(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 浏览(4042) 有用(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 浏览(950) 有用(0) 阅读原文>> [原创]
  • 乡村风味——KMP算法通俗解释   

    题目给出两个字符串main和sub,要求查找sub在main中第一次出现的位置(从0开始)。未出现过,则返回-1。 样例 例子 1 : 输入:main "1235J235J234", sub "235J234" 输出:5 例子 2 : 输入:main "12345Q2345", sub "2345J" 输出:-1 解题这个题目其实比较简单,我们直接定义两个指针,一次进行字符比较。如果相同者指针一起后移,否则重置指针(sub指针大于0的时候,main的指针不需用动;否则只要main的指针后移即可),再次比较。其实main的指针是没有回头路的,只能后移或者不动。而sub的指针就很浪了,前前后后的移动。 程序员版1. 定义i为main的下标,j为sub的下标。current为main字符串在i处的字符,同样search是sub在j位置的字符;start是主串在一轮匹配中的开始位置。2. 如果两个下标都未超出各自字符串范围(下标小于字符串长度),则跳到步骤 3 ;否则跳到步骤 5 。3. 如果current与search相同,则表示当前位置一致。此时i和j下标都加一,然后跳到步骤 2;否则跳到 4 。4. 需要对i或者j下标进行重置:如果j本身就指向sub的第一个字符,则需要将start进行加一,i从start开始;否则,j下标重置为0,i下标不动;然后回到步骤 2 。5. 如果此时j的大小与sub子串长度一致,表示匹配成功,返回i减去sub长度即可(或者说i减去j)。 大爷大妈版1. 大爷有10张麻将牌,乱序排列好,依次在每张牌后面贴上序号,从0开始,递增。2. 大妈有4张麻将牌,乱序排列好,依次在每张牌后面贴上序号,从0开始,递增。3. 如果两个人手里都有牌,则大爷大妈分别打出序号最小的牌,然后跳到步骤 4;否则跳到步骤6 。4. 如果是相同的牌,则跳到步骤 3;否则跳到步骤 5 。5. 此时如果大妈只打出一张牌,则大爷可以丢弃打出的第一张牌;接着两人收回其它各自的牌。然后跳到 3。6. 打牌结束。如果此时大妈手上没有牌,则大妈赢,大爷去干家务;否则大爷赢,就是真·大爷了。 暴力代码版然而,上面说了这么多废话,其实并没有什么用,还是直接上简单的代码比较实在。javapublic static int indexOf(String main, String sub) { if(StringUtils.isBlank(main) StringUtils.isBlank(sub)) { return -1; } if(sub.length() 0) { return 0; } if(main.length() 0){ return -1; } //分别定义两个字符串的下标 int mainIndex 0, mainLen main.length(); int subIndex 0, subLen sub.length(); int mainStart 0; while(subIndex 源串:235J234 下标:0123456当子串下标为6的时候,发现对应字符与主串不一致,这时候需要进行主串和子串的回溯。暴力方法就是直接将子串回溯到起始位置0上,而主串回溯到本轮起始位置的后一个位置上。但这个子串是有规律的,本身子串内存在一定的重复。下标4、5的字符串与子串开始的下标0、1的字符串是一致的。沿用上面代码中的变量定义,当subIndex 6的时候,发现与主串当前字符不一致。它的潜台词就是:subIndex KMP算法 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。关于算法相关理论的推理过程,我这个现学渣(想当年我也是正宗的学霸,到了大学就放纵了,汗颜!--)就不来献丑了,参考文章[《【模式匹配】KMP算法的来龙去脉》](https://www.cnblogs.com/en-heng/p/5091365.html)。KMP算法的核心就是next数组的生成。网上不同的文章对于next数组的内容有所区别,主要是数组元素值加减一的区别,从而影响回溯时数组下标和取值后的修正,最终的思路和结果都是一致的。我在看了一些文章结合自己的思考之后,给出的next数组是无需在使用时修正的。例如子串235J234的next数组如下: 源串:235J234 下标:0123456 修正:0000012从上可以看出,当subIndex 6时,需要回溯到的值是2,与之前第二点讨论的情况一致。 如何生成next数组1. next数组是根据子串生成的。2. 通过两个独立的下标,将一个子串看做两个相同的字符串(同样定义为主和子,通过backIndex和subIndex标记,对应字符依旧定义为current和search),分别进行下标移动。3. 每一轮匹配都是从主串下标为0开始;主串下标可以重置,子串下标每次比较后都需要后移。4. subIndex可以从1开始,所以直接设置next[0] 0来表示此时的回溯值,其实是没动。5. 每次比较,backIndex都是回溯值,next[subIndex] backIndex;如果current和seaarch一致,则backIndex ++和subIndex ++;否则则backIndex 0、subIndex ++;然后重复步骤 5,直到subIndex sub.length结束。关于 5 :通俗点就是,不管是current和search不一致还是第一次一致,都是回溯到0的。因为第一次一致,表示前面的不一致,所以只能回溯到0;如果是第二次即以后的一致,则表示前面已经有一致的情况,此时回溯值才有意义。javastatic int[] createNextArray(String sub) { if(StringUtils.isBlank(sub)) { return null; } int[] next new int[sub.length()]; //初始也当做 0 next[0] 0; int len sub.length(); //回溯下标, 子串移动下标 int backIndex 0, subIndex 1; while(subIndex subLen(current search 导致 subIndex ++) 否则,表示子串的最后一个字符search与主串的current不一致,也就是subIndex不会递增,还是在while条件内。 所以,while结束只能是因为mainIndex mainLen,即主串遍历结束。 / return subIndex subLen ? mainIndex - subLen : noIndex;} 讨论,另一个阴差阳错的暴力版本我之前在写代码过程中还有一个版本:javapublic static int indexOf(String main, String sub) { if(StringUtils.isBlank(main) StringUtils.isBlank(sub)) { return -1; } if(sub.length() 0) { return 0; } if(main.length() 0){ return -1; } int mainIndex 0, mainLen main.length(); int subIndex 0, subLen sub.length(); int mainStart 0; while(subIndex subLen && mainIndex mainLen) { char current main.charAt(mainIndex); char search sub.charAt(subIndex); //指定位置字符一致,则直接后移即可 if(current search) { subIndex ++; mainIndex ++; } else { //不一致,子串无论如何都要重置到第一个字符 //如果当前子串本来就位于第一个字符,则只需要主串后移即可 //区别就是这里,与上面那个正常暴力版本,多了一个判断;后来发现,其实并没有什么用,只是多加了一次判断,单结果依旧是对的 if(subIndex 0) { mainStart ++; mainIndex mainStart; } //可以优化的是这个 //如果子串本身就有重复,那么可以判断下: //当前字符依次往前推有多少个字符 是 跟子串开头连续若干个字符一致 subIndex 0; } } return subIndex subLen ? mainIndex - subLen : -1;}上面的else里面多了一个subIndex 0的判断。最终结果应该是又多了几次比较,而不影响最终结果,因为都可以AC。不过我目前无法明确解释原因,只推测是跟主串与子串比较流程或者子串自身的规律有关。

    KMP   字符串比较   优化   2019-05-05 浏览(338) 有用(0) 阅读原文>> [原创]
  • blogTest
    分享文章
     
    使用APP的"扫一扫"功能,扫描左边的二维码,即可将网页分享给别人。
    你也可以扫描右边本博客的小程序二维码,实时关注最新文章。