![](https://csdnimg.cn/release/download_crawler_static/1517869/bga.jpg)
40 G. Navarro
Fig. 2. The DAWG or the suffix automaton for the sample string. If all the states are final, it is a DAWG.
If only the 2nd, 5th and rightmost states are final then it is a suffix automaton.
interesting in itself, but also essential for
the average case analysis of many search
algorithms, as will be seen later. We now
present the existing results and an empir-
ical validation. In this section we consider
the edit distance only. Some variants can
be adapted to these results.
The effort in analyzing the probabilistic
behavior of the edit distance has not given
good results in general [Kurtz and Myers
1997]. An exact analysis of the probability
of the occurrence of a fixed pattern allow-
ing k substitution errors (i.e. Hamming
distance) can be found in R
´
egnier and
Szpankowski [1997], although the result
is not easy to average over all the possi-
ble patterns. The results we present here
apply to the edit distance model and, al-
though not exact, are easier to use in
general.
The result of R
´
egnier and Szpankowski
[1997] holds under the assumption that
the characters of the text are indepen-
dently generated with fixed probabilities,
i.e. a Bernoulli model. In the rest of this
paper we consider a simpler model, the
“uniform Bernoulli model,” where all the
characters occur with the same probabil-
ity 1/σ . Although this is a gross simplifi-
cation of the real processes that generate
the texts in most applications, the results
obtained are quite reliable in practice. In
particular, all the analyses apply quite
well to biased texts if we replace σ by 1/ p,
where p is the probability that two ran-
dom text characters are equal.
Although the problem of the average
edit distance between two strings is closely
related to the better studied LCS, the
well known results of Chv
´
atal and Sankoff
[1975] and Deken [1979] can hardly be ap-
plied to this case. It can be shown that the
average edit distance between two random
strings of length m tends to a constant
fraction of m as m grows, but the frac-
tion is not known. It holds that for any
two strings of length m, m − lcs ≤ ed ≤
2(m − lcs), where ed is their edit distance
and lcs is the length of their longest com-
mon subsequence. As proved in Chv
´
atal
and Sankoff [1975], the average LCS is be-
tween m/
√
σ and me/
√
σ for large σ , and
therefore the average edit distance is be-
tween m (1−e/
√
σ ) and 2m (1−1/
√
σ ). For
large σ it is conjectured that the true value
is m (1 − 1/
√
σ ) [Sankoff and Mainville
1983].
For our purposes, bounding the proba-
bility of a match allowing errors is more
important than the average edit distance.
Let f (m, k) be the probability of a random
pattern of length m matching a given text
position with k errors or less under the edit
distance (i.e. the text position is reported
as the end of a match). In Baeza-Yates
and Navarro [1999], Navarro [1998], and
Navarro and Baeza-Yates [1999b] upper
and lower bounds on the maximum error
level α
∗
for which f (m, k) is exponentially
decreasing on m are found. This is impor-
tant because many algorithms search for
potential matches that have to be verified
later, and the cost of such verifications is
polynomial in m, typically O(m
2
). There-
fore, if that event occurs with probability
O(γ
m
) for some γ<1 then the total cost
of verifications is O(m
2
γ
m
) = o(1), which
makes the verification cost negligible.
We first show the analytical bounds for
f (m, k), then give a new result on average
ACM Computing Surveys, Vol. 33, No. 1, March 2001.