2
$\begingroup$

Suppose I have a set of alphabet $\Sigma = \{ A,B,\ldots,Z \}$ with $|\Sigma|=26$. I am generating a set of $n$ random strings $S$, with each string of length $k$ from the alphabet (for the random string, each letter in a position is picked with probability $p=\frac{1}{|\Sigma|}$).

I want to find out:

  1. the expected length of longest common prefix
  2. the maximum length of longest common prefix with high probability.

I am working on a radix-tree based algorithm and want to justify the expected length of search operation theoretically.

$\endgroup$

1 Answer 1

1
$\begingroup$

Suppose we are selecting $n$ strings of length $k$ over an alphabet of $m$ letters. Classifying by the length $q$ of the longest common prefix we obtain for the total count of strings

$$m^k + \sum_{q=0}^{k-1} m^q (m^n - m) m^{n(k-1-q)}.$$

This simplifies to

$$m^k + (m^n - m) m^{n(k-1)} \sum_{q=0}^{k-1} m^q m^{-nq} \\ = m^k + (m^n - m) m^{n(k-1)} \sum_{q=0}^{k-1} m^{q(1-n)} \\ = m^k + (m^n - m) m^{n(k-1)} \frac{m^{(1-n)k}-1}{m^{1-n}-1} \\ = m^k + (m^n - m) m^{n(k-1)} \frac{m^{k-(k-1)n}-m^n}{m-m^n} \\ = m^k - m^{n(k-1)} \times (m^{k-(k-1)n}-m^n) \\ = m^k - m^k + m^{nk} = m^{nk}.$$

We have all of them and the sanity check goes through. The trick here was that we can view these $n$ strings as a rectangular array with $n$ rows and $k$ columns. Supposing that the first $q$ columns are the same the next column must not consist of $n$ identical letters or else the common prefix would extend to include it. That means we have $m^n-m$ choices for the letters in said column (there are $m$ strings of length $n$ containing a single letter.)

Now for the expectation we get

$$k m^k + \sum_{q=0}^{k-1} q m^q (m^n - m) m^{n(k-1-q)} \\ = k m^k + (m^n - m) m^{n(k-1)} \sum_{q=0}^{k-1} q m^q m^{-nq} \\ = k m^k + (m^n - m) m^{n(k-1)} \sum_{q=0}^{k-1} q m^{q(1-n)}.$$

Now we have

$$x\left(\sum_{p=0}^{k-1} x^p\right)' = \sum_{p=0}^{k-1} p x^p = x \left(\frac{x^k-1}{x-1}\right)' = x \frac{k x^{k-1}}{(x-1)} - x \frac{x^k-1}{(x-1)^2}.$$

Apply this to the sum to get two terms, the first of which is

$$k m^k + (m^n - m) m^{n(k-1)} m^{1-n} \frac{k m^{(1-n)(k-1)}}{m^{1-n}-1} \\ = k m^k + (m^n - m) m^{n(k-1)} m \frac{k m^{(1-n)(k-1)}}{m-m^n} \\ = k m^k - m^{n(k-1)} m k m^{(1-n)(k-1)} = 0.$$

The second is

$$- (m^n - m) m^{n(k-1)} m^{1-n} \frac{m^{(1-n)k}-1}{(m^{1-n}-1)^2} \\ = - (m^n - m) m^{n(k-1)} m^{n+1} \frac{m^{(1-n)k}-1}{(m-m^n)^2} \\ = m^{n(k-1)} m^{n+1} \frac{m^{(1-n)k}-1}{m-m^n} \\ = m^{nk} \frac{1-m^{(1-n)k}}{m^{n-1}-1}$$

Divide by $m^{nk}$ to get for the expected longest common prefix

$$\frac{1-m^{(1-n)k}}{m^{n-1}-1}.$$

The following Maple code was used to verify this formula.

Q :=
proc(n, k, m)
option remember;
    local d, ind, pref, pos, res, idx1, idx2;

    res := 0;

    for ind from m^(n*k) to 2*m^(n*k)-1 do
        d := convert(ind, base, m);

        for pref from 0 to k-1 do
            for pos from 1 to n-1 do
                idx1 := (pos-1)*k + pref;
                idx2 := pos*k + pref;

                if d[idx1+1] <> d[idx2+1] then
                    break;
                fi;
            od;

            if pos < n then
                break;
            fi;
        od;

        res := res + pref;
    od;

    res/m^(n*k);
end;

X := (n, k, m) -> (1-m^((1-n)*k))/(m^(n-1)-1);
$\endgroup$
5
  • $\begingroup$ Thanks a lot. This really helps boosting my understanding of the problem. $\endgroup$
    – max
    Commented May 13, 2016 at 2:36
  • $\begingroup$ I have run some experiments: Here number of strings $n=256000000$, $k=8$ and $m=256$. (that is I generated 256M random 8-byte integers. Each byte is considered as a symbol.) I calculated the average length to be $4.06$, which does not seem to match to your calculation. $\endgroup$
    – max
    Commented May 16, 2016 at 18:30
  • $\begingroup$ I have obviously misunderstood your question. I am not quite sure what the correct interpretation is. It seems very unlikely that when you have 256M random 8-byte integers they would all agree on the first four bytes. Intuitively this seems impossible, so you must be using a different interpretation of the problem. $\endgroup$ Commented May 16, 2016 at 21:30
  • $\begingroup$ Maybe I could not present the question in the clearest way. I found that in a run with $256$M random $64$-bit integers (generated with $64$-bit Mersenne Twister), there are $224$ numbers, each of which has a common prefix of $6$ bytes with another number. $\endgroup$
    – max
    Commented May 17, 2016 at 18:42
  • $\begingroup$ I see now that the idea and the methodology of my answer above are completely inappropriate to your problem. I would delete my post if that were possible. It would be very kind of you indeed if you were to re-write your question including the explanation that you provided in your last comment and make it into a new post, so we can end activity on this one. I am sure there are people here on MSE who can find an answer for you. $\endgroup$ Commented May 17, 2016 at 21:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .