• Proposal for the project
• Diagram of the data structure
• The Competition: another, admittedly fancier, version of what I did, by someone at University of Michigan.

Specification:

• I created a Hashtable with an entry node for each word. The node contained a String, representing the whole word, and a BitSet, that has one bit for each verse in the Book of Mormon. For the bitset of a given word, a set bit indicates that word occurs in the verse that corresponds to that bit.
• When the partial word search is enabled, the Hashtable is built so that the key that is hashed on is only the first three characters of the word (or the whole word if less than three characters long). I handle my own collision resolution using an open hash. A linked list of is created for each set of words that have the same first three letters. When a partial word is searched, I return the union of the whole list's bitsets. (The reason for not simply maintaining one bitset that is a precomputed union is that the user may choose to search a partial word on more than three characters, and that would eliminate many of the words in the list.)
• In order to speed up the output of the verses, it was necessary to know what byte number each verse began with, so that instead of reading in lines and counting each one, the IO stream can simply skip the necessary number of bytes. For this, I used an array where the index is the verse number (starting at zero; the same index used in the BitSet) and the value is the byte offset from the beginning of the file.
• To test if a verse occurs in a certain book or not, I prepare a BitSet for each book. The organization of the bitset is the same as for the word bitsets. The block of bits that correspond to all the verses in a given book are set for the bitset that corresponds to that book. Then a simple intersection can be taken between the bitset for a word or group of words and the bitset for that book to determine if the word(s) occur in that book.

Rationalization:

The reason I chose a hashtable is that I wanted something that was simple to use, but still very fast. Java's built-in utility Hashtable was perfect since it handled most of the mundane details automatically, but because the default collision resolution did not give me the control I needed over the data, I decided to do my own. A linked-list open hash was a natural solution since it is simple to implement and has variable length. Variable length was very important because there is a very large range in the numbers of words that will collide for a given three starting characters. (e.g., there is only one word that starts with "zar", but many words that start with "the" or "ste")

The BitSets were great because, again, they were such a natural fit and thus very simple to use. The problem if determining from a list of words, each which has a list of verse numbers, which words are in the same verse was quite a challenge, and without some tricky algorithm work could quickly become a gigantic use of time. Since the bitsets' intersection operation is a bitwise one, it is really fast, and also a perfect match for the problem. As mentioned above, the intersection also worked well for book restrictions as was the union for partial word searches. (ASIDE: A feature that could be added in the future would be to allow the user to disallow words in the verse and/or make a distinction between requiring a word be present and simply listing it as a possibility. Aside from some user interface busywork like parsing what the user wrote, the implementation of these would be fairly trivial using bitset operations.)

Summary of hashtable/bitset combination: ELEGANT! FAST!* (* and uses lots of space)

The array was picked because it has basically no overhead, is really fast, and I know the number of elements it needs beforehand since it is read out of the same file every time.

Limitations:

The hashtable/bitset implementation, although I still believe to be a very good choice, has some limitations:

• Space considerations: The hashtable takes up a lot of space, period. The bitset actually saved space for many of the words, in comparison to having a list of the occurences in the form of, for example, an array or a Vector of integers representing the verse or word numbers where it ocurred. Such a representation would have been extremely costly for words like "the", which occured in almost all the verses and over 19,000 times as an individual word. However, as the Zipfian distribution predicts, words like "the" are the minority, and there are many words that occur only once or twice. So, in the aggregate, the bitset was also a waste of space in comparison to other possible implementations. (see complete analysis below)
• Literal string search: Since the bitset's smallest (and only) addressing resolution is by verse, searching for literal strings (the words must occur in the order specified) is not possible. The bitset could in theory be addressed by word instead of verse, but it already took up quite a bit of space in memory, and addressing by word would have pushed it over the edge into an impossibility (at least on ieng9). However, if the user enters the 3 or 4 words as if they were a literal string, it is unusual that there will be very many other verses that are returned, other than the ones they wanted, so they can simply ignore those few.
• Partial word searches must be by at least 3 characters, and they must be the first 3: Since the hashtable for sticky hash mode intentionally collides all words based on their first 3 letters, doing a partial word search by the first one or two characters is not supported. As was the case with literal string searches, this problem in theory all but disappears in practice. After all, how many people (for a legitimate purpose, i.e. not just trying to break my program) are ever going to want to search out all instances of words starting with "c" or "ch"? I decided on the number three because that would produce what I thought to be just the right number of collisions. There are lots of fundamentally and symantically unrelated words that start with the same one or two letters, but three will allow the flexibility, yet restrictiveness that is about right. Also, because I have to do a linear search on the words in the linked list, a search like "th" "st" could have taken a really long time. I wanted to minimize that, since smart users that entered something like "start*" would also suffer. Lastly, on the point that it must be the first three letters, this is because making a hash of all possible 3-letter substrings of a word would have been a huge waste of space. I say waste because, going back to the "normal" use consideration, a user will usually use a partial-word search when they just want to allow different endings for the same word, for example, allowing different tenses of the same verb. Since most English words have such morphological changes at the end, it would be more rare to want to search the end of a word and find variable beginnings.

As mentioned above, I concede that the space (memory) usage of my program suffered in many ways at the hands of time interests. Also, one of the main problems with my implementation was that the interface does not include a search by literal strings, which was because of the bitset's large space consumption. So, I would like to present a defense of this interface concession in terms of a formal anaylsis of the space and time costs of bitset of verses vs. list of word locations in an array:

SPACE:

• In an array with word addressing, the total memory usage would be the sum, over all the distinct words, of the number of occurences of that word, which is simply equal to the total number of words (267,937), times the space used by an integer (32 bits). This gives 85,751,584 bits.
• A bitset with word addressing would consume the product of the number of distinct words (5,569), and the number of words (267,937), since each distinct word would have a bitset with a bit for each word in the book. This gives ~1.5e10 bits, which is clearly unacceptable. So we move on to verse addressing:
• For an array with verse addressing, it is difficult to determine exactly how much memory would be used. If every word occurred in every verse, the usage would be the number of distinct words, times the number of verses, times the size of an integer, which gives 1,186,152,448. However, this is clearly not the case. I would very very roughly estimate that 1/500 to 1/1000 of all the distinct words occur in any given verse which gives something on the order of millions or tens of millions of bits.
• In a bitset with verse addressing (this is what is actually used in this program), the total memory usage is the number of distinct words times the number of verses, which gives 37,067,264 bits. This is comparable to the array/word addressing size estimate of millions or tens of millions of bits. Unfortunately, its also comparable to the figure for word addressing in an array (85.77 million). However, this difference of (very) roughly 3 to 10 times as much space consumption can be forgiven, as will be shown in the time analysis below.

Lets say a user enters a single word for a search and does not give any restrictions on location. In this case, both bitset and array would take about the same time. This is because in both cases, the word will be looked up in the hashtable, and then a full enumeration of its verses will be given to the user, which will linear in both cases. However, if a user enters a whole list of 3, 5, or even 10 keywords, the situation changes dramatically. The following is a comparison of an array indexed by word (that would allow literal string searches), to a bitset addressed by verse (that does not) in the example of a search of multiple keywords: (i.e., continuting to show why I disallowed literal string searches in order to use the bitset)

• Array: Once all the words are found in the hastable, we have before us essentially a collection of sets of locations (one set for each keyword). The problem is to find a (modified) intersection between these sets. (In other words, which of these words have neighboring locations in their sets and therefore follow eachother in the text.) Finding the intersection of sets, unfortunately, is a very non-trivial problem. We would have to start with one instance of one word, and then look in the arrays of all the other words for a nearby instance. But just because two pairs of words occur in the right place in relation to eachother in the string does not mean that all 3 (or 5 or however many) words occur in the right place in relation to eachother in the string. So we would have to compare instances of every word with instances of every other word. If the number of words that the user entered as the string (that we found to be in the book at all) is N (bounded at 5569, the number of distinct words), and the number of instances of each word is M (assume for simplicity that all the words have the same number of instances M, bounded by 19,209, the instances of "the"), this takes O(M * (M * (N-1))) or O(M^2 * N), which could be a very long time! One mitigating factor is that we can assume that the sets are ordered, since they could easily be read in from a file and inserted into the array in order, but this only helps to reduce one of the M's to logM (because we can use binary instead of linear search). This makes the equation O(MNlogM). Even for N=5 ("and it came to pass") and M=3000 (the average number of occurences for those words), about 150,000 comparison operations are required.
• BitSet: The first big advantage is that the bitset has a clearly defined sense of proximity of words, since it is addressed by verse. Since it takes 208 integers to represent the bitset of 6656 verses, it takes 208 cycles of the CPU per comparison between the bitsets of two words (to determine which verses they share). This gives the semi-exact time to be 208(N-1) CPU cycles. Not only does the big-O time, O(N), clearly beat the array implementation, but since the bitwise operations can be measured in CPU cycles instead of just "comparison operations" (as above), this is REALLY fast, beating the array implementation hands-down.

Send questions and comments to clbailey@ucsd.edu (Or ask any time during the presentation)