热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

序列和集合算法之序列比较

将一个序列变成另一个序列的最少修改步数。例如下图,将字符串A变成字符串B,所需要的步骤为6个步骤,match表示0步,其他操作表示1步:设计算法如下:publicsealedc

将一个序列变成另一个序列的最少修改步数。

例如下图,将字符串A变成字符串B,所需要的步骤为6个步骤,match表示0步,其他操作表示1步:

设计算法如下:

    public sealed class MinimumEditDistance
{
public int[,] CalculateDistance(string originalStr, String targetStr)
{
int LenA = originalStr.Length;
int LenB = targetStr.Length;
int[,] C = new int[LenA + 1, LenB + 1];
for (int i = 0; i <= LenA; C[i, 0] = i, i++) ;//targetStr为空串时的边界条件
for (int j = 0; j <= LenB; C[0, j] = j, j++) ;//originalStr为空串时的边界条件
for (int i = 1; i <= LenA; i++)
{
for (int j = 1; j <= LenB; j++)
{
//删除:考虑C[i-1,j],即i-1时已经达到最好情况,新添加的第i个字符需要删除掉
int candidateDel = C[i - 1, j] + 1;
//插入:考虑C[i,j-1],即已经在i的情况下能够达到j-1时的最好情况,此时如果考虑j的情况就是直接插入第j个字符
int candidateIns = C[i, j - 1] + 1;
//匹配:考虑C[i-1,j-1],即在i-1,j-1的情况下已经得到最好值,并且新近考虑的i和j字符相同,则无需任何额外动作
// int candidate = C[i-1, j-1];
//替换:考虑C[i-1,j-1],即在i-1,j-1的情况下已经得到最好值,并且新近考虑的i和j字符不相同,则需一次替换额外动作
//int candidate = C[i - 1, j - 1]+1;
int candidateMatRep;
if (char.Equals(originalStr[i - 1], targetStr[j - 1]))
{
candidateMatRep
= C[i - 1, j - 1];
}
else
{
candidateMatRep
= C[i - 1, j - 1] + 1;
}
//三者取最小代价
C[i, j] = Math.Min(Math.Min(candidateDel, candidateIns), candidateMatRep);
}
}
return C;
}
public List GetPossibleDesicion(int[,] C, int row, int col)
{
List
lo = new List();

for (int i = row, j = col; i > 0 || j > 0; )
{
if (C[i, j] == C[i - 1, j] + 1)//删除
{
lo.Add(
new OperationOnOriginalStr(Operation.Delete, i-1));
i
--;
}
else if (C[i, j] == C[i, j - 1] + 1) //插入
{
lo.Add(
new OperationOnOriginalStr(Operation.Insert, i-1, j-1));
j
--;
}
else if (C[i, j] == C[i - 1, j - 1])//匹配
{
lo.Add(
new OperationOnOriginalStr(Operation.Match, i-1,j-1));
i
--;
j
--;
}
else //替换
{
lo.Add(
new OperationOnOriginalStr(Operation.Replace, i-1, j-1));
i
--;
j
--;
}
}

return lo.Reverse().ToList();
}
}
public enum Operation
{
Delete,
Insert,
Replace,
Match
}
public class OperationOnOriginalStr
{
public OperationOnOriginalStr(Operation op, int aindex, int? bindex = null)
{
operation
= op;
AIndex
= aindex;
BIndex
= bindex;
}
public Operation operation { get; set; }
public int AIndex { get; set; }
public int? BIndex { get; set; }
}

调用方法如下:

            MinimumEditDistance med = new MinimumEditDistance();
var C = med.CalculateDistance(A, B);
var steps = med.GetPossibleDesicion(C, A.Length, B.Length);
steps.ForEach(s
=> Console.WriteLine("Operation:{0},A[{1}],B[{2}]", s.operation, s.AIndex, s.BIndex));

 

作者:Andy Zeng

欢迎任何形式的转载,但请务必注明出处。

http://www.cnblogs.com/andyzeng/p/3736012.html


推荐阅读
  • 本指南从零开始介绍Scala编程语言的基础知识,重点讲解了Scala解释器REPL(读取-求值-打印-循环)的使用方法。REPL是Scala开发中的重要工具,能够帮助初学者快速理解和实践Scala的基本语法和特性。通过详细的示例和练习,读者将能够熟练掌握Scala的基础概念和编程技巧。 ... [详细]
  • 计算机视觉领域介绍 | 自然语言驱动的跨模态行人重识别前沿技术综述(上篇)
    本文介绍了计算机视觉领域的最新进展,特别是自然语言驱动的跨模态行人重识别技术。上篇内容详细探讨了该领域的基础理论、关键技术及当前的研究热点,为读者提供了全面的概述。 ... [详细]
  • 2018年9月21日,Destoon官方发布了安全更新,修复了一个由用户“索马里的海贼”报告的前端GETShell漏洞。该漏洞存在于20180827版本的某CMS中,攻击者可以通过构造特定的HTTP请求,利用该漏洞在服务器上执行任意代码,从而获得对系统的控制权。此次更新建议所有用户尽快升级至最新版本,以确保系统的安全性。 ... [详细]
  • 本文介绍了UUID(通用唯一标识符)的概念及其在JavaScript中生成Java兼容UUID的代码实现与优化技巧。UUID是一个128位的唯一标识符,广泛应用于分布式系统中以确保唯一性。文章详细探讨了如何利用JavaScript生成符合Java标准的UUID,并提供了多种优化方法,以提高生成效率和兼容性。 ... [详细]
  • 哈希表(Hash Table)是一种高效的查找算法,与传统的链表和树结构相比,其在查找过程中无需进行逐个元素的比较。本文将深入探讨哈希表的基本原理、应用场景以及优化策略,帮助读者全面理解其在实际开发中的优势和局限性。通过实例分析和代码示例,我们将展示如何有效利用哈希表提高数据处理效率,并解决常见的冲突问题。 ... [详细]
  • 在Python中,是否可以通过使用Tkinter或ttk库创建一个具有自动换行功能的多行标签,并使其宽度能够随着父容器的变化而动态调整?例如,在调整NotePad窗口宽度时,实现类似记事本的自动换行效果。这种功能在设计需要显示长文本的对话框时非常有用,确保文本内容能够完整且美观地展示。 ... [详细]
  • 本文详细介绍了 jQuery 的入门知识与实战应用,首先讲解了如何引入 jQuery 库及入口函数的使用方法,为初学者提供了清晰的操作指南。此外,还深入探讨了 jQuery 在实际项目中的多种应用场景,包括 DOM 操作、事件处理和 AJAX 请求等,帮助读者全面掌握 jQuery 的核心功能与技巧。 ... [详细]
  • 在使用 `useSelector` 选择器时,发现分派操作后状态未能实时更新。这可能是由于 React 组件的渲染机制或 Redux 的状态管理问题导致的。建议检查 `useSelector` 的依赖项和 `dispatch` 的调用时机,确保状态变化能够正确触发组件重新渲染。此外,可以考虑使用 `useEffect` 钩子来监听状态变化,以确保及时更新。 ... [详细]
  • 本文探讨了基于点集估算图像区域的Alpha形状算法在Python中的应用。通过改进传统的Delaunay三角剖分方法,该算法能够生成更加灵活和精确的形状轮廓,避免了单纯使用Delaunay三角剖分时可能出现的过大三角形问题。这种“模糊Delaunay三角剖分”技术不仅提高了形状的准确性,还增强了对复杂图像区域的适应能力。 ... [详细]
  • 本文详细介绍了使用C++实现插入排序算法的方法,并对其进行了优化。通过具体的代码示例,解释了插入排序的基本原理和优化技巧,包括交换两个元素的函数 `SwapTwo` 的实现。此外,文章还探讨了插入排序的时间复杂度和适用场景,为读者提供了深入理解该算法的全面指南。 ... [详细]
  • Eclipse JFace Text框架中IDocument接口的getNumberOfLines方法详解与编程实例 ... [详细]
  • 本文总结了JavaScript的核心知识点和实用技巧,涵盖了变量声明、DOM操作、事件处理等重要方面。例如,通过`event.srcElement`获取触发事件的元素,并使用`alert`显示其HTML结构;利用`innerText`和`innerHTML`属性分别设置和获取文本内容及HTML内容。此外,还介绍了如何在表单中动态生成和操作``元素,以便更好地处理用户输入。这些技巧对于提升前端开发效率和代码质量具有重要意义。 ... [详细]
  • 在过去,我曾使用过自建MySQL服务器中的MyISAM和InnoDB存储引擎(也曾尝试过Memory引擎)。今年初,我开始转向阿里云的关系型数据库服务,并深入研究了其高效的压缩存储引擎TokuDB。TokuDB在数据压缩和处理大规模数据集方面表现出色,显著提升了存储效率和查询性能。通过实际应用,我发现TokuDB不仅能够有效减少存储成本,还能显著提高数据处理速度,特别适用于高并发和大数据量的场景。 ... [详细]
  • 在 Windows 10 环境中,通过配置 Visual Studio Code (VSCode) 实现基于 Windows Subsystem for Linux (WSL) 的 C++ 开发,并启用智能代码提示功能。具体步骤包括安装 VSCode 及其相关插件,如 CCIntelliSense、TabNine 和 BracketPairColorizer,确保在 WSL 中顺利进行开发工作。此外,还详细介绍了如何在 Windows 10 中启用和配置 WSL,以实现无缝的跨平台开发体验。 ... [详细]
  • 在数据表中,我需要触发一个操作来刷新特定列的数据。例如,对于以下表格:| ID | Name | IsDeleted ||----|-------|-----------|| 1 | test | True || 2 | test2 | False |我希望在点击“更新”按钮时,能够仅刷新选定行的“IsDeleted”列。这将有助于确保数据的实时性和准确性。 ... [详细]
author-avatar
QueenieYam任嘉明
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有