Re: Scheme style auto-resizing hashtable (fwd)

[Jay Glascoe <jglascoe@jay.giss.nasa.gov>]

On Wed, 4 Nov 1998 Chris.Bitmead@misys.com.au wrote:

>  > Paper dictionaries do tend to be in alphabetical order, but that is
>  > merely an implementation detail. The reason it is in alphabetical
>  > order is *not* so you can read all the entries in alphabetical
>  > order, but rather to facilitate random access.
> 
> >True for word -> meaning mapping, but dictionaries can also be used
> >for word -> spelling.  If one can at least spell the beginning of the
> >word, one looks it up & scans the word until finding the wanted one.
> 
> But having a dictionary in alphabetical order for spelling correction is
> still an implementation detail. And it's a very poor implementation at
> that.

so, let's say I have an entry in my dictionary with key "foobar", but I
can only remember "foo.." and then my memory gets fuzzy  ;)  I guess a
dictionary with ordered entries could give me a list of all keys from
"foo" to "fop" to help me find it (in O(log n) time).  neat!

But with a dictionary implemented as a hash table I could do a swift
"dictionary->key-tree my-dictionary string<?" type thing and then climb
the tree, looking for "foo..."'s and whatnot, to my heart's content.

Obviously I'm looking forward to Tel's B-tree implementation:

(define dictionary->key-tree
  (lambda (dictionary less-than?)
    (list->btree (dictionary->keys) less-than?)))

yeah, it's a garbage monster, but it works.

I could even do a "dictionary->ordered-key-list" with

(btree->list (list->btree (dictionary->keys) less-than?))

which is a total space/time pig, but I like it.


	Jay Glascoe
	jglascoe@jay.giss.nasa.gov