in a hash table you
   1 compute the hash value in O(length(key))
   2 compare the found item  to the key also in O(lengthKey)
   3 you compare more keys if they are collisions

On the other hand, TRIES and their look alike process character by
character.
so if the key is not there you can know if faster.

All this depends on the statistical repartition of your keys.
You can imagine a data set with 100 characters keys on where the first 5 are
usually enough to differentiate them.
In that case It's likely that hashtables will be slower.

However, tries and their ilk don't require you to know where the cutoff is
a priori.  They'll get faster all by themselves depending on the actual
distribution of the data.

  in all likelihood, a hashing function is able to take advantage of the
  same property of the input, and but then somewhat more for collisions.

  the real difference, as I see it, is that tries will be able to take
  advantage of _any_ smallest set of differences, so if you have a bunch of
  people names starting with "Smith", the trie will effectively just move
  past the first 5 and use the next 5 characters, instead.  a hash function
  would have to be excessively intelligent to adapt the same way.

   Long chains of "public" hierarchies can all be in the same file since
   they, for the most part, share namespace.  Even "private" hierarchies as
   long at the author interally respects the abstraction boundaries.
   You do have to be  more "disciplined" when using CLOS+packages then when
   depending upon the C++ compiler as an abstraction boundary "enforcer".

   This gives you "libraries" (or a framework) of classes.

   Probably a closer analogy would be to Java (and its packages) than to
   C++ (namespaces).  You can develop quite a maze of namespaces
   with names space control comingled with the object class definitions quite
   a bit more easily with public/protected/private than with namespace
   and class definition mechanisms seperated.

   The  "defsystem" , "modules" , and "package"  solution is one of those
   things CL doesn't quite do in an "inspired" fashion.  You can make it work.
   However, it usually seems more painful than it "should be".  

   I think some people get "bit" by some "package problem" and then just
   shy away from it in the future.  And I'm sure there are also more than
   few for whom in their standard "modus operandi" it all works well.  

--

  problem is, we might have caused the OSCE incident in Kosovo.  the sum
  total of hostilities in the world has to remain constant, so what was the
  world to do?  things just _had_ to get ugly somewhere else, instead.

        (reduce #+ (beastly-encode "BILL GATES III")) => 666

and that you can encode my home telephone number in Rome as

        666 666 666

and you can start to think that every hash function eventually
converges to the Number of The Beast.

Cheers

Exactly.  Plus, if you're doing typical symbol-table or other plaintext stuff,
you can *significantly* cut the amount of storage used with tries by various
forms of "compression" on each node (much like the way most C compilers
generate different styles of code for "switch" statements depending on
the pattern of "case" values), tagging each node with its "style" or kind:

- As Erik notes, you can collapse a run of fanout==1 nodes into a single
  "match"-only node consisting of a string and one further node pointer.

- If the degree of fanout is >1 but still very low, the node might be
  encoded as a small string that's searched sequentially, together with
  a vector of the same length (indexed by the searched-for character's
  position in the string). While this is a good deal slower than a pure
  "radix-sort" style index, it's also *much* smaller.

- With higher fanout, a node might contain "min" & "max" character codes,
  and a vector as large as "max - min + 1", indexed by "this_char - min".

- With still higher fanout, revert to a full max-char-code size vector.
  In most practical applications, you'll only need a few nodes like this
  (maybe even only the root node).

+---------------
| a hash function would have to be excessively intelligent to adapt
| the same way.
+---------------

That reminds me of a trick that can help hash tables: If you use a really
good hash, one for which nearly every bit position contains nearly a full
bit of information (a CRC-32 is such a hash), then if you store the *full*
hash value with the entry, when you want grow the hash table because the
per-bucket chains get too long, you don't have to re-hash the keys -- you
can just use more bits of the original hash value.

Finally, there's an interesting hybrid of hash tables and tries -- a
multi-level hash table that uses different bits of the hash at each level
of the tree/trie (that is, it's a binary tree if you only use one bit of
the hash per level). When you hit a leaf node you do a comparison on
the full hash first before wasting time with a full string compare.
If the hashes are the same but the strings differ, then the strings are
probably *very* different (assuming a "good" hash, such as a CRC), so
hanging a "compressed trie" (as above) off that node should be a cheap
way to resolve the conflict (that is, the strings will very likely differ
in the first character!).

[Hmmm... It would be interesting to compare these three methods for
space & speed to implement "intern"...]

-Rob

Cheers

Could you please expand on the difficulties that one might encounter
using this method of data encapsulation?

Thanks,

--
Kenneth P. Turvey <ktur...@SprocketShop.com>

Does anyone have experience with this style?

I find it hard to understand what exactly about the CL package mechanism
hinders people to create many small (fine grained) name spaces. Perhaps
the fact that for easy interactive use they all would tend to get used
in COMMON-LISP-USER anyway. Garnet seems to be the exception as their
recommended style advises against using the package and for an explicit
package:symbol style.

What do people tend to do? How large a logical unit should a package
be? How large in terms of lines of code or exported symbols should a
package be? What other measures might be useful when considering the
size of packages? Are mutually dependent (either directly or
indirectly) packages always a Bad Thing? Are there any style guides
that address these issues in detail?

    David> I highly appreciate this information, though I must admit
    David> that I'm skeptical at how it can _possibley_ be faster than
    David> a hashtable.

I'll use the regular trie here, because I know it better.  Roughly
speaking:

Searching a trie and coming up with an element if one exists is
roughtly an O(n) operation, with n being the length of the indexing
string.  So (trie-ref trie "foo") takes three steps.  But if the
element does not exist (suppose there are no strings starting with #\f
in the trie), then it can take less than n steps to reject the
reference.

A hashing function on strings takes some number of characters and
combines them to come up with an index into an array.  This is an O(n)
operation with n being the length of the indexing string (although
some implementations arbitrarily cut the hashing function off at say
the 10th character).  This hashing function must be performed
regardless of success or failure, and so a hashing function always
requires n steps.

In practice, this isn't really very interesting, and tries may or may
not have poor cache behaviour etc., so a simple version just says hash
tables and tries are about as fast unless you deal with ridiculously
long strings with the same, say, first 10 characters as a prefix.

Tries have another advantage; they grow better than hash tables
(lookup *always* takes about O(n) in length of string, regardless of
how big the trie is; closed hash tables often are worse than O(n) in
the length of the string for large tables and open hash tables often
need resizing, so they're only O(n) in the length of the string
amortized), but they're also nice from a functional point of view
because you can add nodes to a trie and retain the old one.

It's an interesting data structure to be sure, but not particularly
well known, when it is better than a hash table it is often not much
better, implementing them without wasting a great deal of space can be
very annoying, and various other caveats.  It is very useful for a
programmer in a purely functional language like Haskell because
Haskell doesn't *get* hash tables (copying the array around to update
one element is ridiculous but necessary), and I can see the use for a
symbol table in a compiler, but for the most part it's not really
worth bothering with, like splay trees[0].

It turns out that these data structures -- tries -- are exactly what I
was looking for.  I guess it's not important to explain why, because
what I'm doing is so specfic that it's not too interesting.  But since
you guys have been so helpful, I may as well try to thank you by
describing what I was doing.

I am making a huge string table.  There are times when I'll look up
the string "the" and, right afterwards, I might look up the string
"them".  In this case, it might help to retain the node that the "the"
got me to, and just keep going from there.  Either way, the point is
that there's a lot of shared data, and so the potential for these
tries in my code is great.  I was still hoping that someone would lend
me some code that implements tries (in CL, of course).  but otherwise,
I'll simply try to find out where the algorithms are documented and
redo the work.

but I have, very successfully, implemented keyless hash-tables (I call
them `array-tables'), and they perform comparably to ACL's built-in
hash-tables, and (in my opinion) are extremely easily integrated into
programs which use hash-tables.  I implementing a macro called
`array-table-loop', which lets you do things like:

(array-table-loop for entry being the array-table-values of atable
    [do|maximize|..etc..] ...[etc.])

so you can still get your hash-table iteration working.  CLOS made
making this very elegant, and it seems to run pretty fast.  Oh, and
one nice thing about the keyless array-tables: they arn't limited in
the :test that they can use.  so, for example, you can use
#'string-equal instead of #'equalp.  I think this is a big plus, and
I'm still wondering why ANSI CL limits the :test for hash-tables to
(member #'eql #'eq #'equal #'equalp).  I guess it's because
hash-tables in CL can store _any_ type of object, and #'string-equal,
#'char=, and friends don't operate on just any Lisp object.

The choice of test function is limited because the test function must
always correspond to a hash function (specifically, for any two keys A
and B, it must be that `A equals B' implies `hash(A) == hash(B)'; the
reverse needn't be true.)

    When those objects "move" their identity changes. The gc may
    change all of the references to the "new" identity, but the
    hash table was indirectly dependent upon those "old" ones. Namely
    your object will likely hash to different spot now.  

    That's OK. you can simply rehash the whole table before the next lookup.
    Or follow some other amortized resolution scheme.

    EQUAL and EQUALP should be uninpacted by this. They don't care because
    they're based on a different sense of identity.  So you need not only
    a test but also something that "says" what sort of policy you do
    post GC.    I think common lisp designers chose to let only the
    implementors worry about these issues.

   P.S.  this may mean that EQ is probably _not_ a good :TEST argument
         to your new construct.   You just may not have been bitten by
         it yet.
         [ if you exhaustively search the table until all keys are
            examined then fine. However, you can't really say that
            it has O(1) lookup characteristics.  ]

      You may have used  SXHASH in all cases regardless of resolution
      predicate.  The negates the problem of starting to "look"  in a
      different place. I'm not sure the designeres wanted to constrain the
      implementors to this or if this doesn't have hash code distrubution
      problems where there are more collisons than "necessary".
      [ For instance I think I posted an example where an implementation
        use the size of a vector as its SXHASH code, irregardless of
        contents.  A hash table of same size vectors would have horrific
        ( OK,  linear) performance in this case. ]

--

I wrote some tries just recently... I think I got the main idea from
AICP - I've read about them in many algorithm books, but they usually
make it seem much more complicated than it needs to be. These aren't
too `fancy', but that's what I like about them. Ideally you would be
able to specify the equality function and other such-nots...

;;; Tries

(defstruct (trie)
  (value nil)
  (arcs ())
  parent)

(defun follow-trie-no-extend (key trie)
  (cdr (assoc key (trie-arcs trie))))

(defun follow-trie-extending (key trie)
  (let ((arc (assoc key (trie-arcs trie))))
    (if arc (cdr arc)
        (let ((newtrie (make-trie :parent trie)))
          (push (cons key newtrie) (trie-arcs trie))
          newtrie))))

(defun find-trie-extending (key trie)
  (dotimes (i (length key) trie)
    (setq trie (follow-trie-extending (aref key i) trie))))

(defun find-trie (key trie)
  (loop for code across key
      for newtrie = (follow-trie-no-extend code trie)
        then (follow-trie-no-extend code newtrie)
      while newtrie do (setq trie newtrie)
      finally (return trie)))

(defun put-trie (key trie value)
  (setf (trie-value (find-trie-extending key trie)) value))

(defun get-trie (key trie)
  (let ((found (find-trie key trie)))
    (if (not found) nil
        (trie-value found))))

(defsetf get-trie put-trie)

(defvar *trie* (make-trie))

(setf (get-trie "them" *trie*) "Nope!")
(setf (get-trie "the" *trie*) "Closer")
(setf (get-trie "the dog" *trie*) "has hair")

(trie-value (find-trie "them" *trie*)) => "Nope!"
(trie-value (find-trie "the" *trie*)) => "Closer"
(get-trie " dog" (trie-parent (find-trie "them" *trie*))) => "has hair"