paper6

Best algorithm for LZW ..C language

approximation can be developed for some of the cases.  It is shown by
Amble and Knuth [1] and Knuth [8] (problem 6.4-47) that the average
length of a block of consecutive non-empty locations when using
the optimum insertion strategy is approximately
$(1- alpha ) sup -2 ~-~1$.  
Let this block length be $L$.  
.pp
Consider the case of a successful search when no $A$ field is used.
A successful scan of a block from an arbitrary
position to the end takes on average $L/2~+~1/2$ probes.  
During the initial scan down the memory in the simulations the initial check of the
$V$ bit and the final empty location examined were each counted as a single probe.
This gives a total of $L/2~+~5/2$ probes for the initial scan down. (This is not
exact because there will be a correlation between the position 
of a key's home location within a block 
and the number of keys hashing to that home location).
The scan back up a block will take $L/2~+1/2$ probes (exact for a successful search).
This gives $(1- alpha ) sup -2 +2$ for the expected
number of probes during a successful search.  These values are listed in Table I
and are consistently low by about 10%.
.pp
For an unsuccessful search with no $A$ field the initial scan down the 
memory will take $L/2~+5/2$ probes as above (again this will not be exact because
the probability of a $V$ bit being one will be correlated with the 
size of a block and its
position within the block).
An unsuccessful scan of a block takes $L/2~+~1/2$ probes.  (This assumes
the keys in the block are distributed uniformly.  
This gives the following probabilities that the search will stop at a 
particular location in the block: the first location, $1/2L$; locations 2 
through $L$, $1/L$; the empty $(L+1)$st location, $1/~2L$.
This will not be true for compact hashing because the probability of stopping at a key
which shares its home location with a large number of other keys will be smaller than
for one which shares it with few others.)\ \ Summing these two terms gives $L~+~7/2$
probes.
Given that the keys are distributed randomly there is a probability of 
$e sup {- alpha}$ that a given $V$ bit will be zero.  So the expected number 
of probes overall for an unsuccessful search is 
$e sup {- alpha}~+~(1-e sup {- alpha}) cdot ((1- alpha ) sup -2 + 5/2)$.
These values are listed in Table II and are consistently low by about 5%.
.pp
Considering only the insertion component which is independent of Na then
it is possible to derive an expression for the number of probes.
There is an initial
scan to move the memory down and insert the new key which will scan about half 
the block ($L/2~+~5/2$ probes) 
and a subsequent scan back up of the entire block ($L~+~1$ probes).  
Empirically the probability
that the entire block will subsequently be moved back up is a half which gives
an expected $1/2(L~+~1)$ probes.
Summing these three contributions gives $2(1- alpha ) sup -2 ~+~2$
as the expected number of probes for an insertion (excluding the search time).
Values for this expression are tabulated  in Table III, they are in good 
agreement with the empirical values.
.sh "Acknowledgements"
.pp
I would like to thank Ian Witten for careful checking of a draft version.
Also John Andreae for discussions which showed that something like compact
hashing might be possible.
.sh "References"
.ls 1
.LB "[6]    "
.sp
.NI "[1]  "
[1]\ \ O.\ Amble and D.\ E.\ Knuth, "Ordered Hash Tables,"
.ul
Computer Journal,
vol. 17, pp135-142, 1974.
.sp
.NI "[1]  "
[2]\ \ J.\ H.\ Andreae,
.ul
Thinking with the teachable machine.
London: Academic Press, 1977.
.sp
.NI "[1]  "
[3]\ \ J.\ L.\ Carter and M.\ N.\ Wegman, "Universal classes of hash 
functions,"
.ul
J. Computer System Sci.,
vol. 18, pp143-154, 1979.
.sp
.NI "[2]  "
[4]\ \ J.\ G.\ Cleary, "Compact hash tables,"
Research Report, 82/100/19,
Department of Computer Science, University of Calgary, July 1982.
.sp
.NI "[3]  "
[5]\ \ J.\ G.\ Cleary, "Random insertion for bidirectional linear probing
can be better than optimum," 
Research Report, 82/105/24,
Department of Computer Science, University of Calgary, September 1982.
.sp
.NI "[5]  "
[6]\ \ J. A. Feldman and J. R. Low, "Comment on Brent's Scatter Storage 
Algorithm,"
.ul
CACM,
vol. 16, p703, 1973.
.sp
.NI "[7]  "
[7]\ \ G. D. Knott, "Hashing functions,"
.ul
The Computer Journal,
vol. 18, pp265-278, 1975.
.sp
.NI "[7]  "
[8]\ \ D.\ E.\ Knuth, 
.ul
The art of computer programming:Sorting and searching.
Vol III.
Reading, Massachusetts: Addison Wesley, 1973.
.sp
.NI "[8]  "
[9]\ \ V.\ Y.\ Lum, "General performance analysis of key-to-address 
transformation methods using an abstract file concept,"
.ul
CACM,
vol. 16, pp603-612, 1973.
.sp
.NI "[12]  "
[10]\ \ V.\ Y.\ Lum,\ P.\ S.\ T.\ Yuen and M.\ Dodd, "Key-to-address
transformation techniques,"
.ul
CACM,
vol. 14, pp228-239, 1971.
.sp
.NI "[13]  "
[11]\ \ W. D. Maurer and T. G. Lewis, "Hash table methods,"
.ul
Comp. Surveys,
vol. 7, pp5-19, 1975.
.ls 2
.in 0
.bp 0
\&\ 
.RF
.ta 0.5i +0.75i +0.75i +0.75i +0.75i +0.75i
.nf

	$i	T[i]	R[i]	V[i]	C[i]$
	\l'3.5i'
.br

	12	\0\ -1	\ -1	0	1
.br
	11	101	\01	0	1
.br
	10	\087	\07	1	1
.br
	\09	\076	\06	0	0
.br
	\08	\075	\05	1	1
.br
	\07	\067	\07	1	0   
.br
	\06	\066	\06	1	0
.br
	\05	\065	\05	0	1
.br
	\04	\041	\01	1	1
.br
	\03	\0\ -1	\ -1	0	1
.br
	\02	\019	\09	0	0
.br
	\01	\018	\08	1	0
.br
	\00	\016	\06	0	1
.br
					     Step 1 Step 2 Step 3 Step 4
.br

	$h(H)~=~ left floor^ H/10 right floor$
.br

	$r(H)~=~ H~ roman mod ~10$
.br

.FG ""

.bp 0
\&\ 
.RF
.nf
.ta 0.5i +0.75i +0.75i +0.75i +0.75i
	$count~=~A[i]~=~#C[i]-#V[i]$
.sp
	$count = 0$			$count = 0$
	$C$	$V$		$C$	$V$
	0\|\(rt	1		0\|\(rt	1
	0\|\(rk	0		0\|\(rk	1$<-~i$
	1\|\(rb	1$<-~i$		1\|\(rb	0
.sp
	$count =1>0$		$count = 2 > 0$
	$C$	$V$		$C$	$V$
	0	1$<-~i$		0	1$<-~i$
	1	0		1	0
	0\|\(rt	1		1	1
	0\|\(rk	0		0\|\(rt	0
	1\|\(rb	0		0\|\(rk	0
				1\|\(rb	0
.sp
	$count =-1<0$
	$C$	$V$
	0\|\(rt	0			\|\(rt
	0\|\(rk	0			\|\(rk\ \ Group of entries which hash to 
	1\|\(rb	0			\|\(rb\ \ location i
	0	0
	1	1$<-~i$			\ \ \ Corresponding $C$ and $V$ bits
.FG ""
.bp 0
\&\ 
.RF
.ta 0.5i +0.5i +0.5i +0.5i +0.5i +0.9i +0.6i +0.4i
$i	R[i]	V[i]	C[i]	#V[i]	#C[i]~~#C[i]-#V[i]	A[i]$
.br
\l'4.5i'
.br
12	\ -1	0	1	6	6	\00	0
.br
11	\01	0	1	6	6	\00	0
.br
10	\07	1	1	6	5	\ -1	$inf$
.br
\09	\06	0	0	5	4	\ -1	$inf$
.br
\08	\05	1	1	5	4	\ -1	$inf$
.br
\07	\07	1	0	4	3	\ -1	$inf$
.br
\06	\06	1	0	3	3	\00	0
.br
\05	\05	0	1	2	3	\01	$inf$
.br
\04	\01	1	1	2	2	\00	0
.br
\03	\ -1	0	1	1	1	\00	0
.br
\02	\09	0	0	1	1	\00	0
.br
\01	\08	1	0	1	1	\00	0
.br
\00	\06	0	1	0	1	\01	$inf$
.br
								Step 1 Step 2 Step 3 Step 4
.sp 
Note: 	Only one bit has been allowed for the values of $A$. 
.br
	So the only two possible values are 0 and $inf$.

.FG ""
.bp 0
\&\ 
.RF
.ta 1.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i
.ce
Successful Search
	\l'4i'

	$alpha$	\0.25	\0.5	\0.75	\0.8	\0.85	\0.9	\0.95
	\l'4i'
	
	$BLP sup 1$	\0\01.1	\0\01.3	\0\01.7	\0\02.0	\0\02.3	\0\02.9	\0\04.2
	
	Na
	15	\0\01.1	\0\01.3	\0\01.7	\0\01.9	\0\02.2	\0\02.8	\0\04.6
	\07	\0\01.1	\0\01.3	\0\01.7	\0\01.9	\0\02.2	\0\02.8	\0\09.7
	\03	\0\01.1	\0\01.3	\0\01.7	\0\01.9	\0\02.4	\0\04.2	\025
	\01	\0\01.1	\0\01.3	\0\02.0	\0\02.5	\0\04.1	\0\08.8	\045
	\00	\0\01.1	\0\01.5	\0\03.3	\0\04.9	\0\07.9	\015	\061
	\0-	\0\04.2	\0\07.1	\020	\030	\049	110	370
	\0*	\0\03.77	\0\06.00	\018.0	\027.0	\046.4	102	402

		$\& sup 1~$Taken from Amble and Knuth [1].
		- No $A$ field used.
		* Analytic approximation to line above.
.FG ""
.bp 0
\&
.RF
.ta 1.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i
.ce
Unsuccessful Search
	\l'4i'

	$alpha$	\0.25	\0.5	\0.75	\0.8	\0.85	\0.9	\0.95
	\l'4i'

	$BLP sup 1$	\0\01.3	\0\01.5	\0\02.1	\0\02.3	\0\02.6	\0\03.1	\0\04.4

	Na
	15	\0\01.2	\0\01.4	\0\01.8	\0\01.9	\0\02.1	\0\02.4	\0\03.5
	\07	\0\01.2	\0\01.4	\0\01.8	\0\01.9	\0\02.1	\0\02.4	\0\09.7
	\03	\0\01.2	\0\01.4	\0\01.8	\0\01.9	\0\02.2	\0\03.3	\015
	\01	\0\01.2	\0\01.4	\0\01.9	\0\02.2	\0\03.2	\0\06.0	\028
	\00	\0\01.2	\0\01.5	\0\02.6	\0\03.4	\0\05.3	\0\09.9	\036
	\0-	\0\01.7	\0\03.4	\011	\016	\028	\064	220
	\0*	\0\01.72	\0\03.16	\010.2	\015.6	\027.3	\061.2	247

		$\& sup 1~$Taken from Amble and Knuth [1].
		- No $A$ field used.
		* Analytic approximation to line above.
.FG ""
.bp 0
\&
.RF
.ta 1.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i
	\l'4i'

	$alpha$	\0.25	\0.5	\0.75	\0.8	\0.85	\0.9	\0.95
	\l'4i'

		\0\04.3	\0\08.8	\032	\049	\086	200	700
	*	\0\04.56	\0\09.00	\033.0	\051.0	\089.9\
	201	801

	* Analytic approximation to line above
.FG ""
.bp 0
\&
.ce 
List of Figures
.sp 2
Fig. 1. Example of compact hash memory and search for key.
.sp 2
Fig. 2. Examples showing different values of $#C[i]-#V[i]$.
.sp 2
Fig. 3. Example of calculation and use of array $A$.
.sp 2
.ce
List of Tables
.sp 2
Table I. Average number of probes during a successful search.
.sp 2
Table II. Average number of probes during an unsuccessful search.
.sp 2
Table III. Average number of probes to move block of memory.
.sp 2