Mailing-List: contact cygwin-developers-help AT cygwin DOT com; run by ezmlm
List-Subscribe: <mailto:cygwin-developers-subscribe AT cygwin DOT com>
List-Archive: <http://sources.redhat.com/ml/cygwin-developers/>
List-Post: <mailto:cygwin-developers AT cygwin DOT com>
List-Help: <mailto:cygwin-developers-help AT cygwin DOT com>, <http://sources.redhat.com/ml/#faqs>
Sender: cygwin-developers-owner AT cygwin DOT com
Delivered-To: mailing list cygwin-developers AT cygwin DOT com
From: "Jim Mochel" <jmochel AT foliage DOT com>
To: "Robert Collins" <rbcollins AT cygwin DOT com>, <cygwin-developers AT cygwin DOT com>
Subject: RE: Contemplating drastic change to mount handling
Date: Fri, 6 Sep 2002 12:39:36 -0400
Message-ID: <BAEPJILLDMOHFGEJMLNKMEKCGCAA.jmochel@foliage.com>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 8bit
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
In-Reply-To: <1031328784.1363.37.camel@lifelesswks>
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Importance: Normal

I figure I would mention that there is a _much_ more compact representation
than single character tries that is also fairly easy to construct.
It is called a Multi-character Trie (or McTrie)

It is almost unknown outside of the IR community but it is fairly easy to
code for
and is usually more compact than a read optimized B+Tree and faster for
retrieval than
a single character trie.

Information Processing and Management: an International Journal >archive
Volume 29 ,  Issue 2   March-April 1993 >toc
Multi-character tries for text searching
Authors
 Lorraine K. D. Cooper
 Alan L. Tharp

Publisher
 Pergamon Press, Inc.  
  Tarrytown, NY, USA
  Pages: 197 - 207  Periodical-Issue-Article
  Year of Publication: 1993
  ISSN:0306-4573


If you local library can't get you access to a copy I can fax you mine.

Jim Mochel


> -----Original Message-----
> From: cygwin-developers-owner AT cygwin DOT com
> [mailto:cygwin-developers-owner AT cygwin DOT com]On Behalf Of Robert Collins
> Sent: Friday, September 06, 2002 12:13 PM
> To: cygwin-developers AT cygwin DOT com
> Subject: Re: Contemplating drastic change to mount handling
>
>
> On Fri, 2002-09-06 at 22:52, Earnie Boyd wrote:
>
> >
> > I need educated on "trie".  Do you mean tree or is it something else?
>
> http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Trie.html is a nice
> compact summary.
>
> Rob
>
>