Neighbourhood of a word and Levenshtein distance

Question

The Levenshtein distance or Edit distance $$ lev(U,V) $$ between two strings $U$ and $V$ over a finite alphabet $\Sigma$ of size $ \left| \Sigma \right| = \sigma ,$ is the minimal number of insertions, deletions and replacements to make the strings equal.

For $k \in \mathbb{N} $ and $U \in \Sigma^*$ we define :

$$ N_k(U) = \{ V \in \Sigma^* : lev(U,V) \leq k \} $$

For example if $\Sigma = \{A,B,L\}$ :

\begin{eqnarray*} N_1(AAA) &=& \{ AAA, AA, AAB, AAL, ABA, ALA, BAA, LAA, AAAA, BAAA, \\ &&LAAA, ABAA, ALAA, AABA, AALA, AAAB, AAAL \} \\ N_1(LAB) &=& \{LAB, LA, AB, LB, AAB, BAB, LBB, LLB, LAA, LAL, ALAB, \\ &&BLAB, LLAB, LAAB, LBAB, LALB, LABA, LABB, LABL\} \end{eqnarray*}

My goal is to compute for $\Sigma, n $ and $k$ fixed :

$$ \max_{U \in \Sigma^* , ~ \left| U \right| = n} \left|N_k(U) \right| $$

or an upper bound $f(\Sigma,k,n)$.

I conjecture that the maximum is reached for the words of the form :

$$ c_1c_2 \dots c_{\sigma}c_1c_2 \dots c_{\sigma}\dots $$

where $\Sigma = \{ c_1,c_2, \dots,c_{\sigma} \}. $

Does anyone have an idea of how to compute $ \max_{U \in \Sigma^* , ~ \left| U \right| = n} \left|N_k(U) \right| $ or to prove this conjecture?

A special case has already been studied in the section 6 of the paper What's Behind Blast by Gene Myers.

Answer 1

I can give a partial answer for the analogous question about deletion distance, the variant of edit distance where insertions and deletions are the only basic operations. Substitutions must be performed as a deletions plus and insertion, so their cost is larger than in the metric you gave.

Let $d(U,V)$ be the number deletions and insertions required to convert $U$ to $V$. For $U \in \Sigma^n$, let $N_{a,b}(U) = \{ V \in \Sigma^{n-a+b} : d(U,V) \leq a+b\}$. Let $q = |\Sigma|$.

For all $X \in \Sigma^n$, the size of the insertion ball is the same: $|N_{0,b}(X)| = \sum_{i = 0}^b \binom{n+b}{i}(q-1)^i$. The size of the deletion ball, $|N_{a,0}(X)|$ varies with $X$ and we have the trivial upper bound $|N_{a,0}(X)| \leq \binom{n}{a}$. Each $Y \in N_{a,b}(X)$ has a common substring of length $n-a$ with $X$, so $|N_{a,b}(X)| \leq \binom{n}{a} \sum_{i = 0}^b \binom{n-a+b}{i}(q-1)^i$. For $n \to \infty$ with $a$ and $b$ fixed, this bound is asymptotic to $\binom{n}{a}\binom{n}{b}(q-1)^b$.

Let $\Sigma = \{0,1\}$ and let $X_n$ be the length-$n$ string of alternating zeros and ones. It is not hard to show that $N_{a,b}(X_n) = N_{0,a+b}(X_{n-2a})$, so $|N_{a,b}(X_n)| = \sum_{i = 0}^{a+b} \binom{n-a+b}{i} \sim \binom{n}{a+b}$. This is a factor of $\binom{a+b}{a}$ below the asymptotic upper bound of $\binom{n}{a}\binom{n}{b}$.

However, we can construct other binary strings that do meet the asymptotic upper bound. Let $m \approx \sqrt{n}$ and let it be odd so $X_m$ begins and ends with zero. Let $Y_n = X_m + 10001 + X_m + 10001 + \ldots + X_m + 10001$. If we perform $a$ deletions and $b$ insertions on $Y_n$ such that at most one insertion or deletion is inside each copy of $X_m$ and none are inside the 10001 segments, we produce each member of $N_{a,b}(Y_n)$ at most once because we do not create or destroy any runs of length three in $Y_n$. Thus $|N_{a,b}(Y_n)| \geq \binom{n/(m+5)}{a+b}\binom{a+b}{a}m^a(m+2)^b \sim \frac{(n/m)^{a+b}}{a!b!} m^{a+b} \sim \binom{n}{a}\binom{n}{b}$.

Your question asks about the analogue of $\bigcup_{0 \leq i \leq k, 0 \leq j \leq k} N_{i,j}(X)$. For fixed $k$, only the contribution of $N_{k,k}(X)$ matters asymptotically.

I am not sure how easily these arguments can be adapted to edit distance allowing replacements, but hopefully this provides a helpful starting point.

My paper about an upper bound on the size of deletion correcting codes applies some variants of these ideas.

Answer 2

A recent paper by Hélène Touzet discusses how to compute the size of the neighborhood of a given word via the Universal Levenshtein automaton.

"On the Levenshtein Automaton and the Size of the Neighbourhood of a Word" (unfortunately not freely available online yet).

Maybe it is possible to exploit the structure of the universal DFA or to at least do some practical experiments regarding your conjecture.