Path: utzoo!attcan!uunet!van-bc!sl
From: sl@van-bc.UUCP (pri=-10 Stuart Lynne)
Newsgroups: comp.mail.uucp
Subject: Re: Making /usr/lib/uucp/paths a _binary_ database
Keywords: pathalias UUCP smail
Message-ID: <2126@van-bc.UUCP>
Date: 9 Jan 89 05:58:25 GMT
References: <486@fallst.UUCP> <490@gonzo.UUCP> <307@twwells.uucp>
Reply-To: sl@van-bc.UUCP (pri=-10 Stuart Lynne)
Organization: Wimsey Associates, Vancouver, BC.
Lines: 65

In article <307@twwells.uucp> bill@twwells.UUCP (T. William Wells) writes:
>In article <490@gonzo.UUCP> daveb@gonzo.UUCP (Dave Brower) writes:
>: In article <486@fallst.UUCP> tkevans@fallst.UUCP (Tim Evans) writes:
>: >I'm not very proficient at C, but it seems that since 'paths' is
>: >essentially a two-field set of records it ought not be terribly
>: >hard to make 'pathalias' generate a binary database file.
>:
>: The first question is "what you would gain?"
>
>The answer is:
>
>I designed a compression method just for the paths database. While I
>haven't actually implemented it, my back-of-the-envelope estimate of
>the compressed size of the database is 175K, as compared to the 873K
>it currently takes (on my system).
>
>: A binary format that was significantly smaller would also be much more
>: cpu and disk i/o intensive to access.
>

Actually there is a simple hack to pathalias and smail type programs which
can reduce the size of the paths file substantially, leaving it in ascii.

The tradeoff is access time vs. size.

Specifically the paths file consists of lines like:

	a 	e!d!c!b!a!%s
	b	e!d!c!b!%s
	c	e!d!c!%s
	d	e!d!%s
	e	%s

This can be replaced by a recursive definition like:

	a	b!a!%s
	b	c!b!%s
	c	d!%!s
	d	e!%!s
	e	%s

To produce this file a small change to pathalias is required to simply
trim all prefix's from the beginning of the path (except for one hop).

To use the file modify the client program to recursively search until a
terminal node is reached (in this case node e).

For example mail to a!aperson:

	b!a!%s	->	a!aperson and search for b
	c!b!%s	->	b!a!aperson and search for c
	d!c!%s	->	c!b!a!aperson and search for d
	e!d!%s	->	d!c!b!a!aperson

This method is quite suitable for a small site with limited disk resources
that doesn't forward a great quantity of mail.

I tried this about a year and a half back. It worked fine. Saved about 50%.
Took me a couple of hours. Probably take a competant person somewhat less.

The mod's to the client program can be done so that it will work with
either the original or modified format.

-- 
Stuart.Lynne@wimsey.bc.ca {ubc-cs,uunet}!van-bc!sl     Vancouver,BC,604-937-7532