编辑距离问题
#include
#include
#include
using namespace std;
int min(int a, int b)
{
return a < b ? a : b;
}
int edit(string str1, string str2)
{
int max1 = str1.size();
int max2 = str2.size();
int **ptr = new int*[max1 + 1];
for (int i = 0; i < max1 + 1; i++)
{
ptr[i] = new int[max2 + 1];
}
for (int i = 0; i < max1 + 1; i++){
ptr[i][0] = i;
}
for (int i = 0; i < max2 + 1; i++){
ptr[0][i] = i;
}
for (int i = 1; i < max1 + 1; i++){
for (int j = 1; j < max2 + 1; j++){
int d;
int temp = min(ptr[i - 1][j] + 1, ptr[i][j - 1] + 1);
if (str1[i - 1] == str2[j - 1])
{
d = 0;
}
else
{
d = 1;
}
ptr[i][j] = min(temp, ptr[i - 1][j - 1] + d);
}
}
cout << "*****************************" << endl;
for (int i = 0; i < max1 + 1; i++)
{
for (int j = 0; j < max2 + 1; j++)
{
cout << ptr[i][j] << " ";
}
cout << endl;
}
cout << "*****************************" << endl;
int dis = ptr[max1][max2];
for (int i = 0; i < max1 + 1; i++)
{
delete[] ptr[i];
ptr[i] = NULL;
}
delete[] ptr;
ptr = NULL;
return dis;
}
int main(void)
{
string str1, str2;
ifstream ist("input.txt");
getline(ist, str1);
getline(ist, str2);
int r = edit(str1, str2);
ofstream ost("output.txt");
ost << r;
cout << "the dis is: " << r << endl;
system("pause");
}
算法设计动态规划(编辑距离)
《算法设计与分析》课程报告 课题名称：动态规划——编辑距离问题 课题负责人名（学号）： 同组成员名单（角色）：无 指导教师：左劼 评阅成绩： 评阅意见： 提交报告时间：2010 年 6月23日
动态规划——编辑距离问题 计算机科学与技术专业 学生指导老师左劼 [ 摘要 ]动态规划的基本思想与分治法类似，也是将待求解的问题分解成 若干份的子问题，先分别解决好子问题，然后从子问题中得到最终解。但动态规 划中的子问题往往不是相互独立的，而是彼此之间有影响，因为有些子问题可能 要重复计算多次，所以利用动态规划使这些子问题只计算一次。将字符串 A 变换为字符串所用的最少字符操作数称为字符串 A 到 B 的编辑距离。 关键词：动态规划矩阵字符串操作数编辑距离
一、问题描述 1、基本概念：设 A 和 B 是 2 个字符串。要用最少的字符操作将字 符串 A 转换为字符串 B 。字符串操作包括： (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。 将字符串 A 变换为字符串 B 所用的最少字符操作数称为字符串A 到 B 的编辑距离，记为d(A,B) 。 2、算法设计：设计一个有效算法，对于给定的任意两个字符串A 和 B ，计算其编辑距离d(A,B) 。 3、数据输入：输入数据由文件名为input.txt 的文本文件提供。文 件的第 1 行为字符串 A ，第二行为字符串 B 。 4、结果输出：将编辑距离d(A,B) 输出到文件ouput.txt 的第一行。 输入文件示例输出文件示例 input.txt output.txt fxpimu5 xwrs 二、分析 对于本问题，大体思路为：把求解编辑距离分为字符串A从0个字符逐渐增加到全部字符分别想要变为字符串 B 该如何变化以及变化的最短距离。 具体来说，首先选用数组a1 存储字符串A( 设长度为n)，a2 存储字符串 B( 设长度为m) ，d 矩阵来进行具体的运算；这里有两个特殊情况比较简单可以单独考虑，即A的长度为0而B不为 0还有 A 不为 0B 为 0，这两种情况最后的编辑距离分别为m 和 n；讨论一般情况， d 矩阵为 d[n][m] ，假定我们从 d[0][0] 开始一直进行以下操作到了 d[i][j] 的 位置，其中删除操作肯定是 A 比 B 长，同理，插入字符操作一定是 A 比 B 短，更改字符操作说明一样长，我们所要做的是对d[i][j-1]
编辑距离算法的优化与实现
编辑距离算法的优化与 实现 SANY GROUP system office room 【SANYUA16H-
编辑距离算法的优化与实现摘要：在分析基于动态规划的编辑距离算法对文本相似度计算的不足的基础上，利用数据结构在空间效率和时间效率上优化该算法、采用中文分词的思想优化和改善该算法的时间效率和准确率，克服了原有的基于动态规划的计算方法所具有的效率低、准确率低、耗内存高的缺点。通过多种优化方案的实验测试和分析，结果表明优化后的算法取得了很好的准确率和时空效率，更好的用于文本相似度计算。 关键词：编辑距离算法；文本相似度计算；算法优化；动态规划 1引言 文本相似度的计算在信息检索、文本分类、知识挖掘、网页去重、问答系统等诸多领域有着极为广泛的应用，长期以来一直是研究的热点和难点。人们在文本相似度计算中使用编辑距离算法，但该方法单纯以字为单位计算各个字符之间的编辑距离，插入删除替换三种基本操作的代价值的方法不够明确合理，从而使计算结果存在一定的偏差。故对传统的文本相似度检测编辑距离算法进行优化和改善，提出了一种基于改进编辑距离和中文分词相融合的计算文本相似度的方法，使优化改善后的算法具有较高的准确率和效率、较低的存储空间，更符合文本相似度计算的要求，有效提高文本相似度算法的效率和准确性，使文本相似度计算的性能进一步改善。
2编辑距离算法 4.3.1编辑距离定义 编辑距离又称Levenshtein距离（也叫做EditDistance），是由俄国科学家VladimirLevenshtein于1965年在文献[1]中提出的，是一种常用的距离函数度量方法，在多个领域特别是文本相似度检测得到了广泛的应用。编辑距离是指两系列字符串之间只能通过插入、删除和替换三种基本操作把源字符串（S）转换成目标字符串（T）所需的最少基本操作次数。编辑距离值越大，则相似度越小。 4.3.2编辑距离算法原理 对于求两个字符串之间的编辑距离实际上可以转化为一个求最优解的问题，可以利用动态规划的思想[2]来计算，计算原理的步骤如下表2-1所示： 表2-1编辑距离算法原理的计算步骤
2.4最小编辑距离
2.4.1最小编辑距离 我们如何找到最小的编辑距离？我们可以把它看作是一个搜索任务，在这个任务中，我们在寻找最短路径——从一个字符串到另一个字符串的编辑序列。 图2.13 将查找编辑距离视为搜索问题 所有可能编辑的空间是巨大的，所以我们不能简单地搜索。然而，许多不同的编辑路径最终会以相同的状态（字符串）结束，所以我们不必重写所有这些路径，我们只需要记住到达每一状态的最短路径就可以。我们可以通过使用动态规划来做到这一点。BELLMAN（1957）首先提出动态规划这类算法，它使用表驱动将问题分解为子问题的方法来解决。动态规划师自然语言处理中最常用的一类算法，例如Viterbi和正向算法（CHAP - 9）和CKY算法进行解析（第12章）。 从直观上看，动态规划问题是通过将复杂问题分解为子问题，再将子问题的解合并起来的方法来解决的。图2.14中呈现的是字符串intention到execution 最小编辑距离的最短路径。 假定一个字符串（比如exention）是最优路径中的一个节点。显然，在动态规划中，如果这个exention是最优路径中的一个节点，那么从源字符串（intention）
到该中间节点（exention）的最优路径一定是整体最优路径（从intention到execution）的一部分。为什么？如果从intention到exention存在一个更短的路径，那么我们可以使用这个更短的路径替代原最优路径产生一个更短的全局路径，显然这是矛盾的，因为不可能存在比最优路径更短的路径。 最小编辑距离算法 首先做一些定义，假定源字符串X的长度为n，目标字符串的长度为m，X[1…i]表示字符串X前i个字符，Y[1…j]表示字符串Y的前j个字符。定义两个字符串X [1..i] 和Y [1.. j] 之间的最短编辑距离为D(i, j) 。D(n, m) 为字符串X和Y之间的最短编辑距离。 接下来，我们使用动态规划，通过自底向上和子问题的解来计算D(n, m)。两种最简单的情况：假定源字符串X长度为i，目标字符串Y为空字符串，那么从X 到Y需要进行i次删除。同样，假定源字符串X为空字符串，目标字符串Y长为j，则需要进行j次插入操作。计算D(i, j)需要依赖i、j前小字符串的计算结果。D(i, j)的值为以下三个可能路径的最小值： 如果我们假设使用LevsHeTin距离的版本，其中插入和删除每个都有1的代价（ins-cost（·）= del-cost（·）＝1），并且替换的成本为2（替换相同字母的成本为0），d（i，j）的计算变为：
文本相似度算法
文本相似度算法 1.信息检索中的重要发明TF-IDF 1.1TF Term frequency即关键词词频，是指一篇文章中关键词出现的频率，比如在一篇M个词的文章中有N 个该关键词，则 （公式1.1-1） 为该关键词在这篇文章中的词频。 1.2IDF Inverse document frequency指逆向文本频率，是用于衡量关键词权重的指数，由公式 （公式1.2-1） 计算而得，其中D为文章总数，Dw为关键词出现过的文章数。 2.基于空间向量的余弦算法 2.1算法步骤 预处理→文本特征项选择→加权→生成向量空间模型后计算余弦。 2.2步骤简介 2.2.1预处理 预处理主要是进行中文分词和去停用词，分词的开源代码有：ICTCLAS。 然后按照停用词表中的词语将语料中对文本内容识别意义不大但出现频率很高的词、符号、标点及乱码等去掉。如“这，的，和，会，为”等词几乎出现在任何一篇中文文本中，但是它们对这个文本所表达的意思几乎没有任何贡献。使用停用词列表来剔除停用词的过程很简单，就是一个查询过程：对每一个词条，看其是否位于停用词列表中，如果是则将其从词条串中删除。
图2.2.1-1中文文本相似度算法预处理流程 2.2.2文本特征项选择与加权 过滤掉常用副词、助词等频度高的词之后，根据剩下词的频度确定若干关键词。频度计算参照TF公式。 加权是针对每个关键词对文本特征的体现效果大小不同而设置的机制，权值计算参照IDF公式。 2.2.3向量空间模型VSM及余弦计算 向量空间模型的基本思想是把文档简化为以特征项（关键词）的权重为分量的N维向量表示。 这个模型假设词与词间不相关（这个前提造成这个模型无法进行语义相关的判断，向量空间模型的缺点在于关键词之间的线性无关的假说前提），用向量来表示文本，从而简化了文本中的关键词之间的复杂关系，文档用十分简单的向量表示，使得模型具备了可计算性。 在向量空间模型中，文本泛指各种机器可读的记录。 用D（Document）表示文本，特征项（Term，用t表示）指出现在文档D中且能够代表该文档内容的基本语言单位，主要是由词或者短语构成，文本可以用特征项集表示为D（T1，T2，…，Tn），其中Tk 是特征项，要求满足1<=k<=N。 下面是向量空间模型（特指权值向量空间）的解释。 假设一篇文档中有a、b、c、d四个特征项，那么这篇文档就可以表示为 D（a，b，c，d） 对于其它要与之比较的文本，也将遵从这个特征项顺序。对含有n个特征项的文本而言，通常会给每个特征项赋予一定的权重表示其重要程度，即 D＝D（T1，W1；T2，W2；…，Tn，Wn）
有关编辑距离计算的一点整理
一直让我困惑的问题是：abc与ca之间的编辑距离究竟等于几？ 问了很多同学和网友：大家的普遍观点是：如果在编辑距离定义中指明相邻交换操作为原子操作，那么应该等于2；反之，如果在编辑距离定义中为定义相邻交换操作为原子操作那么应该等于3。 为了更好地阐明这个问题，先给出编辑距离的两种定义形式 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氏编辑距离的定义，然后又紧接着给出了如下的计算公式： 公式1：以上两篇论文中提供的编辑距离计算公式。 根据此计算公式得到的计算结果也是3。
华东师范大学计算机机试真题
2009机试 (2) 计算和的数位 (2) 大写改小写 (3) 素数对 (4) 求最大公约数和最小公倍数 (6) 排序后求位置处的数 (7) *路由器连接 (8) *编译原理 (10) *分开连接 (13) 2010机试 (17) ECNU的含义 (17) 空瓶换啤酒 (18) 统计字符 (20) 2010机试热身 (21) 粽子买三送一，买五送二 (21) 工程流水线问题 (22) 2011机试 (24) hello world (24) Special judge (26) 查询成绩 (28) 2011机试热身 (30) 贪吃蛇 (30) 仰望星空 (34) *编辑距离 (36) 2012机试 (38) 字母排序 (38) 幸运数 (39) 十六进制的加法 (42) 电话号码簿合并排序 (42) *五子棋 (43) *正则表达式匹配 (45) 2013机试 (46) 斐波那契数列的素数个数 (46) *将a字符变成b字符最少修改次数 (47) 2013机试热身 (49) 去重排序 (49) 蛇形图案 (51) 数学手稿 (54)
2009机试 计算和的数位 Sum of digit Description Write a program which computes the digit number of sum of two integers a and b. Input The first line of input gives the number of cases, N(1 ≤N ≤100). N test cases follow. Each test case consists of two integers a and b which are separeted by a space in a line. (0<=a,b<=100000000). Output For each test case, print the number of digits of a + b. Sample Input 3 5 7 1 99 1000 999 Sample Output 2 3 4 #include
最小编辑距离及其C++实现
一、问题介绍： 本题提出了一些关于将字符串x[1..m]转换成y[1..n]的操作。 这些操作有复制、替代、删除、插入、互换和终止。 这些操作所需的开销是不同的，但每个操作的开销都可以看是一个我们已经的常量，我们假设复制和替代这类操作的开销要比插入和删除这类操作的开销少。 我们用x[1..m]来保存原字符串，数组下标用i表示，初始化为1； 用y[1..n]来保存转换后的字符串，数组下标用j来表示，初始化为1；数组z用来存放中间结果，下标用j来表示，初始化为0。 题目有两个待解决的问题： 第一，给定两个序列x[1..m]和y[1..n]以及变换操作开销的集合。从x到y的编辑距离指的就是将x转换成y时的最小开销的操作序列。用动态规划的算法找出从x到y的编辑距离并输出最优操作序列。分析算法的时空复杂度。 第二，解释如何从给定的编辑操作集选择一个子集，从而把寻找总分最高的对齐结果的问题，转化为求序列编辑距离的问题的一个特例。 二、算法分析： 问题a解答： 此题跟最长公共子序列的问题十分类似。 因此，我仿照最长公共子序列问题的方法来求解这个问题。 首先，定义了两个序列Xi=x[1,2,...,m]和Yj=y[1,2,…,n]，题目所求的就是将序列xi 变为yj的编辑操作序列的最小开销。 刻画最优解的结构： 对于序列Xi(0≤i≤m)和序列Yj(0≤j≤n)来说，定义c[i,j]为Xi转换成Yj的操作序列的最小开销。假定我们已经知道了最后一次执行的操作，此时分情况讨论问题的最优解结构。 1. 最后一次操作为copy。此时，根据题目的定义可知x[i]=y[j]，我们待解决的问题就转化成了求将Xi-1转换为Yj-1的最小开销。将Xi-1转换为Yj-1的最优解一定包含在Xi转换为Yj的最优解内。用反证法证明：若存在从Xi-1到yj-1转换的更小的开销，那么用这个更小的开销来代替Xi-1转换为yj-1的最优解，这样就会得到一个更小的从Xi转换为Yj的开销，与已知的Xi转换为Yj的最优解矛盾，所以假设不成立。因此，当最后一次操作为copy时，可以定义c[i,j]=c[i-1,j-1]+cost(copy)。
序关系计数问题 编辑距离问题 最小m段问题 正则表达式匹配问题(DOC)
一、算法实现题3-3 序关系计数问题 *问题描述：用关系“<”和“=”将3个数A，B和C依序排列时有13种不同的序关系：A=B=C，A=B
编辑距离算法的优化与实现
编辑距离算法的优化与实现 摘要：在分析基于动态规划的编辑距离算法对文本相似度计算的不足的基础上，利用数据结构在空间效率和时间效率上优化该算法、采用中文分词的思想优化和改善该算法的时间效率和准确率，克服了原有的基于动态规划的计算方法所具有的效率低、准确率低、耗内存高的缺点。通过多种优化方案的实验测试和分析，结果表明优化后的算法取得了很好的准确率和时空效率，更好的用于文本相似度计算。 关键词：编辑距离算法；文本相似度计算；算法优化；动态规划 1引言 文本相似度的计算在信息检索、文本分类、知识挖掘、网页去重、问答系统等诸多领域有着极为广泛的应用，长期以来一直是研究的热点和难点。人们在文本相似度计算中使用编辑距离算法，但该方法单纯以字为单位计算各个字符之间的编辑距离，插入删除替换三种基本操作的代价值的方法不够明确合理，从而使计算结果存在一定的偏差。故对传统的文本相似度检测编辑距离算法进行优化和改善，提出了一种基于改进编辑距离和中文分词相融合的计算文本相似度的方法，使优化改善后的算法具有较高的准确率和效率、较低的存储空间，更符合文本相似度计算的要求，有效提高文本相似度算法的效率和准确性，使文本相似度计算的性能进一步改善。 2编辑距离算法 4.3.1编辑距离定义 编辑距离又称Levenshtein距离（也叫做Edit Distance），是由俄国科学家Vladimir Levenshtein于1965年在文献[1]中提出的，是一种常用的距离函数度量方法，在多个领域特别是文本相似度检测得到了广泛的应用。编辑距离是指两系列字符串之间只能通过插入、删除和替换三种基本操作把源字符串（S）转换成目标字符串（T）所需的最少基本操作次数。编辑距离值越大，则相似度越小。
1：10000数字高程模型(DEM)生产中常见问题解析
1:10000数字高程模型(DEM)生产中常见问题解析 摘要：数字高程模型，是对地形地貌的一种数字表达，可以进行空间描述，并衍生出等高线、坡度及坡向等信息，在地理地质、测绘、工程建设等众多领域应用十分广泛。1:10000数字高程模型生产工作量较大，任务繁重且时间较短，在数字高程模型生产中存在着一些问题。以坐标转换问题、属性项问题、图形编辑问题、接边与图形输出为中心，研究1:10000数字高程模型生产中常见问题，为数字高程模型生产及实际应用提供指导意义。 关键字：1:10000 数字高程模型 DEM 常见问题 一、1:10000数字高程模型(DEM)生产过程研究 数字高程模型，英文缩写为DEM，是通过等高线或相似立体模型进行数据采集，通过数据内插形成，进行区域地貌形态描述。数字高程模型是一种对地面特性进行空间描述的数字方法，在地理地质、测绘、工程建设、军事等领域应用十分广泛。数字高程模型按照一级精度建执行，格网尺寸为5m×5m，高程数据取位为0.1m，在平地作业高程中误差为0.5m，丘陵、山地及高山地高程中误差分别为1.2m、2.5m与5m。1:10000数字高程模型生产过程主要为：准备工作，主要进行原图扫描，预处理等，通过屏幕数字化，进行矢量数据生成，通过修改生成数字高程模型，通过检查验收后应用。具体生产流程如下图所示：
图1：数字高程模型生产示意图 在数字高程模型生产中，其数字化后期处理主要是进行矢量数据编辑，形成coverage并压缩为eOO文件，eOO文件为数字高程模型生成的重要基础。这个过程的处理与完成多是应用ARC/INFO系统来实现。其中ARC系统承担着空间特征与拓扑关系描述，INFO系统主要为记录属性数据关系的数据库管理系统。通过ARC/INFO系统，实现数据输入、存储、处理、分析与结果输出全过程，具备网络分析、空间分析、动态预测等功能，可以产生高层次地理信息。然而该系统在应用中数据输入需要采取手扶跟踪数字化，操作效率较低，应用GeoScan，其操作界面较好，鼠标自动跟踪扫描图形，输入效率高，且容易被用户掌握，虽然应用ARC/INFO系统可以实现数字高程模型制作，但其平三角难以消除，应用GeoTIN 则可以有效消除不利影响。 二、1:10000数字高程模型生产中常见问题及解决措施研究 （一）坐标转换问题研究 在GeoScan转换图括线层中，其控制点中线十字丝与图括线存在着不吻合问题。这种问题的解决措施为：在Arcedit中通过coordinate keyboard改变为键盘输入法，通过add命令增设弧段，并连接四个控制点，生成闭合方式的多边形，通过clean进行多边形拓扑关系建立，最终生成新的图括，实现控制点中心十字丝与图括线吻合。 通过transform进行坐标转换，因前后图形控制点顺序号不一致导致图形出现变形问题，需要在输入层进行控制点顺序号纠正处理方可保证图形质量。 （二）属性项出现问题研究 属性项问题较多，主要包括以下两个方面：第一，属性项连接失败问题。由GeoScan到ARC/INFO，其数据不存在临时代码及等高值，导致属性项连接失败。为此，可以将GeoScan库文件通过dbaseinfo转换为ARC/INFO属性文件，在此基础上进行属性项连接；第二，属性项顺序错误问题。在1:10000数字高程模型是生产技术规定中要求code、gb、elew属性项顺序不出现错误，如出现错误则可以通过以下措施进行改正：重新添加属性项，通过cal进行内容复制并删除原本属性项，通过alter将属性项目更正，或通过pullitems命令按照系统提示进