Часть 3. Математические модели

О сложности преобразования пар слов относительно операций выпадения-вставки специального вида

П. С. Дергач^a, С. Р. Амирова<sup>b

a</sup> Московский государственный университет имени М. В. Ломоносова, механико-математический факультет
^b Филиал Московского государственного университета им. М.В. Ломоносова в г. Баку

Аннотация: Данная статья посвящена поиску расстояния между парами слов в общем конечном алфавите под действием операции замены одной буквы в две (соседние) и вычислению соответствующей кратчайшей цепочки замен (в случае ее существования). Изначально задача ставилась в более общей формулировке для пары регулярных языков, но позднее постановка задачи была уточнена. При этом рассмотрены две возможности - с разрешением замены ранее отсутствовавших в исходном слове букв или с запретом таких операций. Данное направление актуально и может быть использовано, например, в теории помехоустойчивого кодирования. В частности, стоит упомянуть метрику Левенштейна, вдохновляющую на аналогичные исследования относительно нового вида операций буквенной замены.

Ключевые слова: распознавание текстов, расстояние Левенштейна, метрика, оптимальный алгоритм.