1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
| 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出现的次数，否则输出“NO”，例如：
vocabulary.txt SearchWordInVocabulary.txt SearchWordInVocabulary_Result.txt
data struct CASE 1:
struct datastruct 2
struct CASE 2:
compiling NO
TotPrefixWord文件夹下对应的是问题（3）中的数据，其中TotPrefixWord.txt是要在字典中检索的前缀的数据，需要生成一个TotPrefixWord_Result.txt文件来保存检索的结果，对于TotPrefixWord.txt中的一个输入prefix，输出格式同样是先输出CASE ID:，然后按字典序输出字典中以prefix为前缀的所有word（不能重复），例如:
vocabulary.txt TotPrefixWord.txt TotPrefixWord_Result.txt
a b CASE 1:
aa a CASE 2:
ca a
ab aa
aa ab
a
PrefixFrequence文件夹下对应的是问题（4）中的数据，其中PrefixFrequence.txt是要在字典中检索的前缀的数据，需要生成一个PrefixFrequence_Result.txt文件来保存为检索的结果，对于PrefixFrequence.txt中的一个输入prefix，输出格式同样是先输出CASE ID:，然后按（4）中定义的优先级输出字典中优先级最高的10个以prefix为前缀word和这个word出现的次数，如果不足10个，就全部输出，例如:
vocabulary.txt PrefixFrequence.txt PrefixFrequence_Result.txt
a a CASE 1:
aa b aaa 2
aaa a 2
a aa 1
aaa CASE 2:
ba ba 2
bb bb 1
ba
对于问题5，需要生成一个MostFrequenceWord.txt文件包含出现次数最多的10个单词和单词出现的次数（倒序），格式如下:
b 50000
a 10000
WordInDocument 文件夹下对应的是问题（6）中的数据，其中WordInDocument.txt中的内容为要在Document中检索的word，需要生成一个WordInDocument_Result.txt保存检索的结果，对于WordInDocument .txt中的一个输入word，输出格式同样是先输出CASE ID:然后从小到大地输出包含这个word的全部的Document的ID，例如:
Document.txt WordInDocument.txt WordInDocument_Result.txt
Document 1 cat CASE 1:
there is a cat there 1 2
Document 2 it CASE 2:
it is a cat and 1
CASE 3: 2
TwoWordInDocument 文件夹下对应的是问题（7）中的数据，其中TwoWordInDocument.txt中的内容为要在Document中检索的words，需要生成一个TwoWordInDocument_Result.txt保存检索的结果，在TwoWordInDocument.txt中，每行包含两个word，就是要在Document中检索的两个连续的word，输出格式同样是先输出CASE ID:然后从小到大地输出包含这两个相邻word的全部的Document的ID，例如:
Document.txt TwoWordInDocument.txt TwoWordInDocument_Result.txt
Document 1 a cat CASE 1:
there is a cat there is 1 2
Document 2 is cat CASE 2:
it is a cat and 1
CASE 3:
Document.txt TwoWordInDocument.txt TwoWordInDocument_Result.txt
Document 1 is a cat CASE 1:
there is a cat there is a 1 2
Document 2 is cat and CASE 2:
it is a cat and 1
CASE 3:
2
MultiWordInDocument 文件夹下对应的是问题（6）中的数据，其中MultiWordInDocument.txt中的内容为要在Document中检索的words，需要生成一个MultiWordInDocument_Result.txt保存检索的结果，在MultiWordInDocument.txt中，每行包含不小于3个words，输出格式同样是先输出CASE ID:然后从小到大地输出包含这些相邻word的全部的Document的ID，例如:
● 课程设计要求
1、 认真准备，按时参加上机实习，不得无故缺席，抽查不到者扣分；
2、 独立完成课程设计布置的题目，提交课程设计报告；
3、 提倡创新，可对课本上提供的算法进行改进；
4、 上机程序必须在程序中提供足够的注释，详细为好；
5、 课程设计报告请写出对课程设计的见解， 如对某一算法的改进思想， 算法设计思想，
调试算法过程中出现的问题及改进方法，调试程序的体会等。只要是自己编程和调试就会写
出相应的报告。
● 考核标准
1、机试程序和结果、 设计报告缺一不可，机试程序和结果压缩打包后上交给辅导老师，设计报告打印后提交（每人限打印15页，主要是自己的设计过程和调试心得，报告中不必附带全部的源程序）。
2、设计报告在课程设计结束按时上交。
3、上机程序和设计报告必须独立完成，严禁抄袭，若发现雷同，原创者视和抄袭者均按0分计。
● 具体评分标准
1．完成基本型问题，最高得分75。
2．完成扩展型问题，最高得分90。
3．完成高级型问题，最高得分98。
4．完成挑战型问题，最高得分100。
● 程序输出要求
请大家按照题目的要求，对给定的测试数据，按照上述的输出格式输出你的结果，以便老师评测你的结果。
|