`
Tonyguxu
  • 浏览: 277776 次
  • 性别: 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

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

    字符串匹配算法之Horspool算法

    在此背景下,Boyer和Moore于1977年提出了一种革命性的字符串匹配算法——Boyer-Moore算法,该算法不仅在理论上具有线性时间复杂度的优势,在实际应用中也展现出极高的效率,尤其是在处理长文本和模式时。随后,R....

    字符串匹配算法ppt

    在这个主题中,我们将探讨三种经典的字符串匹配算法:穷举法、KMP(Knuth-Morris-Pratt)算法和BM(Boyer-Moore)算法。 1. **穷举法**:也称为朴素匹配算法,是最直观的字符串匹配方法。它通过比较主串中的每个...

    字符串匹配算法小集(英文)

    ### 字符串匹配算法小集解析 #### 一、引言 本文档提供了一系列共35种不同的字符串匹配算法,这些算法在英文环境下被广泛讨论和应用。通过对这些算法进行详细的解析,我们可以更好地理解每种算法的特点、应用场景...

    PDF电子书《柔性字符串匹配》

    根据提供的信息,《PDF电子书《柔性字符串匹配》》主要探讨了与字符串匹配相关的算法知识。字符串匹配是计算机科学中的一个核心问题,在文本处理、搜索引擎、生物信息学等多个领域都有着广泛的应用。下面将从不同的...

    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算法以其高效的性能在文本搜索、数据挖掘等多个领域广泛应用。 ...

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

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

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

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

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

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

    字符串匹配算法的实现:CPU vs.GPU vs.FPGA.pdf

    字符串匹配算法是计算机科学中一个经典而基础的问题,几乎存在于所有需要处理文本的领域。随着互联网和信息技术的快速发展,人们处理的数据量呈爆炸式增长,这导致了对高效字符串匹配算法的需求日益迫切。传统的串行...

    各种字符串匹配算法--BM,KMP等

    在这个话题中,我们将深入探讨几种经典的字符串匹配算法,包括Bad Character Heuristic(BM算法)和Knuth-Morris-Pratt(KMP算法)。 **Bad Character Heuristic (BM算法)** BM算法是由Sunday和Sunday在1977年提出...

    文件中字符串匹配算法C语言版

    在IT领域,字符串匹配算法是计算机科学中一个基础且重要的概念,特别是在文本处理、搜索引擎和数据挖掘等应用中。本项目关注的是一个C语言实现的文件中字符串匹配算法,其核心目标是读取名为"input.txt"的文件,根据...

    KMP/BM字符串匹配算法源码

    本文将详细解析三种常见的字符串匹配算法:Brute Force(暴力搜索)、KMP(Knuth-Morris-Pratt)以及BM(Boyer-Moore)。这些算法在文本处理、数据搜索、生物信息学等多个领域有着广泛的应用。 首先,让我们来了解...

    Sunday字符串匹配算法

    **Sunday字符串匹配算法详解** Sunday算法,全称为Sunday's Simple String Matching Algorithm,是由E. W. Dijkstra在1976年提出的一种高效字符串匹配算法。这个算法在单字符串匹配领域具有较高的性能,其主要特点...

    KMP算法,全称Knuth-Morris-Pratt字符串搜索算法,是一种线性时间复杂度的字符串匹配算法

    KMP算法,全称Knuth-Morris-Pratt字符串搜索算法,是一种线性时间复杂度的字符串匹配算法。它的主要思想是在发生不匹配时,能知道部分已经匹配的字符序列的后缀和模式串的前缀存在重复,因此可以利用这些信息避免...

    字符串匹配算法(朱泽园)

    ### 字符串匹配算法概述 #### 1. 引言 在信息学竞赛与实际应用领域中,字符串处理占据着极其重要的地位。虽然表面上看似简单的字符串处理问题,却蕴含着丰富的算法思想和技术挑战。本篇文章将详细介绍由ACM金牌...

Global site tag (gtag.js) - Google Analytics