Article View: comp.lang.prolog
Article #1562Re: collapsing lists to tree
From: Dipankar Gupta
Date: Thu, 05 Nov 1992 10:50
Date: Thu, 05 Nov 1992 10:50
36 lines
1413 bytes
1413 bytes
I wish to collapse a list of lists into a tree by recursively factoring
out common initial elements, e.g.
[ [ a, b, l, e],
[ a, b, o],
[ a, b, o, r, t],
...
into
- a - b - l - e - []
\
o - []
\
r - t - []
Is there an established name for this latter data structure? Is there
published code for creating it?
Rule #1 for Algorithms: Look up Knuth.
In this particular case:
Knuth, D. E. The Art of Computer Programming
Vol 3 Sorting & Searching
pp 481-489
The data-structure you're talking about is called a ``Trie''.
For a neato application, have a look at the TeX source code...
Cheers,
Dipankar Gupta
HP Labs Bristol UK
dg@hplb.hpl.hp.com
--
--
Technical Details
Message-ID:
<DG.92Nov5105000@dgupta.hpl.hp.com>Path:
arc1-ca.pugleaf.net!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!dgReferences:
<Bx5CFy.I6F@gabriel.keele.ac.uk>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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 From: dg@dgupta.hpl.hp.com (Dipankar Gupta) Newsgroups: comp.lang.prolog Subject: Re: collapsing lists to tree Message-ID: <DG.92Nov5105000@dgupta.hpl.hp.com> Date: 5 Nov 92 10:50:00 GMT References: <Bx5CFy.I6F@gabriel.keele.ac.uk> Sender: news@hplb.hpl.hp.com (Usenet News Administrator) Organization: Hewlett-Packard Laboratories, Bristol, UK Lines: 36 In-Reply-To: csa09@keele.ac.uk's message of 3 Nov 92 15:31:09 GMT Nntp-Posting-Host: dgupta.hpl.hp.com