[zz]通过构树快速计算编辑距离

今晚微软编程题目中有一题:海量数据的相似字符串快速统计,复杂度希望能近似到线性。类似一个快速KNN的问题,快速统计方法分为近似与精确方法。近似方法属于ANN流派,而精确方法大多通过几何方法,如各种Tree,下面是Matrix67用中文介绍的一篇如何通过Tree来快速计算编辑距离的文章。 参考出处:1. http://www.matrix67.com/blog/archives/333 2. http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees =========================下为转载文章============================== 除了字符串匹配、查找回文串、查找重复子串等经典问题以外,日常生活中我们还会遇到其它一些怪异的字符串问题。比如,有时我们需要知道给定的两个字符串“有多像”,换句话说两个字符串的相似度是多少。1965年,俄国科学家Vladimir Levenshtein给字符串相似度做出了一个明确的定义叫做Levenshtein距离,我们通常叫它“编辑距离”。字符串A到B的编辑距离是指,只用插入、删除和替换三种操作,最少需要多少步可以把A变成B。例如,从FAME到GATE需要两步(两次替换),从GAME到ACM则需要三步(删除G和E再添加C)。Levenshtein给出了编辑距离的一般求法,就是大家都非常熟悉的经典动态规划问题。 在自然语言处理中,这个概念非常重要,例如我们可以根据这个定义开发出一套半自动的校对系统:查找出一篇文章里所有不在字典里的单词,然后对于每个单词,列出字典里与它的Levenshtein距离小于某个数n的单词,让用户选择正确的那一个。n通常取到2或者3,或者更好地,取该单词长度的1/4等等。这个想法倒不错,但算法的效率成了新的难题:查字典好办,建一个Trie树即可;但怎样才能快速在字典里找出最相近的单词呢?这个问题难就难在,Levenshtein的定义可以是单词任意位置上的操作,似乎不遍历字典是不可能完成的。现在很多软件都有拼写检查的功能,提出更正建议的速度是很快的。它们到底是怎么做的呢?1973年,Burkhard和Keller提出的BK树有效地解决了这个问题。这个数据结构强就强在,它初步解决了一个看似不可能的问题,而其原理非常简单。 首先,我们观察Levenshtein距离的性质。令d(x,y)表示字符串x到y的Levenshtein距离,那么显然: 1. d(x,y) = 0 当且仅当 x=y (Levenshtein距离为0 字符串相等) 2. d(x,y) = d(y,x) (从x变到y的最少步数就是从y变到x的最少步数) 3. d(x,y) + d(y,z) >= d(x,z) (从x变到z所需的步数不会超过x先变成y再变成z的步数) 最后这一个性质叫做三角形不等式。就好像一个三角形一样,两边之和必然大于第三边。给某个集合内的元素定义一个二元的“距离函数”,如果这个距离函数同时满足上面说的三个性质,我们就称它为“度量空间”。我们的三维空间就是一个典型的度量空间,它的距离函数就是点对的直线距离。度量空间还有很多,比如Manhattan距离,图论中的最短路,当然还有这里提到的Levenshtein距离。就好像并查集对所有等价关系都适用一样,BK树可以用于任何一个度量空间。 建树的过程有些类似于Trie。首先我们随便找一个单词作为根(比如GAME)。以后插入一个单词时首先计算单词与根的Levenshtein距离:如果这个距离值是该节点处头一次出现,建立一个新的儿子节点;否则沿着对应的边递归下去。例如,我们插入单词FAME,它与GAME的距离为1,于是新建一个儿子,连一条标号为1的边;下一次插入GAIN,算得它与GAME的距离为2,于是放在编号为2的边下。再下次我们插入GATE,它与GAME距离为1,于是沿着那条编号为1的边下去,递归地插入到FAME所在子树;GATE与FAME的距离为2,于是把GATE放在FAME节点下,边的编号为2。 查询操作异常方便。如果我们需要返回与错误单词距离不超过n的单词,这个错误单词与树根所对应的单词距离为d,那么接下来我们只需要递归地考虑编号在d-n到d+n范围内的边所连接的子树。由于n通常很小,因此每次与某个节点进行比较时都可以排除很多子树。 举个例子,假如我们输入一个GAIE,程序发现它不在字典中。现在,我们想返回字典中所有与GAIE距离为1的单词。我们首先将GAIE与树根进行比较,得到的距离d=1。由于Levenshtein距离满足三角形不等式,因此现在所有离GAME距离超过2的单词全部可以排除了。比如,以AIM为根的子树到GAME的距离都是3,而GAME和GAIE之间的距离是1,那么AIM及其子树到GAIE的距离至少都是2。于是,现在程序只需要沿着标号范围在1-1到1+1里的边继续走下去。我们继续计算GAIE和FAME的距离,发现它为2,于是继续沿标号在1和3之间的边前进。遍历结束后回到GAME的第二个节点,发现GAIE和GAIN距离为1,输出GAIN并继续沿编号为1或2的边递归下去(那条编号为4的边连接的子树又被排除掉了)…… 实践表明,一次查询所遍历的节点不会超过所有节点的5%到8%,两次查询则一般不会17-25%,效率远远超过暴力枚举。适当进行缓存,减小Levenshtein距离常数n可以使算法效率更高。

分布式检索结果的前翻页与后翻页

对于一个大的分布式检索系统,检索容量可能达到万亿级,如何能够快速展示给用户,而且能够前翻页与后翻页。 1,涉及到Learning to Rank问题,那么基础索引组件就应该先进行预分类,如按时间进行索引,按重要性进行索引,这样能够保证快速查询结果。进行小范围内排序。如果基础索引组件设计就是混乱的,Rank问题就天方夜谭了。 2,关于统计结果数,根据查询条件扫一遍全索引是不现实的。如度娘和谷哥显示的结果数也是通过小范围内的查询结果然后根据概率模型估算出来的,一个好的概率模型能够比较好的逼近真实结果,逼近(Approximation)算法才是是大数据下的可行性方案。 3,前翻页后翻页,对于命中率很低的查询应用,由服务器段进行缓存代价是浩大的。建议客户端进行部分缓存,能够缓存一部分时间戳信息,或id信息,能够保证用户翻页过程中能够连续触发。而不是从头再次扫索引。。。扫索引的IO代价是很大的。连续翻页对这部分的实现也很重要。如大数据下的度娘和谷哥就没有实现跳转功能,而小数据下的BBS则多是根据条件重新刷数据库的。 3.1,如果是按时间翻页,为了处理同一时间戳上的数据覆盖问题,就需要同时利用_version_信息进行排序,如在Solr中可利用sort:startTime desc, _version_ desc,同时根据缓存中记录的偏移量剔除掉同一时间戳上的前页覆盖数据。

关于搜索引擎分页查询

Google 搜索结果页概览 【关于搜索引擎的分页】 http://hi.baidu.com/cycosmic/item/6993d7175a306226f6625c88 查询+缓存机制 【百度搜索结果终结分页之我见】http://itlobo.com/articles/1718.html 没必要全部检索,结果数采用概率进行估算。 【大数据查询是否适合做缓存】http://wenku.baidu.com/view/5e8e8c6f58fafab069dc0294.html 不适合服务器缓存,最好客户端缓存。 【基于Lucene搜索结果分页输出】http://www.cnblogs.com/suyuan/archive/2008/04/03/1136288.html 查询+缓存机制 分块缓存。

Solr/Lucene的排序机制

以下内容转自:http://hi.baidu.com/shirdrn/item/c5611d1556921a0cb98a1aa4 关于Lucene得分的计算。 在IndexSearcher类中有一个管理Lucene得分情况的方法,如下所示: public Explanation explain(Weight weight, int doc) throws IOException { return weight.explain(reader, doc); } 返回的这个Explanation的实例解释了Lucene中Document的得分情况。我们可以测试一下,直观地感觉一下到底这个Explanation的实例都记录了一个Document的哪些信息。 写一个测试类,如下所示: package org.shirdrn.lucene.learn; import java.io.IOException; import java.util.Date; import net.teamhot.lucene.ThesaurusAnalyzer; import org.apache.lucene.document.Document; import org.apache.lucene.document.Field; import org.apache.lucene.index.CorruptIndexException; import org.apache.lucene.index.IndexWriter; import org.apache.lucene.index.Term; import org.apache.lucene.index.TermDocs; import org.apache.lucene.search.Explanation; … 继续阅读

再谈Solr core LRU–注册3W个SolrCore索引大数据

之前我们利用 Solr现成的LRU对Core进行动态加载 http://jacoxu.com/?p=595,但是有个问题是先注册的core都没有进入加载的LRU队列中,可以通过界面显示:http://localhost:8983/solr/admin/cores?action=STATUS 返回所有的状态,未加载的core的 isLoaded属性是false。不过4.6版本修复了个这个bug,可以进行尝试。对于大数据来说,这个bug的修复无疑是值得庆祝的! 下面我们来做一个测试,尝试在单个solr实例中创建万级规模的core, 1、测试单实例最大Core数和实例数,测试环境:Linux-Suse11.1 24processors, 2.0GHz, 64G RAM. ,申请内存16G 【试验】:每个core有545条短文本,测试在单实例中创建25000个core,从创建第一个core只用了0.3秒,到第3500个core用了1.1秒,创建新core速度都很快,并没有太大影响。目前所有的core都处于加载状态,打开文件数已经达到25469,使用内存达9G,下面重启tomcat使得目前加载的core进入LRU队列中。重启之后,只打开了1个core,其他所有的core进入未索引数据未加载状态。 然后重启入库程序,继续创建新core,此时创建速度很慢,Solr基本处于卡死状态。创建一个新core用了7分钟,最重要的是,这段时间内,基本无法完成其他基本查询功能。 停掉入库程序之后,Tomcat仍然处于卡死状态,重启tomcat 尝试更新Solr最新版本4.6,创建一个core只使用了0.2秒,创建到3500个core时也只使用0.3秒。而且,所有的core都在LRU-100队列中进行动态加载。文件打开数维持在800左右,内存使用峰值为7G。 接下来把LRU设为50,重启tomcat后继续插数据,测试单实例的CoreList上限 注意由于文件夹同级目录有上限32000,所以最好同时写入到多个目录中去。 持续创建新core,LRU-50,创建到6K左右时,内存占用率达8G左右,创建新core在0.5秒左右,commit 5000条数据在0.5秒左右,文件打开数维持在300左右。创建到1W7左右的时候,Tomcat内存使用到15G,文件打开数维持在300左右,创建一个新core 1秒左右,插入5000条数据使用0.6秒或26秒,重启tomcat,界面初始化时反应有些迟钝 有10分钟之久,入库程序可正常插入,创建到25000个core时,创建Core的速度仍然很快,不超过2秒,不过持续写入数据出现JVM GC问题,有时会稍慢一些到1分钟左右。值得注意的是重启tomcat居然用了45分钟之久,想必是刷了一遍每个core的STATUS,这个操作很会很慢,此时Tomcat只占用了一个processor的100%CPU进行处理。 我们尝试下一个试验,把25000个core分布到10个实例中去,减少每个实例所维护的CoreList,或许刷新Core STATUS的时候多个实例能够并发。在入库时,查看CPU的状态能够发现,单线程写入Solr多实例时,虽然Tomcat基本也占用100%左右的CPU,但是会分布到多个CPU上。由于时间问题这个试验没有做完,只索引了14000个core,此时重启tomcat用了不到3分钟,时间尚可接受,待进一步后续验证。 另一点值得注意的是,tomcat下的实例数并非可以无限制增加,在SuSE-11.1 64G环境下曾部署过10个实例没有问题,但是在SuSE-11.2 256G环境下部署6个实例就无法启动,报出如下错误: OutOfMemoryError thrown from the uncaughtExceptionHandler in thread “main” OutOfMemoryError thrown from the … 继续阅读

Solr4.0 如何配置使用UUID自动生成id值

下面是转来的一篇文章,经过测试使用,OK。不过要注意的问题是,既然id是自动生成的,那么如果有两份一模一样的数据建立索引的时候会有各自不同的id而保存多份数据,如果id由自己来指定的话就比较方便以后数据更新。 原地址:http://blog.csdn.net/keepthinking_/article/details/8501058 最近学习了Lucene,随便也学习了Solr,Solr规定每一条记录必须有一个主键值,用来唯一标识一条索引的记录,默认是使用id字段来作主键的(可以通过修改schema.xml文件更改),最烦的是这个主键不能设置自动增长,所以每添加一条记录,不得不手动为id字段赋值,如果不小心重复了,还很恶心的直接覆盖了原来的记录,所以在编程的时候不得不通过一些途径来维护这个id值,通过google发现了一个可以自动生成id值的方法,即让solr自动生成UUID值(Universal Unique Identifiers通用唯一标识符),这样编程的时候就不用维护这个id值了,使用这种做法的缺点就是:id值不是数值连续的,它是一串字符,如:5bb977a7-8a4c-46d6-ae49-b4eefade080c 具体配置如下:(这是Solr 4.0的配置) 一、配置schema.xml文件 1、添加fieldType <types>       <!– other field types –>       <fieldType name=“uuid” class=“solr.UUIDField” indexed=“true” />   </types>   2、添加主键id字段配置(注释或者删除原来的id字段配置,切记) <field name=“id” type=“uuid” indexed=“true” stored=“true” required=“true” multiValued=“false” />   二、配置solrconfig.xml文件 1、注释掉以下的配置,原因及可能产出的异常参考:https://issues.apache.org/jira/browse/SOLR-3398 <searchComponent name=“elevator” class=“solr.QueryElevationComponent” >     <str name=“queryFieldType”>string</str>     <str name=“config-file”>elevate.xml</str>   </searchComponent>   2、添加一个updateRequestProcessorChain配置 <updateRequestProcessorChain name=“uuid”>       <processor class=“solr.UUIDUpdateProcessorFactory”>           <str name=“fieldName”>id</str>       </processor>       <processor class=“solr.RunUpdateProcessorFactory” />   </updateRequestProcessorChain>   3、修改其中一个requestHandler配置,注意:上一步是添加,而这里是修改,如果直接添加的话,那么就会重复配置,这样后面的配置会覆盖前面的配置,本人就是很不幸的被默认的配置覆盖了我添加的配置,当时够郁闷的! <requestHandler name=“/update” class=“solr.UpdateRequestHandler”>       <!– See below for information on defining              updateRequestProcessorChains that can be used by name              on each Update Request          –>       <!–           <lst name=“defaults”>   … 继续阅读

Locality Sensitive Hashing归总

最近发邮件讨论Semantic Hashing的同学和同事很多,推荐李老师的文献列表供大家参阅:http://cs.nju.edu.cn/lwj/L2H.html 说到Hash,大家都很熟悉,是一种典型的Key-Value结构,最常见的算法莫过于MD5。其设计思想是使Key集合中的任意关键字能够尽可能均匀的变换到Value空间中,不同的Key对应不同的Value,即使Key值只有轻微变化,Value值也会发生很大地变化。这样特性可以作为文件的唯一标识,在做下载校验时我们就使用了这个特性。但是有没有这样一种Hash呢?他能够使相似Key值计算出的Value值相同或在某种度量下相近呢?甚至得到的Value值能够保留原始文件的信息,这样相同或相近的文件能够以Hash的方式被快速检索出来,或用作快速的相似性比对。位置敏感哈希(Local Sensitive Hashing, LSH)正好满足了这种需求,在大规模数据处理中应用非常广泛,例如已下场景[1]: 1. 近似检测(Near-duplicate detection):通常运用在网页去重方面。在搜索中往往会遇到内容相似的重复页面,它们中大多是由于网站之间转载造成的。可以对页面计算LSH,通过查找相等或相近的LSH值找到Near-duplicate。 2. 图像、音频检索:通常图像、音频文件都比较大,并且比较起来相对麻烦,我们可以事先对其计算LSH,用作信息指纹,这样可以给定一个文件的LSH值,快速找到与其相等或相近的图像和文件。 3. 聚类:将LSH值作为样本特征,将相同或相近的LSH值的样本合并在一起作为一个类别。 LSH(Location Sensitive Hash),即位置敏感哈希函数。与一般哈希函数不同的是位置敏感性,也就是散列前的相似点经过哈希之后,也能够在一定程度上相似,并且具有一定的概率保证[3]。 LSH的形式化定义: 对于任意q,p属于S,若从集合S到U的函数族H={h1,h2…hn}对距离函数D(q,p),如欧式距离、曼哈顿距离等等,满足条件: 若\(D(p,q) \le r\), 且\({\rm{Pro}}[h(p) = h(q)] \ge p1\) 若\(D(p,q) > r(1 + \varepsilon )\), 且\({\rm{Pro}}[h(p) = h(q)] \le p2\) 则称D(p,q)是位置敏感的。 如下图,空间上的点经位置敏感哈希函数散列之后,对于q,其rNN有可能散列到同一个桶(如第一个桶),即散列到第一个桶的概率较大,会大于某一个概率阈值p1;而其(1+emxilong)rNN之外的对象则不太可能散列到第一个桶,即散列到第一个桶的概率很小,会小于某个阈值p2. LSH的作用: … 继续阅读

关于Solr的性能调优

如何能在有限的服务器资源上较好的使用Solr服务,性能调优是必不可少的。鉴于个人经验,给出几条可调优方法: 1. 配置SolrConfig中的Directory, 不当的Directory会消耗大量的内存或IO资源,当索引规模变大时也很容易导致内存溢出,或索引维护的Map Failed现象!如何选择合适的Directory可参看《Lucene in Action》(第二版) Section2.10 中文本P52; 2. 配置Schema中的字段的 omitNorm= true, Norm中保存了大量的字段信息用于评分排序. 如果不是很必要的话可把omitNorm设置为true能够减少磁盘和内存的使用并加快索引速度,同时只用来索引而不需要显示的字段也可设置indexed=”true” stored=”false”, 具体Norm的作用可参见《Lucene in Action》(第二版) Section2.53 中文本P47; 3. 调整SolrConfig中的合并因子mergeFactor和内存触发机制setRAMBBufferSizeMB。mergeFactor越小,索引合并越频繁,索引段越少,同时,setRAMBBufferSizeMB越小,Writer更新的越频繁,索引段越多;《Lucene in Action》(第二版) Section11 4. 在索引阶段,不进行索引优化能够接受的话,就不进行索引优化optimize(),很耗时的一件事!但是在查询阶段,优化往往能够大幅度提高查询效率,因而如果可以,考虑周期性optimize()或optimize(maxNumSegments);《Lucene in Action》(第二版) Section11 注意:1. 在优化过程中,索引文件很容易占用超过自身文本大小10倍的硬盘空间,因而一定要考虑服务器的资源限制问题!《Lucene in Action》(第二版) Section11 中文本P355 2.字段中必留的三个: uniqueKey:id ,version, … 继续阅读

Solr的主从模式Master-Slave

在做Solr索引的时候,频繁读取数据文件,造成了Linux很大的物理内存分配给了cache, 即使已经设置了NIO模式.况且查询的时候压力也很大, 尤其是facet用shards进行多核查询统计时占用的内存极高. 而且为了避免读写的并发冲突问题可考虑利用主从Master/Slave进行同步操作, 使得读写操作分到不同的服务器上. 关于Solr的Replication机制是这么解释的: The SolrReplicationHandler supports replicating indexes from a “master” used for indexing and “slaves” used for queries. http://wiki.apache.org/solr/SolrReplication It is also neccessary for SolrCloud to function (in Cloud mode, the replication handler is used to … 继续阅读