Code with correction of deletions and insertions

code for correction of deletions and insertions

A code intended for the correction of errors of two types encountered in the transmission of information. By a deletion of a letter in a word $ \beta = b _ {1} \dots b _ {n} $ of length $ n $ over some alphabet $ B $ one means a transformation of $ \beta $ into a word $ \beta ^ \prime = b _ {1} \dots b _ {i-1} b _ {i+1} \dots b _ {n} $ of length $ n - 1 $, $ 1 \leq i \leq n $. The numbers $ N _ {s} ( \beta ) $ of words obtainable from $ \beta $ by deletion of $ s $ letters satisfies the following estimates

$$ \left ( \begin{array}{c} \tau ( \beta ) - s + 1 \\ s \end{array} \right ) \ \leq \ N _ {s} ( \beta ) \ \leq \ \left ( \begin{array}{c} \tau ( \beta ) + s - 1 \\ s \end{array} \right ) . $$

Here $ \tau ( \beta ) $ is the number of series of $ \beta $( by a series of a word $ \beta = b _ {1} \dots b _ {n} $ one means a word $ b _ {i+1} \dots b _ {j} $, $ j \geq i + 1 $, such that 1) $ b _ {i+1} = \dots = b _ {j} $; 2) if $ i \geq 1 $, then $ b _ {i} \neq b _ {i+1} $; and 3) if $ j < n $, then $ b _ {j+1} \neq b _ {j} $). In particular, $ N _ {1} ( \beta ) = \tau ( \beta ) $. By an insertion of a letter in a word $ \beta = b _ {1} \dots b _ {n} $ one means a transformation of $ \beta $ into a word $ \beta ^ \prime = b _ {1} \dots b _ {i} b b _ {i+1} \dots b _ {n} $ of length $ n + 1 $, where $ b \in B $ and $ 0 \leq i \leq n $. The number of words obtainable from an arbitrary word $ \beta $ of length $ n $ by the insertion of $ s $ letters of an alphabet $ B $ is equal to

$$ \sum _ { j=0 } ^ { s } \left ( \begin{array}{c} n + s \\ j \end{array} \right ) ( r - 1 ) ^ {j} , $$

where $ r $ is the number of letters in $ B $. A set $ K $ of words over the alphabet $ B $ is called a code for correction of $ s $ deletions (insertions, deletions or insertions) if no word in $ B $ can be obtained from two distinct words of $ K $ as the result of $ s $ or fewer deletions (insertions, deletions or insertions) of letters in each of them. The function defined on the pairs $ ( \beta _ {1} ,\ \beta _ {2} ) $ of words in $ B $ and equal to the minimum number of deletions and insertions of letters converting $ \beta _ {1} $ into $ \beta _ {2} $ is a metric. A set $ K $ of words over the alphabet $ B $ is a code for correction of $ s $ deletions (insertions, deletions or insertions) if and only if the distance between any two distinct words of $ K $ is greater than $ 2 s $, so that the above three definitions of a code are equivalent. An example of a code for correction of one deletion or one insertion is the set of words $ \{ \beta = b _ {1} \dots b _ {n} \} $ of length $ n $ over the alphabet $ B = \{ 0 ,\ 1 \} $ for which $ \sum _ {i=1} ^ {n} i b _ {i} \equiv 0 $( $ \mathop{\rm mod} \ n + 1 $). The number of words in this code is equal to

$$ \frac{1}{2 ( n + 1 )} \sum \phi (d) 2 ^ {( n + 1 ) / d} , $$

where the sum is taken over all odd divisors $ d $ of $ n + 1 $ and $ \phi (d) $ is the Euler function; it is asymptotically maximal as $ n \rightarrow \infty $.