`
Tonyguxu
  • 浏览: 278482 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

字符串匹配算法——Edit distance

 
阅读更多

如何比较两个字符串之间的相似程度(或者差异)?


想要比较两个字符串之间的相似程度,可以看其中一个字符串通过几步操作可以转换为另一个字符串,通过度量转换操作的步数可以来衡量两个串的相似程度,如果转换步数越少,则两者越匹配。这里转换操作的度量就称为:

edit distance。该值越小,则两个字符串越匹配。

 

但是对edit distance有不同的definition

 

 http://en.wikipedia.org/wiki/Edit_distance写道
edit distance between two strings of characters generally refers to the Levenshtein distance.

However,The term ‘edit distance’ is sometimes used to refer to the distance in which insertions and deletions have equal cost and replacements have twice the cost of an insertion”

There are several different ways to define an edit distance, depending on which edit operations are allowed: replace, delete, insert, transpose, and so on.
  

 

相应的也有不同的算法来计算这个值,常见的有Levenshtein distance

 

Levenshtein distance

 

http://en.wikipedia.org/wiki/Levenshtein_distance 写道
The Levenshtein distance between two strings is defined as the minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character.
 

算法基本步骤

 

 

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].

 

 

比较"GUMBO"和"GAMBOL"的相似程度,计算两者的edit distance


 

参考

 

1.Levenshtein_distance

http://www.merriampark.com/ld.htm

http://en.wikipedia.org/wiki/Levenshtein_distance

2.Edit_distance

http://en.wikipedia.org/wiki/Edit_distance

 

 

 

  • 描述: Levenshtein distance算法示例
  • 大小: 387.1 KB
分享到:
评论

相关推荐

    比KMP更快的字符串匹配算法——BM算法,排序算法数据结构 最快的排序算法

    BM算法是比KMP更快的字符串匹配算法,它的理论时间复杂度也是O(n+m),但实际上它的平均速度比KMP快很多。BM算法的原理是考虑O(nm)的暴力对比进进行字符串匹配,我们总是希望某次失配后能根据已有信息进行尽可能多的...

    带通配符的字符串匹配算法

    带通配符的字符串匹配算法则是这个领域的延伸,它允许在模式字符串中包含特殊字符,如星号(*)或问号(?),以表示任意字符或单个任意字符。这种算法使得搜索更加灵活,可以适应更复杂的查询需求。 **通配符的含义** -...

    串匹配算法——kmp算法,并行算法

    在并行计算领域,串匹配算法也可以利用MPI(Message Passing Interface)进行分布式处理,将大文本字符串分割成多个部分,每个计算节点独立运行KMP算法,然后汇总结果。这种方法可以极大地提高处理大规模数据的效率...

    字符串的模式匹配算法——KMP

    字符串的模式匹配算法在计算机科学中占据着重要的地位,它主要应用于文本搜索、数据分析和文本处理等领域。KMP(Knuth-Morris-Pratt)算法是其中一种高效的算法,尤其适用于处理具有重复子串的模式匹配问题。接下来...

    多模式的字符串匹配算法--AC_BM算法的实现代码

    《多模式字符串匹配算法——AC_BM算法的深度解析与实现》 字符串匹配算法是计算机科学中的一个重要领域,尤其在文本处理、搜索引擎、数据挖掘等领域有着广泛应用。其中,AC_BM算法,即Aho-Corasick算法结合Boyer-...

    字符串匹配算法C代码实现

    本篇文章将详细探讨四种常见的字符串匹配算法:平凡算法(SimpleSM)、KMP算法(KMPSM)、BM算法(bmSM)以及RK算法(rkSM),并分析它们的基本原理和C代码实现。 1. **平凡算法(SimpleSM)** 平凡算法是最基础的...

    字符串匹配算法ppt

    常见的字符串匹配算法及实现

    字符串匹配算法总结

    在不匹配时,算法会查找模式串中不匹配字符的位置,从而快速调整模式串的位置。这种方法减少了不必要的移动次数,提高了效率。 4. **Boyer-Moore算法**:Boyer和Moore设计的算法结合了bad-character heuristics和...

    字符串匹配算法_朴素字符串匹配算法

    一般而言文本就是要编辑的文档,而模式字符串往往由用户来指定,高效的字符串匹配 算法可以提高程序的响应性能,当然字符串匹配算法的应用远远不止于此,例如在生物计算科学中查找特定的DNA序列,也是字符串匹配算法...

    算法与数据结构 算法分析课程 第11章 字符串匹配 字符串匹配算法 KMP算法 共11页.pptx

    本章节将重点介绍字符串匹配的基本概念以及两种重要的算法——简单字符串匹配算法和KMP算法。 #### 一、简单字符串匹配算法 简单字符串匹配算法是最基础的一种方法,其基本思想是从文本串的第一个字符开始,逐个...

    实现并对比三种基本的字符串匹配算法

    首先对三种基本字符串匹配算法进行了详细分析和说明,再编程实现。创新拓展研究了Boyer-Moore算法,进行了分析和编程实现。让四种算法对数据量极大的文本,进行子串的查询处理,并分析算法运行时间效率,并对所有...

    C++ 字符串匹配

    在这一篇文章中,我们将详细介绍 C++ 中的字符串匹配算法,主要包括 Brute Force 算法和其他一些常见的字符串匹配算法。 Brute Force 算法 Brute Force 算法是最简单的字符串匹配算法,它的思想是将模式串与主串...

    KMP算法:高效字符串匹配算法详解

    KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为“部分匹配表”或“next数组”的数组来减少字符串匹配过程中的...

    用C++实现BM的字符串模式匹配算法

    本篇文章将深入探讨如何使用C++实现Bad Character Rule(坏字符规则)和Good Suffix Rule(好后缀规则)来优化Boyer-Moore(BM)字符串匹配算法。BM算法以其高效的性能在文本搜索、数据挖掘等多个领域广泛应用。 ...

    KMP.rar_KMP_KMP算法_visual c_字符串匹配_字符串匹配算法

    KMP算法,全称为Knuth-Morris-Pratt算法,是一种高效的字符串匹配算法,由Donald Knuth、James H. Morris和 Vaughan Pratt三位学者在1970年代提出。该算法在处理字符串匹配问题时,避免了不必要的回溯,极大地提高了...

    一种改进的字符串匹配算法

    ### 一种改进的字符串匹配算法:KMP算法详解 #### KMP算法简介 KMP算法是一种高效的字符串匹配算法,由D.E.Knuth、V.R.Pratt和J.H.Morris三位计算机科学家共同发现,因此得名为Knuth-Morris-Pratt算法(简称KMP...

    2.KMP算法:高效字符串匹配算法详解

    KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为“部分匹配表”或“next数组”的数组来减少字符串匹配过程中的...

    字符串匹配之BM算法(英文)

    BM算法,全称为Boyer-Moore字符串搜索算法,是一种高效的字符串匹配算法。该算法由Robert Boyer和J Strother Moore提出,主要用于在一个主字符串(text)中查找模式字符串(pattern)的出现位置。BM算法的核心思想...

    C++字符串匹配算法理解(从BF算法到KMP算法)

    KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的...

    基于字符串模式匹配算法的病毒感染检测问题_算法_数据结构_

    字符串模式匹配算法在此过程中扮演了核心角色,因为它可以高效地查找可能的病毒签名或恶意代码序列。本话题将深入探讨如何利用C语言实现基于字符串模式匹配算法的病毒感染检测。 首先,我们需要了解字符串模式匹配...

Global site tag (gtag.js) - Google Analytics