home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / prolog / 2035 < prev    next >
Encoding:
Internet Message Format  |  1992-11-06  |  1.3 KB
  1. Path: sparky!uunet!charon.amdahl.com!pacbell.com!decwrl!hal.com!olivea!charnel!rat!usc!zaphod.mps.ohio-state.edu!sdd.hp.com!scd.hp.com!hpscdm!hplextra!otter.hpl.hp.com!hpltoad!toad.hpl.hp.com!dg
  2. From: dg@dgupta.hpl.hp.com (Dipankar Gupta)
  3. Newsgroups: comp.lang.prolog
  4. Subject: Re: collapsing lists to tree
  5. Message-ID: <DG.92Nov5105000@dgupta.hpl.hp.com>
  6. Date: 5 Nov 92 10:50:00 GMT
  7. References: <Bx5CFy.I6F@gabriel.keele.ac.uk>
  8. Sender: news@hplb.hpl.hp.com (Usenet News Administrator)
  9. Organization: Hewlett-Packard Laboratories, Bristol, UK
  10. Lines: 36
  11. In-Reply-To: csa09@keele.ac.uk's message of 3 Nov 92 15:31:09 GMT
  12. Nntp-Posting-Host: dgupta.hpl.hp.com
  13.  
  14.  
  15.    I wish to collapse a list of lists into a tree by recursively factoring
  16.    out common initial elements, e.g.
  17.  
  18.        [ [ a, b, l, e],
  19.      [ a, b, o],
  20.      [ a, b, o, r, t],
  21.      ...
  22.  
  23.    into
  24.  
  25.      - a - b - l - e - []
  26.          \
  27.            o - []
  28.          \
  29.            r - t - []
  30.  
  31.    Is there an established name for this latter data structure?  Is there
  32.    published code for creating it?
  33.  
  34. Rule #1 for Algorithms: Look up Knuth.
  35.  
  36. In this particular case:
  37. Knuth, D. E. The Art of Computer Programming
  38. Vol 3 Sorting & Searching
  39. pp 481-489
  40.  
  41. The data-structure you're talking about is called a ``Trie''.
  42. For a neato application, have a look at the TeX source code...
  43.  
  44. Cheers,
  45. Dipankar Gupta
  46. HP Labs Bristol UK
  47. dg@hplb.hpl.hp.com
  48. --
  49. --
  50.