计算机算法寻找变位词讲述.pptx

找出变位词的集合 算法分析与复杂性理论(期末大作业) 文成 2150230509 计算机于软件学院 软件工程 给定一本英语单词词典，找出所有的变位词集。所谓的变位词是指，组成各个单词的字母完全相同，只是字母排列的顺序不同。例如，tea和eat是变位词，同属一个集合，找出所有这种集合。 问题描述 问题一：如何判断两个单词是否为变位词。 思路二： 将两个字符串按照字母表顺序排序，看排序后的字符串是否相等，如果相等则是变位词。 思路一： 如果两个单词是变位词，那么它们具有相同的长度，且每个英语字母的个数是一样的。一个单词组成字母所生成的排列就可能是它变位词。 问题二：如何从字典中找出所有变位词的集合。 思路一： 我们已经知道如何判断两个单词是否为变位词，最直接的方法就是针对每一个单词跟字典中的其他单词进行比较。（有n个单词就要比较n^2次。效率低下，我们需要找出效率更高的方法） 思路二： 标识字典中的每一个单词，使得在相同变位词类中的单词具有相同的的标识，然后集中具有相同标识的单词。将每个单词按照字母表排序，排序后得到的字符串作为该单词的标识。（这种方法的时间效率根据你使用的排序算法不同而不同） 那么对于该问题的解题过程可以大致分为三步： 第一步，对单词内部的字母进行排序得到标识； 第二步，将所有的单词按照其标识的顺序排序； 第三步，将同一个变位词类中的各个单词放到同一行中。 这个问题使用面向过程的方法更为简单，在我的程序中对应以下几个方法。按顺序执行以下三个方法，其中前一个步骤程序的输出作为下一个步骤程序的输入。 Sign() Reorder() Arrange() 下面给出一个简单的例子，仅有6个单词的字典的处理过程 tea apple ate said dais eat tea apple ate said dais eat aet aelpp aet adis adis aet sign(); 对每个输入的单词进行标识，每个单词的标识就是依照字母进行排序后的串，在这里我使用的是快速排序。 sign tea apple ate said dais eat aet aelpp aet adis adis aet reorder(); 对标识后的单词，按照字典序进行排序，使得具有相同标识的单词都排在一起。 要区分的是，这里是对单词间的排序，而上一步是对单词中的字母的排序。 reorder dais said apple ate eat tea adis adis aelpp aet aet aet arrange(); 对之前的结果进行整合，具有相同标识符的单词都挨着。后面只需要将同一个变位词类中的各个单词放到同一行中 arrange dais said apple ate eat tea adis aelpp aet dais said apple ate eat tea adis adis aelpp aet aet aet 考虑实际情况： 读入的是大词典文件，有单词、音标、标点符号、阿拉伯数字、例句等信息，我们需要做一些特殊处理（预处理）。 例如： 对于无用的符号在读文件时要过滤掉。 对于大写的单词，统一转换成小写。 对于重复的单词只保留一个。 …… 所给算法主要针对读入的是字典的索引，其处理步骤就按照之前叙述的就可以了。 效率分析 第一步：对单词进行排序得到标识 （相当于对组成单词的字母间做快速排序，实际上有m个单词就要做m次快排。这里主要影响因素是单词字母的个数，实际上每个单词的字母数都不会太多。） 第二步，将所有的单词按照其标识的顺序排序； （这里的输入规模是单词的个数，也是效率的主要影响因素。若单词的个数为n，其时间复杂度为O（nlogn）） 第三步：将同一个变位词类中的各个单词放到同一行中。 （在一次线性扫描中就能完成，时间复杂度为O(n)） 随着输入规模的增大，理论上该程序的效率应该符合右图。即快速排序的效率。 主要影响程序效率的是第二步的对单词的快速排序，不重复的单词的个数对算法效率的影响最大。 数据规模： 10000 20000 30000 40000 50000 耗时（s） 6 13 19 27 35 实际效率分析： 为了简化实验过程，我将输入词典的单词个数作为输入的规模。分别采用10000个单词，20000个单词，30000个单词，40000个单词的样本数据作为输入。为了方便实验，我从英语小说中截取相应字数的段落来分析。 一般来说一本四六级英语词典的索引分别有6600和7500个单词，一般的英语词典则更多，所谓大词典，应该有上万个单词。我实验的测试用例选取1万到5万个单词的文本文件作为输入，分别统计耗时。 图形上： 形状基本符合n（线性增长