《算法分析大作业 寻找变位词》由会员分享，可在线阅读，更多相关《算法分析大作业 寻找变位词（13页珍藏版）》请在金锄头文库上搜索。
1、深圳大学研究生课程论文题目 大作业：变位词实验 成绩 专业 计算机与软件学院 软件工程 课程名称、代码 算法分析与复杂性理论 (161023050011) 年级 2015 姓名 文 成 学 号 2150230509 时间 2015 年 12 月 任课教师 杨烜 一、大作业要求与内容大作业内容：在下列问题中挑选一个问题，选用适当的算法进行实现，在课堂上，针对该问题完成一个 10 分钟的论文演讲与演示，并提交演讲 PPT。（30 分）在一个类似英语词典的大文件中找出变位词的所有集合，例如，tea 和 eat 是变位词，同属一个集合，找出所有这种集合。大作业要求： （70 分）（1）要求演示算法解决
2、问题的完整过程，如果我对解这个问题一无所知，看了你的解决过程，就要能理解算法是如何解决问题的；（2）要求交互界面活泼生动，演示速度可控；（3）尽可能提供丰富的功能让我理解你是如何解决这个问题的；（4）提交源程序、大作业报告（介绍详细的算法设计说明和使用说明）；（5）以论文、报告等形式考核专用答题纸写大作业，大作业报告中要分析算法效率，并给出实测效率和理论效率图表；（6）大作业用 5 号字体，总页数不得少于 8 页，否则视为无效。二、大作业步骤Introduction:给定一本英语单词词典，找出所有的变位词集。所谓的变位词是指，组成各个单词的字母完全相同，只是字母排列的顺序不同。例如，tea 和
3、 eat 是变位词，同属一个集合，找出所有这种集合。Motivating idea:1.如何判断两个单词是否为变位词。思路一：如果两个单词是变位词，那么它们具有相同的长度，且每个英语字母的个数是一样的。我们只需要挨个对各个单词进行比较即可。这个思路容易想，但时间效率太低，还可以继续改进一下，且看下面的思路二。思路二：将两个字符串按照字母表顺序排序，看排序后的字符串是否相等，如果相等则是兄弟字符串（变位词）。这种方法的时间效率根据你使用的排序算法不同而不同。这里我采取思路二，我使用的是快速排序。但是依旧有个问题，单词与单词一个一个比较的话效率还是太低了，我们可以再做改进。2.如何从字典中找出所有
4、变位词的集合。思路一：对于这个问题，最快想到的最直接的方法就是针对每一个单词跟字典中的其他单词进行比较。然而，假设一次比较至少花费 1 微秒的时间，则拥有二十万单词的字典将花费：200000 单词 x 200000 比较/单词 x 1 微秒/比较 = 40000x106 秒 = 40000 秒 11.1 小时。比较的次数太多了，导致效率低下，我们需要找出效率更高的方法。思路二：标识字典中的每一个单词，使得在相同变位词类中的单词具有相同的的标识，然后集中具有相同标识的单词。所以我们要做的就是将每个单词按照字母表排序，排序后得到的字符串作为该单词的标识。再按照排序后的字符串再对单词进行一次快速排序
5、，使得同位词都集中在一起，接下来只需要对这些同位词进行整合就可以了。下面给出我解决这个问题的方法。the way to solve the problem:在编程珠玑书中就有部分提到了变位词程序的设计思路，我的解决步骤与它大同小异。但考虑到词典现实情况的特殊性，我在实现的过程中还进行了很多改进和处理，经过改进后，我的程序不仅可以读入词典的索引，也可以读入完整的词典，还可以读入英语文章。如果考虑单词中字母的所有可能排列，那算法会出奇的低效和复杂。实际上，每个变位词相当于一个等价类。算法的关键是要选择一个标识来标识这个等价类，使得在相同变位词类中的单词具有相同的标识。然后，将所有相同标识的单词集中
6、在一起。我们可以使用基于排序的标识（可见要使用排序技术） ，将单词中的字母按照字母表排序。我的变位词程序按照三个步骤来执行，其中前一个步骤程序的输出作为下一个步骤程序的输入。（预处理：程序读入字典文件，去除无用符号和阿拉伯数字，找出一个不重复的只含单词的列表）第一步：读入字典文件，对单词进行排序得到标识第二步：将所有的单词按照其标识的顺序排序第三步：程序将这些单词整理为每个变位词类一行的形式由于问题的规模不大，采取面向过程的方法解决问题更简单。我依次使用以下三个方法来解决问题。Sign 方法是对每个单词进行标识，reorder 方法是对标识后的单词重新排序，arrange 方法就是一个整合的过
7、程，具有相同标识的单词就是互为变位词。 sign();对每个输入的单词进行标识，每个单词的标识就是依照字母进行排序后的串，在这里我使用的是快速排序。 reorder();对标识后的单词，按照字典序进行排序，使得具有相同标识的单词都排在一起。要区分的是，这里是对单词间的排序，而上一步是对单词中的字母的排序。 arrange();对之前的结果进行整合，具有相同标识符的单词都挨着。后面只需要将同一个变位词类中的各个单词放到同一行中。Example:下面是简单的例子，仅有 6 个单词的字典的处理过程对这六个单词 tea apple ate said dais eatAlgorithm:这里只提供算法思
8、路的代码，实际在实现源程序中还做了很多特殊情况的处理。void sign()/程序标识单词ifstream dataFile(inPath); /字典文件ofstream ofs(outPath+step1.txt,ios:out);/标识单词后的输出路径vector str; /用于逐行扫描单词vector vstr; /用于存放不重复单词if (!dataFile.is_open()cout word) /只要是个单词就把它提取出来，然后接着扫描;/把读入的单词全部转换为小写vstr.push_back(word);/删除容器中的重复字符串for (int i = 0; i s2i)ret
9、urn 1;i+;if (i &s, int p, int r)/快速排序，对一系列的单词按字典序排序if (p str; /用于逐行扫描单词int flag=1;string wordset; /每次读入单词的标识，都把这个标识放进wordsetif (!dataFile.is_open()cout word) /只要是个单词，就把它取出来比较 /后面需要判断是原单词还是单词的标识if(flag=1)wordset=word; /第一次读入的时候把第一个单词的标识存给wordsetofswordset: ; /wordset就作为没一行的开头，也就是一个等价类的标识，然后再输出一个：flag
10、+;continue;elseif(flag%2=0)ofsword ; /把相同标识的单词放到同一行flag+;continue;elseif (wordset=word) /如果读入得标识没有改变，那么wordset不做变化flag+;continue;else /如果读入的标识改变了，那么wordset=wordofs endl;wordset=word;ofswordset: ;flag+;continue;ofs.close();dataFile.close();Implementation:实现使用面向过程的方法，用 C+实现，详细的代码见附件中的 cpp 文件。后面会给出两个测试
11、用例。Preliminary Experimental Results:下面给出两个测试用例的实验结果。一个小词典文件，一个大词典文件。一个是字典文件的索引（仅含单词） 。一个是比较完整的字典（字典中包含单词，单词的解释，例句。其中有阿拉伯数字，标点符号等特殊字符。 ）如下图：首先是第一个测试用例的结果，下面展示整个过程：通过 sign 函数后，每个单词都被标识。然后第二步就是对这些单词排序。第三步就是将相同标识的单词放在同一行。这个是第一个测试用例从开始到结束的一个过程。当然，第一步和第二步生成的中间文件在程序结束后是可以自动删除的，使用这句代码就可以了。/remove(char*)dels
12、tep1.data();remove(char*)delstep2.data();/删除中间生成的文件对于第二个比较完整的字典文件，我的程序也是可以比较好的处理。下面是中间过程。在第一步的过程中，需要对无用字符进行去除，而且对于重复出现的单词要只保留一个。但目前这只是一个 demo。实际的大词典可能会有中文，音标等其它内容。目前这个demo 读入大部分的词典文件应该没什么问题。 最终生成的结果如下图所示，与预期结果相同。三 实验结果与分析理论效率分析：我的程序主要为下面三个步骤。第一步：程序标识单词第二步：程序排序标识后的单词第三步：程序将这些单词整理为每个变位词类一行的形式其中数据的读写都是
13、在一次线性扫描中完成，时间复杂度为 O(n)第一步的标识过程主要是对单词内部进行快速排序的过程。假设单词的长度都不超过 20。最坏情况也就相当于是对 m 个长度为 20 单词做字母的快速排序。而第二步中，程序排序标识后的单词，这里使用的是快速排序，当单词的数目增加，算法的效率会降低，时间复杂度为 O（nlogn） 。第三步将这些单词整理为每个变位词类一行的形式，只需要一次线性扫描就可以完成。第一步和第二步都使用的快速排序。但第一步中单词的长度是固定的，相当于做 m 次快排。但第二步中随着单词的增多，第二步对整个程序的影响最大。所以该算法的理论时间复杂度为快速排序的时间复杂度，为 O（nlogn
14、） 。（程序在读文件的过程中还进行了化小写处理，去符号处理等，可能对实际效率有影响。这些因素在此处不进行分析。 ）理论效率分析：快速排序的理论曲线图形如下图所示。理论曲线图形实际效率分析：为了简化实验过程，我将输入词典的单词个数作为输入的规模。分别采用 10000 个单词，20000 个单词，30000 个单词，40000 个单词的样本数据作为输入。为了方便实验，我从英语小说中截取相应字数的段落来分析。数据规模： 10000 20000 30000 40000 50000耗时（s ） 6 13 19 27 35在不同数据规模下排序所消耗的时间图、由上表数据整合而成的折线图图形上：形状基本符合 n（线性增长）结论：我们发现，由于时间复杂度是 o（nlog 2n） ，当数据规模扩大 n 倍时，相应的在时间的消耗上会扩大 nlog2n 倍，同时我们发现，理论上乘以 nlog2n 后的数据普遍会略小于实际数据，这主要原因快速排序需要递归调用，递归调用需要花费额外的时间，此外轻微的误差可能是数据的差异造成或者电脑等其他因素造成。而且，还有其他因素的影响，去符号和小写变换以及读写文件同样占用时间。四 实验心得与总结这个实验看起来不复杂，但要思考的东西还是很多的。找
