Consider an alphabetized list of words which has been compressed by replacing the characters repeated...

probability/prefix.overlap New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Consider an alphabetized list of words which has been compressed by
replacing the characters repeated between subsequent entries with a
count.  For example, "hello", "help" and "hi" are stored as:

[0] hello
[3] p
[1] i

The numbers in brackets are the counts of repeated characters.  This is
a common way of compressing keys stored in indices.  What is the
average length of the stored words?

For the sake of simplicity, we can:
1. Ignore the fixed overhead of the count of repeated characters
2. Assume some simple distribution of word lengths (e.g., uniform)

Four cases are of interest:
1. The simple case: The probability of a character in a word is the
   same for all characters.
2. The known probability case: The probability of a character is known
   but not necessarily the same for all characters.
3. The realistic case: The probability of a character or sequence of
   characters is known.
4. The unknown probability case: Nothing is known about the probability
   of characters.

Show solution

There is a recent preprint on this subject (for what you call the
simple model) by R. Simion and H. Wilf, "The distribution of prefix
overlap in consecutive dictionary entries."  They show, among other
things, that in a dictionary of D words, all of the same length, over
an alphabet of size A, the average prefix overlap is close to the
logarithm to the base A of D.  You can get a copy of the paper by
writing to

   Professor Herbert Wilf
   Department of Mathematics
   University of Pennsylvania
   Philadelphia, PA 19174

   Professor Rodica Simion
   Department of Mathematics
   Bryn Mawr
   Bryn Mawr, PA 19010

-- Andrew Odlyzko, AT&T Bell Laboratories <ihnp4!alice!amo>, June 1985

Try Knuth Vol III [Editor: was Vol II] "Sorting and Searching" Sec 6.3
p493 analysis of digital search tree algorithms.  The sizes of such
trees should give you the answers you want.

-- John G. Cleary, University of Calgary <ihnp4!alberta!calgary!vaxb!cleary>