数据结构-西工大.doc

2011~2012 学年第一学期《数据结构》课程设计 研究背景介绍 随着互相网信息急剧地增加，要在互联网中检索到自己想要的信息变得非常困难。全文搜索引擎的出现，使我们能够在庞大的互联网中检索自己需要的信息。Google，Baidu是目前文本搜索领域最具代表性的两个高效搜索引擎。如果你在baidu或者google的搜索框中输入ja,就会出现一个候选框，如下所示： 候选框中都是以ja为前缀的word，本次课程设计我们就来探索该如何解决这样的问题。 此外，当你输入java然后点search的时候，被检索到都是包含java的网页，如下图所示。在这个检索结果中，我们可以把每个网页看成一个 Document，这个问题就可以描述为如何快速地在所有的Document中检索到包含java的全部Document。 上面提到的两个问题已经被划分成如下的（1）~（8）个小问题，我们把这些问题分成四个层次，分别是基本型、扩展性、高级型和挑战型。在本次课程设计中，希望同学们根据自己所学的知识，查找相关的资料，构造合适的数据结构，尽自己最大的努力解决这些问题，从而使自己学到更多新的知识。 题目：单词（词组）检索 现在有一个英文字典（每个单词都是由小写的a-z组成），单词量很大，达到100多万的单词，而且还有很多重复的单词。 此外，我们现在还有一些 Document，每个Document 包含一些英语单词。 针对这个问题，请你选择合适的数据结构，组织这些数据，使时间复杂度和空间复杂度尽可能低，并且解决下面的问题和分析自己算法的时间复杂度。 1）基本型问题 （1）选择合适的数据结构，将所有的英文单词生成一个字典Dictionary。 （2）给定一个单词，判断这个单词是否在字典 Dictionary中。如果在单词库中，输出这个单词总共出现的次数。否则输出NO。 2）扩展型问题 （3）给定一个单词，按字典序输出字典 Dictionary 中所有以这个单词为前缀的单词。例如，如果字典 T={a,aa, aaa, b, ba}, 如果你输入 a,那么输出应该为{a, aa, aaa}。 （4）给定一个单词，输出在Dictionary 中以这个单词为前缀的单词的出现频率最高的10个单词，对于具有相同出现次数的情况，按照最近（即最后）插入的单词优先级比较高的原则输出。 （5）输出Dictionary中出现次数最高的10个单词。 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。 设计说明： 1）Vocabulary文件夹下的 vocabulary.txt 是英文字典的数据总共有 100 多万个单词， 即问题（1）~（5）中单词库。 Document 文件夹下的 Document.txt 是用于（6），（7），（8）题中的 Document 数据 数据格式如下： Document?ID? word1?word2?word3?....? Document.txt 文件中包含多个 Document（实验数据中共有 3000个 Document），每个Document 都是以 Document 和ID开始的，ID表示这个Document 的Id号，下面就是这个Document 的数据（即英语单词），数据确保Document中的数据都是小写的英语单词，例如： Document 1 you are complimenting me Document 2 there were many documents SearchWordInVocabula文件夹下对应的是问题（2）中的数据，其中SearchWordInVocabulary.txt是要在字典中检索的数据，需要生成一个SearchWordInVocabulary_Result.txt来保存检索的结果，其中结果的格式为对于每个输入的Word，首先输出CASE ID: ID表示这个Word是输入的第ID个Word，然后如果这个Word在字典中，输出这个Word出现的次数，