If you ever find yourself in need of a Trie, I've implemented one for lexic and released it under the Apache-2 license:
http://code.google.com/p/lexic/source/browse/#svn/trunk/src/net/healeys/trie It's capable of supporting multiple dialects and languages. I've used it to cram about 80,000 US & UK words into less than 800K. Reading the entire trie takes about 30 seconds, but it has the ability to prune the trie based on 2-letter markov chains to drastically increase the speed. It's got a bit of lexic-specific code in it right now, but I'd be interested in working with anyone who wants to adapt it to their own project. -Johnny On Mar 11, 5:52 am, Al Sutton <[email protected]> wrote: > http://en.wikipedia.org/wiki/Trie > > In my view the best way to do a static dictionary. > > Then populate the SQL database with and additions the user makes. > > Thing to remember; SQLites' design goals are read/write capabilities. > That doesn't mean it's using the best way to handle read-only data. > > Al. > > > > Stoyan Damov wrote: > > On Wed, Mar 11, 2009 at 3:52 AM, Mark Murphy <[email protected]> > > wrote: > > >> Justin Allen Jaynes wrote: > > >>> I couldn't deal with a 5 minute startup time on an app, so I decided to > >>> include the actual database file in my resource raw folder (others > >>> suggested this to me). > > >> One potential flaw with put-the-database-file-in-the-APK approach is > >> SQLite file format. Suppose Android 1.5 includes an update to SQLite > >> that causes the SQLite file format to change, such that SQLite cannot > >> read your binary database file you packaged up? Now your app is "broken" > >> for newer Android devices. > > >> It may be that SQLite will be backwards compatible, or it may be that > >> this is just unlikely to happen. However, it is a risk developers need > >> to keep in mind. > > > This is not going to happen. If Google rolls out SQLite X.YY and it's > > incompatible with the database file format used by currently installed > > apps (some probably paid), would you think that the OTA upgrade will > > kind of search for all SQLite databases on the device (some might be > > on the SD card) and offer the user to upgrade them? > > >> The same general argument holds true for packaging the data in the form > >> of SQL statements, though given that SQL is more or less a standard, I > >> would expect fewer problems this way...performance notwithstanding. > > >> Obviously, given the performance characteristics in your case, if SQLite > >> has to be the answer (see below), then you have no choice but to package > >> the binary database and pray. > > > If I was building a dictionary app and it had to use database and not > > some other binary format I'd compress a database with non-indexed > > tables, put it as a resource, then on 1st run inflate it to SD card, > > and create an index (if that's supported, I'm assuming running an > > SQLite db off the SD card is). This would decrease my storage > > requirements to the bare minimum. > > >>> (mine is a large word dictionary > >>> and the whole app after first run takes 4 meg) > > >> Another thing to consider with large yet simple database structures is > >> whether SQLite is the right answer at all. This is particularly true if > >> the data is read-only or read-mostly. It may be you are better served > >> finding a Java library implementing a lower-level data structure > >> (red-black tree, AVL tree, etc.) that is better tuned for your scenario. > >> You might even find one that can work efficiently with an InputStream, > >> thereby allowing you to keep the data in the APK without a second copy. > > >> For example, when I see "large word dictionary", I think of > >> spell-checkers, and implementing a spell-checker with a SQLite backend > >> would seem likely to have poor performance. Of course, then again, it's > >> been about two decades since I wrote my last spell-checker... > > >> -- > >> Mark Murphy (a Commons Guy) > >>http://commonsware.com > >> Android Training in Sweden --http://www.sotrium.com/training.php > > -- > > * Written an Android App? - List it athttp://andappstore.com/* > > ====== > Funky Android Limited is registered in England & Wales with the > company number 6741909. The registered head office is Kemp House, > 152-160 City Road, London, EC1V 2NX, UK. > > The views expressed in this email are those of the author and not > necessarily those of Funky Android Limited, it's associates, or it's > subsidiaries. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Android Developers" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/android-developers?hl=en -~----------~----~----~----~------~----~------~--~---
