5
$\begingroup$

I would like to know the number of strings at edit distance $n$ of a string $s$.

I guess this is textbook knowledge... but I cannot find the textbook in question.

More formally, I have an alphabet $\Sigma$ (in my case, $|\Sigma| = 4$), and I consider all the words in $\Sigma^*$. I use the edit distance $d$. I am looking for the number of words at distance $n$ of a word $w \in \Sigma^*$. Namely,

$ f_1(w, n) = \lvert \{ w' \in \Sigma^*: d(w, w') = n \} \rvert $

I need the maximum size, considering all the words of a given length. Namely:

$ f_2(s, n) = \max_{w,\ |w| = s}(f_1(w, n)) $

In practice, I have to compute a table of $f_2$ with $s \in [0, 100]$, and $n \in [0, 5]$, so I can compute $f_2$ recursively.

I tried to read the original Levenshtein paper, but it seems to deal with binary alphabets only.

What I had in mind, is that $f_2(s, n)$ can be computed with $f_2(s, n-1)$, and adding an error: insertion, deletion, substitution.

$ f_2(s, n) = (s+1) |\Sigma| f_2(s, n-1) + s f_2(s, n-1) + s (|\Sigma|-1) f_2(s, n-1)$

I know it is not strict bound, because deleting a (previous inserted) insertion should not count. But am I far from true?

With the previous recursion (and knowing that $f_2(s, 0) = 1$), I would have:

$ f_2(s, n) = (|\Sigma| (2s + 1))^n $

Is there a better bound?

|cite|improve this question
$\endgroup$
  • $\begingroup$ I have asked a very similar thing before. I don't think this is an easy problem. $\endgroup$ – Raphael♦ Apr 25 at 13:57
  • $\begingroup$ @Raphael Yes, I saw your question. But I thought that would somehow "correct" a word. In this case, the search space is (somewhat) more limited. $\endgroup$ – unamourdeswann Apr 25 at 14:04
  • $\begingroup$ You're looking at a different metric, but other than that I think we're interested in the same thing. Mixing notation, $|\{w\}_k| = f_1(w, k)$. The final goal differs, though: you're looking for (bounds on) the maximal value for word length $n$ whereas I was looking for complexity of computing the exact number for a given set of words. $\endgroup$ – Raphael♦ Apr 25 at 14:09
  • $\begingroup$ Correcting words was the initial motivation for me; I was aiming at a rough idea of how much a dictionary would explode if annotated with all close-enough words. $\endgroup$ – Raphael♦ Apr 25 at 14:11
  • $\begingroup$ @Raphael Interesting question! $\endgroup$ – unamourdeswann Apr 25 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.