'database' search

[Bjorn Pettersen]

I haven't done this before, so I thought I'd ask if anyone has any
experience...

I have a relatively stable database of between 1500 and 5000 items (new
insertions are probably going to be less than 100 during the lifetime of
the database).  The items are keyed on a text string.

I'm creating a gui where I want to implement field completion as the
user is typing, i.e. if the user types 'aa', all entries (or at least a
subset) with that prefix will be (unobtrusively) presented so the user
can use an alternate selection method (similar to the file open dialog
on win2k, although I'm not tied to any specific implementation).

I'm interested in experiences anyone might have with respect to both
which datastructure to use, and if any gui toolkit is better suited for
this.

The smallest datastructure I've found so far, is a 'prefix dictionary',
so if e.g. "aardwark" was in the database, the 'prefix dictionary' would
contain:

 pfdict = {
  'a':        ['aardwark', ...],
  'aa':       ['aardwark', ...],
  'aar':      ['aardwark'],
  'aard':     ['aardwark'],
  'aardw':    ['aardwark'],
  'aardwa':   ['aardwark'],
  'aardwar':  ['aardwark'],
  'aardwark': ['aardwark']
 }

The maximum size for this would be n * avg len of item, with the real
size being much(?) smaller with sufficient prefix sharing...

-- bjorn