密码保护：Distributed Learning
无法提供摘要。这是一篇受保护的文章。
标签归档：Information Retrieval
[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 查询+缓存机制 分块缓存。
Reading two Patents about Chinese Query Refinement by Google Inc.
1. Systems and methods for translating Chinese pinyin to Chinese characters [Link] a). Systems and methods to process and translate pinyin to Chinese characters and words are disclosed. b). 2. Systems and methods for spell correction of non-roman characters … 继续阅读
simHash是否适合短文本的相似文本匹配
附注：用BigInteger类型来存储64位的hash码 http://doc.java.sun.com/DocWeb/api/all/java.math.BigInteger 很好用，xor()异或、BigInteger.bitLength()取位长、.bitCount()取位为1的个数。 simHash算法流程： 1): 计算simHash码 a). 字符串String分词得到tokens； b). 计算每个tokens的64位Hash码； c). 按Hash码的位进行标记，1则标记为1、否则标记为-1； d). 把每个tokens的Hash码按位进行统计求和； e). 进行签名，大于0则为1，否则为0，得到64位simHash指纹。 2): 把64位simHash码均分为汉明距离n+1块，方便后续查找的所有近邻simHash码； 3): 计算两个simHash码的汉明距离， 方法一：给出simHash的64位二进制码字符串：str1.charAt(i) != str2.charAt(i)； 方法二：给出simHash的int值：先做异或，然后统计异或后二进制位数为1的个数 问题！？：simHash在短文本的可行性！ 测试相似文本的相似度与汉明距离 测试文本：20个城市名作为词串：北京,上海,香港,深圳,广州,台北,南京,大连,苏州,青岛,无锡,佛山,重庆,宁波,杭州,成都,武汉,澳门,天津,沈阳 相似度矩阵： simHash码： 勘误：0.667, Hm:13 是对比的msg 1与2。 可见：相似度在0.8左右的Hamming距离为7，只有相似度高到0.9412，Hamming距离才近到4，此时，反观Google对此算法的应用场景：网页近重复。 … 继续阅读
关于SimHash算法原理
最近发邮件讨论Semantic Hashing的同学和同事很多，推荐李老师的文献列表供大家参阅：http://cs.nju.edu.cn/lwj/L2H.html 前言： SimHash: Similarity Estimation Techniques from Rounding Algorithms 2002 A locality sensitive hashing scheme: sim(x,y). is a method of performing probabilistic dimension reduction of high-dimensional data. MinHash(Min-wise independent permutations): is a technique for quickly estimating how similar two … 继续阅读
Read paper about similarity Search
8B pages == 8Billion pages Title: Detecting Near-Duplicates for Web Crawling WWW 2007, Track: Data Mining. Session: Similarity Search Keywords: Hamming Distance, near-duplicate Problem: the problem of elimination of near-duplicate web documents in a generic crawl has not received attention. … 继续阅读
漫话匹配学习(Learning to match) 与Q&A
李航在2012年的一年共做了四篇关于匹配学习的报告，大致内容一致。 2012. 07 mmds_2012 @Stanford University Large Scale Machine Learning for Query Document Matching in Web Search 2012.08 sigir2012_tutorial Beyond Bag of Words Machine Learning for Query-Document Matching in Web Search 2012.08 yssnlp_2012 Learning to Match for Natural Language Processing … 继续阅读
利用solrj API进行微博内容检索
【实验目的】：在172.18.29.185直接调用solrj的API接口完成检索功能，不要使用现成的UI用户界面，不使用web服务。 【参考】：solrj wiki: http://wiki.apache.org/solr/Solrj 【尚有遗留问题】： 测试了本地部署的嵌入服务模式，但一直报错，查了一些网站，还没有找出哪需要配置。 1：关于solr和lucene Lucene是一个使用Java语言写的全文检索开发包（API），利用它可以实现强大的检索功能。 Solr可以说是Lucene下的一个子项目，是一个完完整整地应用。换句话说，它是一个全文检索服务器。Solr目前的客户端面向的有Java、PHP、Python、C#、Json和Ruby等，有了这些客户端，使用者能很方便地将Solr集成到具体运用中。目前最完善的当属Java客户端Solrj。 a)、Solr服务器的配置在solrconfig.xml中完成，包括对缓存，servlet的个性化配置等等，即系统全局的配置； b)、索引方法、索引域（字段）等等在schema.xml中完成，这个配置是针对Solr实例的； [Solr分词顺序]Solr建立索引和对关键词进行查询都得对字串进行分词，在向索引库中添加全文检索类型的索引的时候，Solr会首先用空格进行分词，然后把分词结果依次使用指定的过滤器进行过滤，最后剩下的结果才会加入到索引库中以备查询。分词的顺序如下： 索引 1：空格whitespaceTokenize 2：过滤词StopFilter 3：拆字WordDelimiterFilter 4：小写过滤LowerCaseFilter 5：英文相近词EnglishPorterFilter 6：去除重复词RemoveDuplicatesTokenFilter 查询 1：查询相近词 2：过滤词 3：拆字 4：小写过滤 5：英文相近词 6：去除重复词 以上是针对英文，中文的除了空格，其他都类似 关于schema.xml的配置方法可以借鉴 http://hi.baidu.com/lewutian/item/3d72e939309473bd124b14bd 配置solrconfig.xml，用来配置Solr的一些系统属性，比较重要的一个就是可以通过更改其中的dataDir属性来指定索引文件的存放位置。 [Solr的检索运算符] ? “:” 指定字段查指定值，如返回所有值*:* ? “?” 表示单个任意字符的通配 ? “*” 表示多个任意字符的通配（不能在检索的项开始使用*或者?符号） … 继续阅读