4
$\begingroup$

As input we are given a string $s$ comprising $n$ tokens from a vocabulary of size $m$. We are asked to count the number of strings from the same vocabulary that are at a particular edit distance of $k$ away from $s$.

Is there an efficient algorithm in $n$, $m$, and $k$ for this problem?

$\endgroup$
2
  • $\begingroup$ Is transposition considered an edit or only substitution, insertion and deletion? $\endgroup$
    – Pushpendre
    Oct 6, 2016 at 5:07
  • $\begingroup$ Only insertion, deletion, and substitution are allowed. $\endgroup$
    – Norouzi
    Oct 28, 2016 at 5:03

2 Answers 2

1
$\begingroup$

You can look into Levenshtein automaton. The main references are Fast String Correction with Levenshtein-Automata by Schulz and Mihov and Deciding word neighborhood with universal neighborhood automata by Mitankin, Mihov, and Schulz. There is an implementation called liblevenshtein which you can play with online here.

This algorithm gives you all words at distance at most $k$ from your string. So to get words that are at distance exactly $k$ you must remove the words at distance less than or equal to $k-1$.

$\endgroup$
1
  • $\begingroup$ Thanks for the pointers, but this does not provide a polynomial time algorithm for the problem. $\endgroup$
    – Norouzi
    Sep 15, 2016 at 17:01
0
$\begingroup$

I'll assume you are using an edit distance that can be computed in polynomial time and that the reverse of an edit is also an edit. Also, for any string there are only a polynomial number of possible edits. Then, reverse search will take time that is polynomial in the number of output strings, even if $k$ is an increasing function of $n$.

Define an order (say, lexicographic order) on the edits that can be made to a string. Call this with argument $s$:

procedure search(string t) Output $t$; if dist$(t,s) < k$ then for each string $u$ obtained by applying one edit to $t$ do if dist$(u,s)$=dist$(t,s)+1$ and $t$ is the result of applying the lexicographically least edit to $u$ then search($u$) endif endfor endif endprocedure

$\endgroup$
1
  • $\begingroup$ Number of strings at a distance of $k$ can be larger than $(m-1)^k$, when you substitute $k$ tokens, so it is not polynomial in $k$ and $m$. $\endgroup$
    – Norouzi
    Oct 28, 2016 at 5:06

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.