主题:Levenshtein Distance(LD);
相关介绍:Levenshtein distance是由俄国科学家Vladimir Levenshtein在1965年设计并以他的名字命名的。如果不能拼写或发Levenshtein音,通常可以称它edit distance(编辑距离);
用途:该算法用于判断两个字符串的距离,或者叫模糊度。个人理解就是差异程度。而差异的标准就是1)加一个字母(Insert),2)删一个字母(Delete),3改变一个字母(Substitute)。
算法描述:
Step
|
Description
|
1
|
Set n to be the length of s.Set m to be the length of t. If n = 0, return m and exit.If m = 0, return n and exit. Construct a matrix containing 0..m rows and 0..n columns.
|
2
|
Initialize the first row to 0..n. Initialize the first column to 0..m.
|
3
|
Examine each character of s (I from 1 to n).
|
4
|
Examine each character of t (j from 1 to m).
|
5
|
If s[i] equals t[j], the cost is 0. If s[i] doesn’t equal t[j], the cost is 1.
|
6
|
Set cell d[I,j] of the matrix equal to the minimum of: a. The cell immediately above plus 1: d[i-1,j] + 1. b. The cell immediately to the left plus 1: d[I,j-1] + 1. c. The cell diagonally above and to the left plus the cost: d[i-1,j-1] + cost.
|
7
|
After the iteration steps (3, 4, 5, 6) are complete, the distance is found in cell d[n,m].
|
1、 得到源串s长度n与目标串t的长度m,如果一方为的长度0,则返回另一方的长度。
2、 初始化(n+1)*(m+1)的矩阵d,第一行第一列的值为0增至对应的长度。
3、 遍历数组中的每一个字符(i,j从1开始)。如果s[i]与t[j]的值相等,cost值为0,否则为1。D[i][j]的值为d[i-1,j] + 1(左边的值加1)、d[I,j-1] + 1.(上边的值加1)、d[i-1,j-1] + cost (斜上角的值加cost) 中的最小者。
4、 等第三步遍历完后,右下角d[n,m]的值就为两个字符串的距离。
应用演示:source:word与target:world比较过程。
应用举例:据《开发自己的搜索引擎——Lucene 2.0+Heriterx
》记载P134页记载,lucene中FuzzyQuery(模糊匹配)就是应用该算法的;也可用于Spell checking(拼写检查),Speech recognition(语句识别),DNA analysis(DNA分析) ,Plagiarism detection(抄袭检测)。
分享到:
相关推荐
lucene实例lucene实例lucene实例lucene实例lucene实例lucene实例lucene实例lucene实例lucene实例
lucene,lucene教程,lucene讲解。 为了对文档进行索引,Lucene 提供了五个基础的类 public class IndexWriter org.apache.lucene.index.IndexWriter public abstract class Directory org.apache.lucene.store....
lucene3.0 lucene3.0 lucene3.0 lucene3.0 lucene3.0
lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习...
Lucene3.0特性Lucene3.0特性
赠送jar包:lucene-core-7.7.0.jar; 赠送原API文档:lucene-core-7.7.0-javadoc.jar; 赠送源代码:lucene-core-7.7.0-sources.jar; 赠送Maven依赖信息文件:lucene-core-7.7.0.pom; 包含翻译后的API文档:lucene...
赠送jar包:lucene-core-7.2.1.jar; 赠送原API文档:lucene-core-7.2.1-javadoc.jar; 赠送源代码:lucene-core-7.2.1-sources.jar; 赠送Maven依赖信息文件:lucene-core-7.2.1.pom; 包含翻译后的API文档:lucene...
lucene.NET 中文分词 高亮 lucene.NET 中文分词 高亮 lucene.NET 中文分词 高亮 lucene.NET 中文分词 高亮
本课程由浅入深的介绍了Lucene4的发展历史,开发环境搭建,分析lucene4的中文分词原理,深入讲了lucenne4的系统架构,分析lucene4索引实现原理及性能优化,了解关于lucene4的搜索算法优化及利用java结合lucene4实现...
lucene-analyzers-common-4.2.0.jar; lucene-analyzers-kuromoji-4.2.0.jar; lucene-analyzers-phonetic-4.2.0.jar; lucene-codecs-4.2.0.jar; lucene-core-4.2.0.jar; lucene-grouping-4.2.0.jar; lucene-...
lucene学习教程lucene讲义 叫你用lucene算法
lucene3源码分析
本书深入浅出地介绍了Lucene——一个开源的使用Java语言编写的全文搜索引擎开发包。它通过浅显的语言、大量的图注、丰富的代码示例,以及清晰的结构为读者呈现出作为优秀开源项目的Lucene 所体现的强大功能。全书共...
lucenetest.rar,lucene,全文检索,lucene例子 lucenetest.rar,lucene,全文检索,lucene例子lucenetest.rar,lucene,全文检索,lucene例子
赠送jar包:lucene-core-6.6.0.jar; 赠送原API文档:lucene-core-6.6.0-javadoc.jar; 赠送源代码:lucene-core-6.6.0-sources.jar; 赠送Maven依赖信息文件:lucene-core-6.6.0.pom; 包含翻译后的API文档:lucene...
Lucene3.5全部源码,打包jar文件,可以直接打开查看源码,Lucene开发必备
c#下实现Lucene时间区间查询匹配。主要还是对Lucene查循对像Query的实现
Annotated Lucene 中文版 Lucene源码剖析
lucene-core-2.9.4,lucene-core-3.0.2,lucene-core-3.0.3,lucene-core-3.4.0
《Lucene实战(第2版)》基于Apache的Lucene 3.0,从Lucene核心、Lucene应用、案例分析3个方面详细系统地介绍了Lucene,包括认识Lucene、建立索引、为应用程序添加搜索功能、高级搜索技术、扩展搜索、使用Tika提取文本...