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
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
>
>

- Raw text -