|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
О сложности преобразования пар слов относительно операций выпадения-вставки специального видастатья
- Авторы: Дергач П.С., Амирова С.Р.
- Журнал: Интеллектуальные системы. Теория и приложения (ранее: Интеллектуальные системы по 2014, № 2, ISSN 2075-9460)
- Том: 27
- Номер: 3
- Год издания: 2023
- Издательство: [б.и.]
- Местоположение издательства: М.
- Первая страница: 122
- Последняя страница: 136
- Аннотация: Данная статья посвящена поиску расстояния между парамислов в общем конечном алфавите под действием операции замены одной буквы в две (соседние) и вычислению соответствующейкратчайшей цепочки замен (в случае ее существования). Изначально задача ставилась в более общей формулировке для пары регулярных языков, но позднее постановка задачи была уточнена. Приэтом рассмотрены две возможности - с разрешением замены ранееотсутствовавших в исходном слове букв или с запретом таких операций. Данное направление актуально и может быть использовано,например, в теории помехоустойчивого кодирования. В частности,стоит упомянуть метрику Левенштейна, вдохновляющую на аналогичные исследования относительно нового вида операций буквенной замены.Ключевые слова: распознавание текстов, расстояние Левенштейна, метрика, оптимальный алгоритм.
- Добавил в систему: Дергач Пётр Сергеевич