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

编辑距离

 
阅读更多

1.Levenshtein distance(以下简称L氏距离)。 此距离由Levenshtein 于1965年定义,在这个定义体系中有三种原子操作:insertion,deletion,substitution(出处见论文《BINARY CODES CAPABLE OF CORRECTING,DELETIONS,INSERTIONS AND REVERSALS》);

2.Damerau,F,J distance(以下简称D氏距离)。此距离有Damerau于1964年定义,在这个定义体系中有四种原子操作:insertion,deletion,substitution,以及transpositionof ajacent symbols(出处见论文《A Technique for Computer Detection and Correction of Spelling Errors》);

两种定义的区别:

1.L氏距离的原子操作集中不包括相邻交换这个操作;

2.根据wiki上介绍:L氏距离可以处理多重编辑错误,而D式距离只能处理单一的编辑错误。

 

综上:

如果利用L氏编辑距离计算abc与ca之间的编辑距离,结果应该是3(删除b->原字符串开头的a被替换为c->原字符串结尾的c被替换为a),这个是没有任何异议的;如果根据D氏距离计算abc与ca之间的编辑距离应该为2(删除b->原字符串首尾的字符a与c交换位置),现在问题就出来了:很多书籍和论文(例如 Kemal Oflazor 的《Error-tolerant Finite-state Recognition with Application to Morphological Analysis and Spelling Correction》,M.W.Du and S.C.Chang的《A model and a fast algorithm for multiple errors spelliing correction》)中采用了D氏编辑距离的定义,然后又紧接着给出了如下的计算公式:

 

image

公式1:以上两篇论文中提供的编辑距离计算公式。

 

根据此计算公式得到的计算结果也是3。

这个时候很多会说,因为得出2的结果的时候,先删除中间的b,没有满足“顺序操作”所以得到错误的结果。对于字符串abc的正确处理顺序应该是先处理a,然后处理b,然后处理c。正确的计算应该是:删除a->b换成c->c换成a。但是编辑距离应该是满足对称性的。也就是说abc与ca的编辑距离等于ca与abc的编辑距离。ca变成abc可以经过如下步骤:ca->ac,ac中间插入b。因此这种说法是不太合理的,况且编辑距离的定义只是对现实情况的一种数学抽象,不考虑程序设计问题,和“顺序流”之间没有多大关系。

 

这个问题困扰了我很长时间,今天通过查wiki才知道了事情的来龙去脉:大体情况是这样的,L和D自己对编辑距离的定义是没有问题的,符合泛函理论中对距离定义的三个要素条件。后来一些人就想将L和D的距离定义融合在一起,成为了Damerau–Levenshtein distance(以下简称D-L距离),认为这样就既可以克服了D定义只能识别单一编辑操作引起的错误的局限,又弥补了L定义不包含相邻字符互换操作的遗憾。其实上面的公式1计算的就是D-L距离。但是这个D-L距离并不满足泛函理论中所要求的距离定义的三要素标准,它不满足三角不等式,所以这个定义是有问题的,数学上具有不严谨性。于是也就有了将abc与ca的编辑距离错算为3的情况。但是由于这个错误并不影响工程中的应用,并且这个公式能够给实际工作带来便利,就一直沿用了下来。

分享到:
评论

相关推荐

    编辑距离算法的总结和分析

    编辑距离算法,也称为Levenshtein距离,是计算两个字符串之间差异的一种度量方法,广泛应用于文本处理、拼写纠正、生物信息学等领域。它通过衡量将一个字符串转换为另一个字符串所需的最少单字符操作数(包括删除、...

    SQL SERVER实现编辑距离(Edit Distance)算法

    编辑距离(Edit Distance)算法,也被称作Levenshtein距离算法,是一种用于字符串之间模糊匹配的常用方法。在SQL Server数据库中,我们可以通过创建一个函数来实现Levenshtein距离算法,进而进行字符串的比较和...

    编辑距离问题-算法导论.pdf

    编辑距离问题-算法导论 在计算机科学中,编辑距离问题是指将一个字符串转换成另一个字符串所需的最少操作步骤数。这些操作可以是插入、删除、替换和复制字符。编辑距离问题是一种典型的动态规划问题。 动态规划是...

    c或c++中求编辑距离的程序代码

    编辑距离(Edit Distance)是一种衡量两个字符串相似度的算法,广泛应用于文本处理、生物信息学等领域。这个算法基于动态规划的思想,计算出将一个字符串转换为另一个字符串所需要的最少操作次数,包括插入、删除和...

    编辑距离 字符串的相似度

    编辑距离(Edit Distance)是一种衡量两个字符串相似度的数学概念,它定义了将一个字符串转换成另一个字符串所需的最少单字符操作次数,包括插入、删除和替换。这些操作在自然语言处理(NLP)中有着广泛的应用,比如...

    计算两字符串的编辑距离

    编辑距离,又称Levenshtein距离,是一种衡量两个字符串相似度的指标,广泛应用于文本处理、数据校验、搜索引擎优化等多个领域。这个概念源于俄国科学家瓦迪姆·列文斯坦在1965年提出,它定义了将一个字符串转换成另...

    树编辑距离的 Python APTED算法_python_代码_下载

    这是 APTED 算法的 Python 实现,它是计算树编辑距离的最先进的解决方案 ,它取代了 RTED 算法 输入 目前,我们只支持输入树的所谓括号表示法,例如,编码{A{B{X}{Y}{F}}{C}}对应于以下树: A / \ B C /|\ X Y...

    一种编辑距离算法及其在网页搜索中的应用

    ### 编辑距离算法及其在网页搜索中的应用 #### 概述 在互联网时代,搜索引擎作为获取信息的主要工具之一,其核心竞争力在于如何更准确、更高效地将用户查询与相关网页进行匹配。传统的相关性排序算法往往侧重于...

    编辑距离JS算法

    ### 编辑距离JS算法详解 #### 一、编辑距离概念 编辑距离(Edit Distance),又称Levenshtein距离,是一种衡量两个字符串相似度的方法。它定义为通过插入、删除或替换一个字符的方式将一个字符串转换成另一个字符串...

    编辑距离原代码 根据编的

    编辑距离,又称Levenshtein距离,是一种衡量两个字符串相似度的度量方式。这个概念在计算机科学,尤其是文本处理、信息检索和生物信息学等领域有着广泛应用。原码(或称为原始代码)指的是程序员最初编写,未经任何...

    动态规划解决编辑距离问题

    编辑距离,又称为Levenshtein距离,是度量空间中的一个重要概念,它衡量了两个字符串通过插入、删除或替换操作相互转换所需的最小步骤数。在这个问题中,我们将深入探讨动态规划如何有效地计算编辑距离。 编辑距离...

    编辑距离的详细讲解

    ### 编辑距离详解 #### 一、编辑距离的基本概念 **编辑距离**(Edit Distance),也称为Levenshtein距离,是一种衡量两个序列相似度的方法。它定义为通过一系列预定义的操作(如插入、删除或替换一个字符)将一个...

    编辑距离问题 对于给定的字符串A和字符串B,编程计算其编辑距离d(A,B)。

    ### 编辑距离问题 #### 一、问题背景与定义 在计算机科学领域,编辑距离(Edit Distance)是一个衡量两个字符串相似度的重要概念。编辑距离指的是通过一系列预定义的操作(如插入、删除或替换字符)将一个字符串...

    基于编辑距离的拼写矫正算法

    **基于编辑距离的拼写矫正算法** 在计算机科学和自然语言处理领域,拼写矫正是一项重要的任务,尤其在文本输入、搜索引擎优化、机器翻译等方面有着广泛的应用。编辑距离(Edit Distance)是解决这一问题的一种经典...

    编辑距离问题-------txt

    ### 编辑距离问题解析 #### 一、问题定义与背景 编辑距离(Edit Distance),又称Levenshtein距离,是一种衡量两个字符串相似度的方法。它定义了将一个字符串转换成另一个字符串所需的最少单字符编辑操作次数。...

    动态规划之编辑距离问题

    动态规划之编辑距离问题 编辑距离问题是计算机科学中一个经典问题,旨在寻找将一个字符串转换为另一个字符串所需的最少操作数。这个问题可以通过动态规划算法来解决,下面将对其进行详细的解释。 问题描述 编辑...

    Python-Levenshtein快速计算编辑距离以及字符串的相似度

    在Python编程环境中,Levenshtein库是一个非常实用的工具,用于计算两个字符串之间的编辑距离。编辑距离,也称为Levenshtein距离,是衡量两个字符串差异的一种度量,定义为由一个字符串转换成另一个字符串最少的单...

    编辑距离EditDistance

    **编辑距离(Edit Distance)** 编辑距离,也称为Levenshtein距离,是一种衡量两个字符串相似度的方法。在计算机科学和信息学中,它被广泛应用于文本比较、拼写检查、生物信息学等领域。编辑距离定义为从一个字符串...

    编辑距离算法例子

    编辑距离算法,也被称为Levenshtein距离,是一种衡量两个字符串相似度的度量方法。在信息技术、自然语言处理和生物信息学等领域有着广泛应用。它定义了将一个字符串转换成另一个字符串所需的最少单字符编辑操作次数...

    算法设计编辑距离问题

    ### 编辑距离问题解析与算法实现 #### 一、问题背景及定义 **编辑距离**(Edit Distance),也称为Levenshtein Distance,是一种衡量两个字符串相似度的方法,即通过最少的操作次数(如插入、删除或替换字符)将一个...

Global site tag (gtag.js) - Google Analytics