文档介绍：找出变位词的集合
算法分析与复杂性理论(期末大作业)
文成 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万个单词