Perfect codes in the metric of deletions and insertions

V. I. Levenshtein

Diskretnaya Matematika, Tome 3 (1991) no. 1, pp. 3-20.

Résumé

We consider a problem of packing and covering a metric space $B^n_q$ that consists of $q$-ary words of length $n$ and is provided with a metric of deletions and insertions. For any $n=1,2,\dots $ we present partitions of the space $B^n_2$ and the set of permutations $S_n$ $(S_n\subset B^n_n)$ into perfect codes with correction of individual deletions. In connection with a problem of constructing ordered codes with correction of $s$ deletions we formulate a problem of constructing ordered Steiner systems and give a solution of this problem for certain values of the parameters. We construct codes complete in $B^n_q$ with correction of individual deletions for $n=3$ and any $q$, and also for $n=4$ and any even $q$. We find the asymptotic behavior of the maximum cardinality of the code in $B^n_q$ with correction of individual deletions as $q/n\to\infty$.