课程设计实验报告
班级： 学号： 姓名：王康10031101 2011302645
● 题目：单词（词组）检索
现在有一个英文字典（每个单词都是由小写的'a'-'z'组成），单词量很大，达到100多万的单词，而且还有很多重复的单词。
此外，我们现在还有一些 Document，每个Document 包含一些英语单词。 针对这个问题，请你选择合适的数据结构，组织这些数据，使时间复杂度和空间复杂度尽可能低，并且解决下面的问题和分析自己算法的时间复杂度。
1）基本型问题（必须采用字符串哈希，hash散列算法） （1）将所有的英文单词生成一个字典Dictionary。
（2）给定一个单词，判断这个单词是否在字典Dictionary中。如果在单词库中，输出这个单词总共出现的次数。否则输出NO。
（3）输出Dictionary中出现次数最高的10个单词。（必须采用快速排序或堆排序算法）
2）扩展型问题（可选择合适的数据结构）
（4）给定一个单词，按字典序输出字典 Dictionary 中所有以这个单词为前缀的单词。例如，如果字典 T={a,aa, aaa, b, ba}, 如果你输入 a,那么输出应该为{a, aa, aaa}。
（5）给定一个单词，输出在Dictionary 中以这个单词为前缀的单词的出现频率最高的10个单词，对于具有相同出现次数的情况，按照最近（即最后）插入的单词优先级比较高的原则输出。
对于以下问题，需采用2种不同的数据结构（hash散列与Trie树，并针对以下题目，比较两种数据结构的优缺点。）
3）高级型问题
（6）现在我们有一些Document，每个Document 由一些单词组成，现在的问题就是给你一个word，检索出哪些 Document包含这个word，输出这些Document的DocumentID（就如同搜索引擎一样，即输入一些关键字，然后检索出和这些关键字相关的文档）。
（7）在第（6）问中，我们只考虑了一个word在哪些Document中的情况，我们进一步考虑2个相邻word的情况，检索出同时包含这两个相邻word的DocumentID。
4）挑战型问题
（8）现在我们再对（7）的问题进行扩展，把（7）中的只检索相邻2个word推广到可以检索多个word（即连续的k个word，其中k>=2），检索出同时包含k个连续word的DocumentID。 ●
一、需求分析
本演示程序中，Vocabulary 文件夹下的vocabulary.txt 是英文字典的数据总共有120 多万个单词，由此生成一个字典树。SearchWordInVocabulay 文件夹下对应的是问题（2）中的数据，其中SearchWordInVocabulary.txt 是要在字典中检索的数据，需要生成一个SearchWordInVocabulary_Result.txt 来保存检索的结果，其中结果的格式为对于每个输入的Word，首先输出CASE ID: ID 表示这个Word 是输入的第ID 个WORD，然后如果这个Word 在字典中，输出这个Word 出现的次数，否则输出“NO”。 TotPrefixWord 文件夹下对应的是问题（3）中的数据，其中TotPrefixWord.txt 是要在字典中检索的前缀的数据，需要生成一个TotPrefixWord_Result.txt 文件来保存检索的结果，对于TotPrefixWord.txt 中的一个输入prefix，输出格式同样是先输出CASE ID:，然后按字典序输出字典中以prefix 为前缀的所有word（不能重复）。PrefixFrequence 文件夹下对应的是问题（4）中的数据，其中PrefixFrequence.txt是要在字典中检索的前缀的数据，需要生成一个PrefixFrequence_Result.txt 文件来保存为检索的结果，对于PrefixFrequence.txt 中的一个输入prefix，输出格式同样是先输出CASE ID:，然后按（4）中定义的优先级输出字典中优先级最高的10 个以prefix 为前缀word 和这个word 出现的次数，如果不足10 个，就全部输出）。对于问题（5），需
数据结构课程设计实验报告
