9
$\begingroup$

Please consider the set of all possible strings of some finite size $M$ alphabet $\Sigma$, $\alpha$ $= a_1, a_2, ..., a_k, ..., a_n$, of length $|\alpha| = L$. The Levenshtein distance (or 'edit distance') between any two strings, $D(a_{k1},a_{k2})$ = $p$, can be defined as the number of single-character insertions, deletions, or substitutions necessarily to transform one string, $a_{k1}$, into another, $a_{k2}$. We are forbidding the transposition operation, giving the $L = 3$ example: $D("abc", "cba")$ = $2$.

Let $(s_{p1}, s_{p2}, ..., s_{pk}, ..., s_{pm}) \in S_p$, be a particular set that has the largest possible number of strings over the finite alphabet within a fixed Levenshtein distance, $p$, of one-another. Can we find a particular instance of $S_p$, or perhaps more easily $||S_p||$, for an arbitrarily sized alphabet, $\Sigma$, and an arbitrary string length, $L$?

Perhaps this is more of a definition, but we know (trivially) that $||S_0|| = 1$. It seems to be true that $||S_1||$ increases in a linear way with $L$ and $M$. But there doesn't appear to be a nice growth relationship for $||S_p||$ as a function of $M$ and $L$ if $p > 1$.

Update - For the provided data, $||S_2||$ appears to have a closed-form solution of $4*(L-1)^2$ for a three-character alphabet, and a closed-form solution of $\frac{3}{2}(5*(L-1)^2+(L-1))$ for a four-character alphabet.

Update - Does anyone know if this problem is in class NP, similar to the complexity of generating many types of error-correcting codes? I was hoping the case here would be different, as we're asking for less information...


A computer search yields:

For $L = 1$: $$\eqalign {&(||S_0||,||S_1||)=\cr &\qquad (1, 1) \sim M = 2 \cr &\qquad (1, 2) \sim M = 3\cr &\qquad (1, 3) \sim M = 4\cr} $$

For $L = 2$: $$\eqalign {&(||S_0||,||S_1||,||S_2||)=\cr &\qquad (1, 2, 1) \sim M = 2\cr &\qquad (1, 4, 4) \sim M = 3\cr &\qquad (1, 6, 9) \sim M = 4\cr} $$

For $L = 3$: $$\eqalign {&(||S_0||,||S_1||,||S_2||,||S_3||)=\cr &\qquad (1, 3, 4, 1) \sim M = 2\cr &\qquad (1, 6, 16, 8) \sim M = 3\cr &\qquad (1, 9, 33, 27) \sim M = 4\cr} $$

For $L = 4$: $$\eqalign {&(||S_0||,||S_1||,||S_2||,||S_3||,||S_4||)=\cr &\qquad (1, 4, 9, 4, 1) \sim M = 2\cr &\qquad (1, 8, 36, 35, 16) \sim M = 3\cr &\qquad (1, 12, 72, 130, 81) \sim M = 4\cr} $$

For $L = 5$: $$\eqalign {&(||S_0||,||S_1||,||S_2||,||S_3||,||S_4||,||S_5||)=\cr &\qquad (1, 5, 16, 11, 5, 1) \sim M = 2\cr &\qquad (1, 10, 64, 124, 80, 32) \sim M = 3\cr &\qquad (1, 15, 126, 410, 438, 243) \sim M = 4\cr} $$

For $L = 6$: $$\eqalign {&(||S_0||,||S_1||,||S_2||,||S_3||,||S_4||,||S_5||,||S_6||)=\cr &\qquad (1, 6, 27, 28, 15, 6, 1) \sim M = 2\cr &\qquad (1, 12, 100, 306, 302, 192, 64) \sim M = 3\cr &\qquad (1, 18, 195, 942, 1938, 1458, 729) \sim M = 4\cr} $$

For $L = 7$: $$\eqalign {&(||S_0||,||S_1||,||S_2||,||S_3||,||S_4||,||S_5||,||S_6||,||S_7||)=\cr &\qquad (1, 7, 40, 60, 39, 21, 7, 1) \sim M = 2\cr &\qquad (1, 14, 144, 612, 1030, 712, 448, 128) \sim M = 3\cr &\qquad (1, 21, 279, 1807, 5803, 6966, 5103, 2187) \sim M = 4\cr} $$

For $L = 8$: $$\eqalign {&(||S_0||,||S_1||,||S_2||,||S_3||,||S_4||,||S_5||,||S_6||,||S_7||,||S_8||)=\cr &\qquad (1, 8, 56, 113, 97, 56, 28, 8, 1) \sim M = 2\cr &\qquad (1, 16, 196, 1074, 2716, 2575, 1792, 1024, 256) \sim M = 3\cr &\qquad (1, 24, 378, 3086, 13716, 28310, 23414, 17496, 6561) \sim M = 4\cr} $$

For $L = 9$: $$\eqalign {&(||S_0||,||S_1||,||S_2||,||S_3||,||S_4||,||S_5||,||S_6||,||S_7||,||S_8||)=\cr &\qquad (1, 9, 74, 194, 216, 135, 84, 36, 9, 1) \sim M = 2\cr &\qquad (1, 18, 256, 1724, 5956, 8315, 6309, 4608, 2304, 512) \sim M = 3 \cr} $$

For $L = 10$: $$\eqalign {&(||S_0||,||S_1||,||S_2||,||S_3||,||S_4||,||S_5||,||S_6||,||S_7||,||S_8||)=\cr &\qquad (1, 10, 95, 311, 448, 321, 210, 120, 45, 10, 1) \sim M = 2\cr} $$

$\endgroup$
  • 1
    $\begingroup$ Let G_n be the graph with vertices any string of length at most n (fixing some alphabet) and edges between strings with L-dist 1. Let G be the similar graph, but with no length restriction. Given a distance D, D neighborhoods in G_n are strictly smaller than D neighborhoods in G, so your search _for D neighborhoods in G_n should take place in some larger fragment (G_(n+D) should suffice) of G. It might make sense to study automorphisms of G and G_n and consider doing your enumeration after such a study. Gerhard "Ask Me About System Design" Paseman, 2010.06.14 $\endgroup$ – Gerhard Paseman Jun 15 '10 at 2:58
  • $\begingroup$ Gerhard, I had a feeling this this problem might have been tackled in some form, somewhere in the literature... But about looking for awhile, I thought I might be able to a hit from the community here. $\endgroup$ – Rob Grey Jun 15 '10 at 3:18
  • $\begingroup$ I suggest the automorphisms because that is how I believe it should be tackled. You could try Polya enumeration, but I do not know if it has already been done for this problem. Of course, check Sloane's encyclopedia. Gerhard "Ask Me About System Design" Paseman, 2010.06.14 $\endgroup$ – Gerhard Paseman Jun 15 '10 at 4:26
  • $\begingroup$ Sloane's was the first thing I checked once I had some values, and I couldn't find anything. :-( $\endgroup$ – Rob Grey Jun 15 '10 at 4:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.