Thanks Matt and Ken for your suggestion. Well, if I store one word (or phrase) per record and let the database sort for each insertion or deletion action, that would cause a huge processing overhead and I doubt a user would like to wait that long. So, I am thinking of storing several words per record and then using a binary heap for indexing purpose. This way, in case of insertion, I would be able to add the word anywhere and all I need to change/refresh is the index database (which is a binary heap containing pointer to dictionary database records) - no resorting of dictionary database. Any comments/suggestions regarding this idea?
Thanks, MN ----- Original Message ----- From: "Matt Graham" <[EMAIL PROTECTED]> Newsgroups: palm-dev-forum To: "Palm Developer Forum" <[EMAIL PROTECTED]> Sent: Wednesday, July 14, 2004 9:35 AM Subject: Re: Indexing algorithm for index file for a dictionary > kcorey wrote: > > > On Tue, 2004-07-13 at 17:01, Nur wrote: > > > >>What would be the most efficient algorithm to use for an index file for an > >>modifiable dictionary database (where words can be inserted or removed)? > >>Factors to be considered: searching speed, addition/deletion speed, index > >>file size etc. > >>Algorithms to be considered: binary search tree, binary heap, ......... ? > > > > > > It depends on a few things...are you going to sort on more than one > > field, or is it strictly alphabetical? what's your most common access > > type for the dictionary (lookup, insertion, deletion)? > > > > I would presume a lookup function on an alphabetically (only) sorted > > database. In that case, there's no real need for an index per se, just > > sort the records of the database. Slow to insert, but fast to lookup, > > as if the database is in order, you could simply do a binary search on > > the database. > > > > However, if inserts and deletes are done on a regular basis, you might > > want to lower the cost of insertion at the expense of making retrieval > > slower. (For this scenario, I'd imagine a separate index > > If this works, you could speed up inserts and deletes by putting storing > several words in one Palm record. Like if you could store a max of 100 > words in one Palm record, start off w/ 50-70 or whatever depending on > how much you want to insert and delete. Whatever your method, if you > will be storing large numbers of words, you'll probably want to store > more than one per Palm record. > > /* > * Matt Graham > * Palm OS Developer > * www.healthramp.com > */ > > -- > For information on using the Palm Developer Forums, or to unsubscribe, please see http://www.palmos.com/dev/support/forums/ > -- For information on using the Palm Developer Forums, or to unsubscribe, please see http://www.palmos.com/dev/support/forums/
