🚀 go-pugleaf

In article <4604@cluster.cs.su.oz.au> alg@is.morgan.com (Al Guintu) writes:

   in <4577@cluster.cs.su.oz.au>, webb+@CS.CMU.EDU (Jon Webb) wrote:
   JW>  Yes, and that's exactly the scheme described by Knuth,
   JW>  volume 3, page 486 (start from the top), 1973, as well as
   JW>  many other sources. It's a good balance between time and
   JW>  space. That's why it's so popular for storing
   JW>  dictionaries.

That's what Dan Bernstein said.  I said the opposite; Knuth's method
is the inverse of the patented method.  To quote:

 in the first few levels of the tree.  We can get better performance by
 mixing two strategies, using a trie for the first few characters and
 then switching to some other technique.  For example, E. H.
 Sussenguth, Jr. [CACM 6 (1963), 272-279] has suggested using a
 character-by-character scheme until we reach part of the tree where
 only, say, six or less keys of the file are possible, and then we can
 sequentially run through the short list of remaining keys.  We shall
 see that his ;mixed strategy decreases the number of trie nodes by
 roughly a factor of six, wihtout substantially changing the running time."

However, note that Dan's point is still probably valid -- if someone
tried the inverse idea in 1963 it seems reasonable to suggest that
someone else tried the same idea sometime since then.  But the
reference is not what he represented it to be, and of course the
Patent Office goes by what has been published, not what has been tried
somewhere someplace.

-- J