今天老师布置一道实验题，虽然说给的时间挺长的，但是还是挺难的，而且网上没有代码，在这里讲解一下。
看他的需求：
设A和B是两个字符串，使用最少的字符操作将字符串A转换为B。字符操作包括：（1）删除一个字符；（2）插入一个字符；（3）将一个字符改写为另一个字符。将字符串Ａ变换为字符串Ｂ所需要的最少字符操作数称为字符串Ａ到字符串Ｂ的编辑距离（Edit Distance）。
任务：
1.应用动态规划设计策略，设计一个有效的算法，对于任意给定的2个字符串，计算它们的编辑距离，包含递归描述，可以参考附件A。2、使用编辑距离，可以发现文本中的错误单词，实现简单的拼写纠正。针对附件B中的文本，自己构建一个英文常用词的字典，检测附件B中的错误单词，并利用编辑距离给出可能正确的单词，并进一步给出分析结果，分析算法的优缺点以及可能改进的方法。（附件C中是一些常用单词列表）
大概意思就是算一下两个字符串的编辑距离，再利用它去修改文件中文章的错误单词。
怎么实现，先来看看编辑距离的思路：
存在两个字符串A和B，他们的长度分别是lenA和lenB。首先考虑第一个字符，它们是一样的，所以只需要计算A[2...lenA]和B[2...lenB]之间的距离即可。如果两个字符串的第一个字符不一样，可以考虑把第一个字符变成一样的（假设把A串变成B串）：
(1).修改A串的第一个字符成B串的第一个字符，之后仅需要计算A[2...lenA]和B[2...lenB]的距离即可；
(2).删除A串的第一个字符，之后仅需要计算A[2...lenA]和B[1...lenB]的距离即可；
把B串的第一个字符插入到A串的第一个字符之前，之后仅需要计算A[1...lenA]和B[2...lenB]的距离即可。
然后考虑A串的第i个字符和B串的第j个字符：
不考虑A的前i-1字符和B串的第j-1个字符。如果A串的第i个字符和B串的第j个字符相等，即A[i]=B[j]，则只需要计算A[i...lenA]和B[j...lenB]之间的距离即可。如果不想等，则：
(1).修改A串的第i个字符成B串的第j个字符，之后仅需要计算A[i+1...lenA]和B[j+1...lenB]的距离即可；
(2).删除A串的第i个字符，之后仅需要计算A[i+1...lenA]和B[j...lenB]的距离即可；
把B串的第j个字符插入到A串的第i个字符之前，之后仅需要计算A[i...lenA]和B[j+1...lenB]的距离即可。
动态规划方程：
原来编辑距离就是不断递归去想，比如两个字符串长度都是n:先比较字符串的第一个，这时候就剩下了n-1个，一直递归直到最后一个。
第一问比较好实现，网上有很多方法，可以求出编辑距离：
这里是将字符串a变为字符串b:
代码：
int min(int a, int b){if (a < b){return a;}else{return b;} //判断a是否小于b，小于返回a,否则返回b}int edit(string str1, string str2){int len1 = str1.length();int len2 = str2.length();int **ptr = new int*[len1 + 1];//二维指针for (int i = 0; i < len1 + 1; i++){ptr[i] = new int[len2 + 1];}for (int i = 0; i < len1 + 1; i++){ptr[i][0] = i;}for (int j = 0; j < len2 + 1; j++){ptr[0][j] = j;}for (int i = 1; i < len1 + 1; i++){for (int j = 1; j < len2 + 1; j++){int d;int temp = min(ptr[i - 1][j], 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 << "编辑距离为:" << ptr[len1][len2];return ptr[len1][len2];//求编辑距离}
运行结果如下：
算出了编辑距离就可以开始思考第二问：
他给的文件中是一篇英文文章，需要自己建立一个词典，将错误的单词一个一个和词典比较，如果是一个错误的单词，需要找出编辑距离最小的单词并修改再输出：
建立两个txt:attach-B.txt和zidian.txt,attach-B中的文章内容是：
University time is the best in our life. You can leanr what you want to learn, eat what you like to eat, play what you like to play. But don't froget that here is where you can buid your power and where you can impruoe your ability. The last thing I want to say is that algorithme design and analysis is an important course.
zidian.txt是你自己建立的需要用的单词，就不一一列举了。
需要的函数：计算最小编辑距离；将错误的单词替换；计算编辑距离;主函数。
主要实现代码：
计算最小编辑距离：
int edCount(string a, string b)//算出两个字符串不相同的字串个数{int count = 0;int m = a.size();int n = b.size();int p;if (m > n){for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (a[i] == b[j])count++;}}p = m - count;}else{for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (a[i] == b[j])count++;}}p = n - count;}return p;}将错误的单词替换：
void editjuli(string w1[500], string w2[500]){int juli[64][132];//第一个文件有64个字符，第二个词典有132个单词for (int i = 0; i < 64; i++){for (int j = 0; j < 132; j++){juli[i][j] = edit(w1[i], w2[j]);}}for (int i = 0; i < 64; i++){int minn = 10, h = 0;for (int j = 0; j < 132; j++){int a = w1[i].length();int b = w2[j].length();int k = 0;if (abs(b - a) <= 1){k = edCount(w1[i], w2[j]);}if ((juli[i][j] < minn) && (abs(b - a) <= 1) && (k <= 1)){minn = juli[i][j];h = j;}}if (minn == 0)cout << w1[i] << ' ';//如果编辑距离为0说明两个字符串相等，不需要输出修改后的else if (min != 0){cout << w2[h] << ' ';//如果最小值不是0说明编辑距离不是0，需要修改为词典中的单词}}}
计算编辑距离就是第一问的代码，主函数代码：
void main(){string w1[500];string w2[500];ifstream infile;cout << "原文章:" << endl;infile.open("E:attach-B.txt");//打开原文件if (!infile.is_open()){cerr << "打开文件失败！" << endl;exit(EXIT_FAILURE);}for (int j = 0; j < 64; j++){infile >> w1[j];//将w1的内容写入infile}infile.close();for (int j = 0; j < 64; j++){cout << w1[j] << ' ';//再输出}cout << endl;cout << "新建的词典如下：" << endl;infile.open("E://zidian.txt");if (!infile.is_open()){cerr << "打开文件失败！" << endl;exit(EXIT_FAILURE);}char cc;int shu = 0;while (!infile.eof()){infile.get(cc); //从文件中读取一个字符if (cc == 'n')shu++;}infile.close();infile.open("E://zidian.txt");for (int i = 0; i < 132; i++)//这里的i严格按照132个单词循环，或多或少下边修改后的文章都不能紧挨着，会有空格{infile >> w2[i];}infile.close();for (int i = 0; i < 132; i++){cout << w2[i] << endl;}cout << "修改后的文章如下：" << endl;editjuli(w1, w2);}这样就基本实现了需求，代码结果如下：
总结：
这里是说词典中有132个单词，必须循环132次后边输出修改后的文章才能紧紧挨着它输出，否则会有不同的换行或者词典显示不全。
自认为这里算法的不足之处有很多：
1.原文章中每一个的单词都需要在字典里循环遍历一遍，效率较低
2.字典中单词越多，编辑距离相似的就越多，错误率越高
3.需要两个较大内存的数组，空间复杂度也较高
4.不断地需要对文件读写操作，效率较低
5.算法复杂度较高
这个程序只能勉强完成需求，但有很多不足之处，下次希望可以写的更周全。
共勉