Pre-Filled Trie

Question

Background:
My CSS360 team is trying to create an Android app that will include an auto-complete feature. The data we are looking for is about 7000 records and will be stored in the SQLite database on the phone itself. The most obvious approach would be to do a linear search of the database after each character that the user enters, and then return a list of sentences that are potential alphabetical extensions of the user query. However, it seems that this would be rather inefficient, and we were looking for better alternatives. In another of my classes, my instructor briefly discussed the trie data structure today and mentioned that it is often used to store entire dictionaries. Trie entries can be found in logarithmic time (as opposed to linear time for a regular old array), so this seems like a great tool for us! Unfortunately, we are already in waaaay over our heads in this project, and none of us really knows how to do this. All of us, ever encoded today, are the basic console applications to teach us the basics of programming. We are all trying to learn the Android platform in a week by watching videos on YouTube and differing from the database by one guy in our group who has any SQL experience. We could seriously use some pointers!

Questions:

• When creating a trie, is it possible for the whole structure to be pre-populated? IE: create a line of code for each node used so that the entire structure is already in memory when the program starts? My thinking here is that this will save us from the overhead associated with the need to regenerate the entire trie from the database each time the program starts. If so, is there an easy way to get these thousands of lines of code in our program? IE: Some kind of script that converts database files into a giant text file of java commands that can be copied and pasted into Eclipse?
• Will there be a significant amount of overhead if we search the database directly and not use any internal list or data structure? Should we copy the names from the database and look for them inside the program for our autocomplete function?
• If this is too complicated for us technically, and we have to resort to regular linear searches, will performance be noticeably affected?
• Our current plans are to start the autocomplete function every time the user enters a character, and then waits for the function to return before allowing them to continue typing. The only programs that each of us have already written work this way synchronously. What do we need to know to make this function asynchronously? Given our newcomers and the demands we already need to meet, would that be too difficult for us?

Answer 1

sqlite should be able to satisfactorily perform this autocomplete function. I would recommend using their internal indexes to reimplement the wheel. If you need to do the latter, then sqlite will probably not help you after you have done this work.

If you need a substring search, then full-text search is probably the best choice.

If you only want to complete the beginning of a word, then just using their vanilla indexes should be more than enough. If performance is a problem, just wait until they type three characters before executing the query. Set a limit on your results for a quick response.