Коды с автоматической коррекцией ошибок

[Odnako]

Подскажите, пожалуйста, в какую сторону покопать для решения такой задачи.
Нужно придумать кодировку N десятичных чисел такую, чтобы если при ошибке ввода допущено не более n опечаток и m вставок/удалений, то была возможна автоматическая коррекция. Допустим, нужно закодировать 3 числа, код должен обнаружить и исправить 1 опечатку и 1 вставку/удаление. Тогда возможные варианты кодов будут, например.
Код 1. 0, 111, 122.
Код 2. 11, 22, 33.

[Sonic86]

Коды, в которых можно исправить одну ошибку и обнаружить наличие двух ошибок называются кодами Хэмминга с расстоянием 3 - можете погуглить или в литературе найти. Коды Хэмминга могут быть обобщены и на большее расстояние - в результате получается упаковка шаров радиуса $d$ в $\mathbb{Z}_2^n$. Это Вам немного подходит, только у Вас вместо $\mathbb{Z}_2$ все $\mathbb{Z}$ и расстояние произвольное. А вот насчет вставок или удалений - не знаю.

[Kallikanzarid]

Sonic86 в сообщении #474519 писал(а):

только у Вас вместо $\mathbb{Z}_2$ все $\mathbb{Z}$ и расстояние произвольное.

Тут проблема:
1) $\mathbb{Z}$ - не поле, так что модуль $\mathbb{Z}^n$ будет не очень хороший,
2) В компьютере невозможно хранить произвольные целые числа.

Так что возникает прежде всего вопрос, насколько большие числа нужно хранить.

[Sonic86]

Kallikanzarid в сообщении #474546 писал(а):

1) $\mathbb{Z}$ - не поле, так что модуль $\mathbb{Z}^n$ будет не очень хороший,

А мне не нужно было поле. Мне нужно было множество, кодирующее алфавит счетной мощности.

Kallikanzarid в сообщении #474546 писал(а):

2) В компьютере невозможно хранить произвольные целые числа.

Ну может у ТС конечный алфавит произвольной мощности

[Kallikanzarid]

Sonic86 в сообщении #474614 писал(а):

Мне нужно было множество, кодирующее алфавит счетной мощности.

Шары-то паковать там все равно потом придется

[Sonic86]

Kallikanzarid в сообщении #474624 писал(а):

Sonic86 в сообщении #474614 писал(а):

Мне нужно было множество, кодирующее алфавит счетной мощности.

Шары-то паковать там все равно потом придется

Наверное я зря взял $\mathbb{Z}$ - там и шаров будет бесконечно много. Надо было взять $\mathbb{Z}_n$. Только я все равно не понял, зачем нам именно поле. Мы же просто расстояние считаем. Для этого вполне достаточно аддитивной полугруппы

[Kallikanzarid]

Sonic86 в сообщении #474627 писал(а):

Только я все равно не понял, зачем нам именно поле.

Незачем :)

[PAV]

Сходу нашлось:

А. С. Долгополов, “Недвоичные коды, исправляющие вставки, выпадения и замены символов”, Пробл. передачи информ., 21:1 (1985), 35–39

ссылка (доступен полный текст)

-- Ср авг 10, 2011 10:42:16 --

посмотрите также с этой страницы ссылки на другие статьи, может быть там что-то найдется

ключевые слова - insertion deletion correction codes