5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ What is the question ? $\endgroup$ May 11, 2016 at 16:20
  • $\begingroup$ @JohannesTrost OP's question, as I understand it, is "for what $n$-letter words $U$ on an alphabet of size $σ$ is the cardinality of the ball of radius $k$ for the edit distance the greatest possible? what are the words and what is the maximum cardinality in question?" It's a reasonably well-posed question. $\endgroup$
    – Gro-Tsen
    May 11, 2016 at 17:05
  • $\begingroup$ Is there a particular regime of parameters $|\Sigma|, k, n$ that you're interested in? $\endgroup$
    – usul
    May 12, 2016 at 3:16
  • $\begingroup$ @Distance Thank you for adding a question. $\endgroup$ May 12, 2016 at 11:43

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.