EN
О сложности преобразования пар слов относительно операций выпадения-вставки специального вида
Опубликована: 2023 год, том 27, выпуск 3, С. 122–136
Аннотация
Данная статья посвящена поиску расстояния между парами слов в общем конечном алфавите под действием операции замены одной буквы в две (соседние) и вычислению соответствующей кратчайшей цепочки замен (в случае ее существования). Изначально задача ставилась в более общей формулировке для пары регулярных языков, но позднее постановка задачи была уточнена. При этом рассмотрены две возможности - с разрешением замены ранее отсутствовавших в исходном слове букв или с запретом таких операций. Данное направление актуально и может быть использовано, например, в теории помехоустойчивого кодирования. В частности, стоит упомянуть метрику Левенштейна, вдохновляющую на аналогичные исследования относительно нового вида операций буквенной замены.
Ключевые слова: распознавание текстов, расстояние Левенштейна, метрика, оптимальный алгоритм.
BibTeX
@article{IS-Dergach-Amirova2023,
author = {Дергач, Пётр Сергеевич and Амирова, Сабина Ровшан гызы},
title = {{О сложности преобразования пар слов относительно операций выпадения-вставки специального вида}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2023},
volume = {27},
number = {3},
pages = {122--136},
}
AMSBIB
\RBibitem{IS-Dergach-Amirova2023}
\by П.\,С.~Дергач, С.\,Р.\,г.~Амирова
\paper О сложности преобразования пар слов относительно операций выпадения-вставки специального вида
\jour Интеллектуальные системы. Теория и приложения
\yr 2023
\vol 27
\issue 3
\pages 122--136