· 8 years ago · Jul 20, 2018, 06:10 AM
1package search;
2
3import java.io.*;
4import java.util.*;
5
6/**
7 * This class encapsulates an occurrence of a keyword in a document. It stores the
8 * document name, and the frequency of occurrence in that document. Occurrences are
9 * associated with keywords in an index hash table.
10 *
11 * @author Sesh Venugopal
12 *
13 */
14class Occurrence {
15 /**
16 * Document in which a keyword occurs.
17 */
18 String document;
19
20 /**
21 * The frequency (number of times) the keyword occurs in the above document.
22 */
23 int frequency;
24
25 /**
26 * Initializes this occurrence with the given document,frequency pair.
27 *
28 * @param doc Document name
29 * @param freq Frequency
30 */
31 public Occurrence(String doc, int freq) {
32 document = doc;
33 frequency = freq;
34 }
35
36 /* (non-Javadoc)
37 * @see java.lang.Object#toString()
38 */
39 public String toString() {
40 return "(" + document + "," + frequency + ")";
41 }
42}
43
44/**
45 * This class builds an index of keywords. Each keyword maps to a set of documents in
46 * which it occurs, with frequency of occurrence in each document. Once the index is built,
47 * the documents can searched on for keywords.
48 *
49 */
50public class LittleSearchEngine {
51
52 /**
53 * This is a hash table of all keywords. The key is the actual keyword, and the associated value is
54 * an array list of all occurrences of the keyword in documents. The array list is maintained in descending
55 * order of occurrence frequencies.
56 */
57 HashMap<String,ArrayList<Occurrence>> keywordsIndex;
58
59 /**
60 * The hash table of all noise words - mapping is from word to itself.
61 */
62 HashMap<String,String> noiseWords;
63
64 /**
65 * Creates the keyWordsIndex and noiseWords hash tables.
66 */
67 public LittleSearchEngine() {
68 keywordsIndex = new HashMap<String,ArrayList<Occurrence>>(1000,2.0f);
69 noiseWords = new HashMap<String,String>(100,2.0f);
70 }
71
72 /**
73 * This method indexes all keywords found in all the input documents. When this
74 * method is done, the keywordsIndex hash table will be filled with all keywords,
75 * each of which is associated with an array list of Occurrence objects, arranged
76 * in decreasing frequencies of occurrence.
77 *
78 * @param docsFile Name of file that has a list of all the document file names, one name per line
79 * @param noiseWordsFile Name of file that has a list of noise words, one noise word per line
80 * @throws FileNotFoundException If there is a problem locating any of the input files on disk
81 */
82 public void makeIndex(String docsFile, String noiseWordsFile)
83 throws FileNotFoundException {
84
85 // load noise words to hash table
86 Scanner sc = new Scanner(new File(noiseWordsFile));
87 while (sc.hasNext()) {
88 String word = sc.next();
89 noiseWords.put(word,word);
90 }
91
92 // index all keywords
93 sc = new Scanner(new File(docsFile));
94 while (sc.hasNext()) {
95 String docFile = sc.next();
96 HashMap<String,Occurrence> kws = loadKeyWords(docFile);
97 mergeKeyWords(kws);
98 }
99
100 }
101
102 /**
103 * Scans a document, and loads all keywords found into a hash table of keyword occurrences
104 * in the document. Uses the getKeyWord method to separate keywords from other words.
105 *
106 * @param docFile Name of the document file to be scanned and loaded
107 * @return Hash table of keywords in the given document, each associated with an Occurrence object
108 * @throws FileNotFoundException If the document file is not found on disk
109 */
110 public HashMap<String,Occurrence> loadKeyWords(String docFile)
111 throws FileNotFoundException {
112
113 //throws fileNFE if file doesn't exist
114 Scanner sc = new Scanner(new File (docFile));
115 HashMap<String, Occurrence> hashTable = new HashMap<String, Occurrence>();
116
117 //loop through all words, check if valid, add to table
118 while (sc.hasNext()) {
119
120 String word = getKeyWord(sc.next());
121
122 if (word == null)
123 continue;
124
125 Occurrence oc = hashTable.get(word);
126
127 //if new occurrence of a word, create new occ and add to table, else ++ freq.
128 if (oc == null)
129 hashTable.put(word, new Occurrence(docFile, 1));
130 else
131 oc.frequency++;
132
133 }
134
135 return hashTable;
136
137 }
138
139 /**
140 * Merges the keywords for a single document into the master keywordsIndex
141 * hash table. For each keyword, its Occurrence in the current document
142 * must be inserted in the correct place (according to descending order of
143 * frequency) in the same keyword's Occurrence list in the master hash table.
144 * This is done by calling the insertLastOccurrence method.
145 *
146 * @param kws Keywords hash table for a document
147 */
148 public void mergeKeyWords(HashMap<String,Occurrence> kws) {
149
150 //scroll through each key, merging each with the master hash table
151 for (String s : kws.keySet()) {
152
153 //if a new key, create occurrence list and add to hash table
154 if (!keywordsIndex.containsKey(s)) {
155 ArrayList<Occurrence> newAL = new ArrayList<Occurrence>();
156 newAL.add(kws.get(s));
157 keywordsIndex.put(s, newAL);
158 }
159
160 //if key exists, add to array list, sort, and add to hash table
161 else {
162 ArrayList<Occurrence> occ = keywordsIndex.get(s);
163 occ.add(kws.get(s));
164 ArrayList<Integer> useless = insertLastOccurrence(occ);
165 keywordsIndex.put(s, occ);
166 }
167 }
168 }
169
170 /**
171 * Given a word, returns it as a keyword if it passes the keyword test,
172 * otherwise returns null. A keyword is any word that, after being stripped of any
173 * TRAILING punctuation, consists only of alphabetic letters, and is not
174 * a noise word. All words are treated in a case-INsensitive manner.
175 *
176 * Punctuation characters are the following: '.', ',', '?', ':', ';' and '!'
177 *
178 * @param word Candidate word
179 * @return Keyword (word without trailing punctuation, LOWER CASE)
180 */
181 public String getKeyWord(String word) {
182
183 String retWord = "";
184 char[] wordChars = word.toCharArray();
185 int token = 0;
186
187 //scans up until punctuation, should be only punct. after that
188 for (char ch : wordChars) {
189 if (Character.isLetter(ch)) {
190 retWord += ch;
191 token++;
192 }
193 if (!Character.isLetter(ch))
194 break;
195 }
196
197 String secondHalf = word.substring(token);
198 char[] retWordChars = secondHalf.toCharArray();
199
200 //if any letters exist after the punct mark, no keyword is created
201 for (char ch : retWordChars)
202 if (Character.isLetter(ch))
203 return null;
204
205 retWord = retWord.toLowerCase();
206
207 //if the word is a noiseword, ret. null
208 for (String s : noiseWords.keySet()) {
209 if (retWord.equals(s))
210 return null;
211 }
212
213 //if passed all tests, return the word
214 return retWord;
215 }
216
217 /**
218 * Inserts the last occurrence in the parameter list in the correct position in the
219 * same list, based on ordering occurrences on descending frequencies. The elements
220 * 0..n-2 in the list are already in the correct order. Insertion of the last element
221 * (the one at index n-1) is done by first finding the correct spot using binary search,
222 * then inserting at that spot.
223 *
224 * @param occs List of Occurrences
225 * @return Sequence of mid point indexes in the input list checked by the binary search process,
226 * null if the size of the input list is 1. This returned array list is only used to test
227 * your code - it is not used elsewhere in the program.
228 */
229 public ArrayList<Integer> insertLastOccurrence(ArrayList<Occurrence> occs) {
230
231 if (occs.size() == 1)
232 return null;
233
234 ArrayList<Integer> ints = new ArrayList<Integer>();
235
236 Occurrence oc = occs.remove(occs.size()-1);
237 int high = occs.size(); //highest freq, lowest index
238 int mid = 0;
239 int low = 0; //lowest freq, highest index
240
241 //binary search to insert occurrence
242 while (low < high) {
243
244 mid = (high+low)/2;
245 ints.add(mid);
246
247 if (oc.frequency == occs.get(mid).frequency) {
248 break;
249 } else if (oc.frequency > occs.get(mid).frequency) {
250 high = mid;
251 } else {
252 low = mid + 1;
253 }
254
255 }
256
257 //adds the last mid to the list, returns the list
258 mid = (high+low)/2;
259 occs.add(mid, oc);
260
261 return ints;
262
263 }
264
265 /**
266 * Search result for "kw1 or kw2". A document is in the result set if kw1 or kw2 occurs in that
267 * document. Result set is arranged in descending order of occurrence frequencies. (Note that a
268 * matching document will only appear once in the result.) Ties in frequency values are broken
269 * in favor of the first keyword. (That is, if kw1 is in doc1 with frequency f1, and kw2 is in doc2
270 * also with the same frequency f1, then doc1 will appear before doc2 in the result.
271 * The result set is limited to 5 entries. If there are no matching documents, the result is null.
272 *
273 * @param kw1 First keyword
274 * @param kw1 Second keyword
275 * @return List of NAMES of documents in which either kw1 or kw2 occurs, arranged in descending order of
276 * frequencies. The result size is limited to 5 documents. If there are no matching documents,
277 * the result is null.
278 */
279 public ArrayList<String> top5search(String kw1, String kw2) {
280
281 //reference lists, and result list
282 ArrayList<Occurrence> kwo1 = keywordsIndex.get(kw1);
283 ArrayList<Occurrence> kwo2 = keywordsIndex.get(kw2);
284 ArrayList<String> docNames = new ArrayList<String>(5);
285
286 //if both are null, ret. null
287 if (kwo1 == null && kwo2 == null) {
288 return null;
289 }
290
291 //if one is null, simply pull top 5 results from the first list
292 if (kwo1 == null) {
293
294 for (int i = 0; i < 5; i++) {
295 if (kwo2.get(i) == null)
296 break;
297 docNames.add(kwo2.get(i).document);
298 }
299
300 }
301
302 //if the other is null, pull top 5 from other list
303 else if (kwo2 == null) {
304
305 for (int i = 0; i < 5; i++) {
306 if (kwo1.get(i) == null)
307 break;
308 docNames.add(kwo1.get(i).document);
309 }
310
311 }
312
313 //otherwise, compare the highest order freq. with each other, and pull the greatest one.
314 //force insert get(0) for both to start docNames.size()
315 else {
316
317 if (kwo1.get(0).frequency >= kwo2.get(0).frequency) {
318 docNames.add(kwo1.get(0).document);
319 kwo1.remove(0);
320 System.out.println("kwo1 remove index 0. checking hash table comparison");
321 }
322 else {
323 docNames.add(kwo2.get(0).document);
324 Occurrence check = kwo2.remove(0);
325 System.out.println("kwo2 remove index 0. checking hash table comparison");
326 System.out.println("check is: " +check.document +" with frequency: " +check.frequency);
327
328 System.out.println("checking oG hastable: ");
329 Occurrence os = keywordsIndex.get(kw2).get(0);
330 System.out.println("check2 is: " +os.document + " with frequency: " +os.frequency);
331
332 }
333
334 //each comparison scans to see if the item is already inserted
335 while (docNames.size() < 5 && (kwo1 != null || kwo2 != null)) {
336
337 String document;
338
339 //if kwo1's first item is greater, insert kwo1.get(0) into list, remove top, and continue
340 if (kwo1.get(0).frequency >= kwo2.get(0).frequency) {
341 document = kwo1.get(0).document;
342
343 for (String s : docNames) {
344 if (s.equals(document))
345 continue;
346 }
347
348 kwo1.remove(0);
349 System.out.println("kwo1 remove index 0. checking hash table comparison");
350 }
351
352 //else, insert kwo2.get(0) into the list, remove, and continue
353 else {
354 document = kwo2.get(0).document;
355
356 for (String s : docNames) {
357 if (s.equals(document))
358 continue;
359 }
360
361 kwo2.remove(0);
362 System.out.println("kwo2 remove index 0. checking hash table comparison");
363 }
364
365 //add document, whether from kw1 or kw2
366 docNames.add(document);
367
368 }
369
370 }
371
372 return docNames;
373 }
374
375}