Hashing

Concordances and Search Engines

A concordance is an index that tells where in a particular document any word appears. Biblical concordances have been around for a long, long time. They are used by scholars to identify the book and verse in which any word appears.

Assignment

You are to develop an application/applet that allows a user to search the Bible (you may use any document of equivalent length) for a particular word or combination of words. Your application should be able to take a logical expression made up of words [ e.g. ((god && love) && !(world))], and return a list of locations and verses where this occurance takes place. For extra credit, you should be able to bring the user to the location in the running text where the verse is found. Case and punctuation should both be ignored; they must not enter into your hash function, and your word-matching must be case-insensitive.

Resources

You can find and download several public domain versions of the Bible at the Project Gutenberg page http:www.promo.net/pg . The King James Version of the Bible is about 4.4MB of text (approximately 100K words). As mentioned above, if you prefer, you can use another text; but the KJV version of the Bible comes equipped with it's own indexing scheme (Book,chapter,verse) which will help in file structure organization. If you decide on a different text, (Shakespearian sonnets might be nice), you will have to come up with your own indexing scheme.

System Architecture Suggestions

You may use the Java HashTable class for your application. Create a class to represent each word. The class should contain the word, (of course) and a linked list of verse indices where the word occurs. Build the hash table by reading the text file. Use a random access file to store the text for quick lookup of the verses. A second hash table can be used to go from verses indices to byte locations in the random access file.

So, when a user enters a word ["smite", for instance], the first hash table can be used to find and return the appropriate word description object. The word description object has a linked list of verse addresses. The second hash table can be used to get a location in the random access file for each address. Loop through the linked list and print the selected verses into a text area on your application.

Hint : Get single word queries working first. For complex queries ["(smite || rest) && wicked", for instance]. The first hash table can be used to get the lists of occurrences for each word. If the lists are sorted by where they occur, it's an easy task to write merge functions to perform the logical set operations of union (logical or - ||) and intersection (logical and - &&) .

More hints : Get started early and develop your application using a small text (the first chapter of Genesis, only).