Finding a set with the maximum number of finite alphabet strings within a fixed Levenshtein distance of one-another

2010-06-15T02:31:05Z

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} $$

Finding a set with the maximum number of finite alphabet strings within a fixed Levenshtein distance of one-another - MathOverflow

Finding a set with the maximum number of finite alphabet strings within a fixed Levenshtein distance of one-another