Определение степени сходства строк с помощью ChatGPT

Одним из широко известных методов, позволяющих определить сходство строк, в информатике является вычисление редакционного расстояния.

Расстояние Левенштейна (редакционное расстояние, дистанция редактирования) — метрика, измеряющая по модулю разность между двумя последовательностями символов. Она определяется как минимальное количество односимвольных операций (а именно вставки, удаления, замены), необходимых для превращения одной последовательности символов в другую. В общем случае, операциям, используемым в этом преобразовании, можно назначить различные цены.

Одним из самых популярных вариантов применения расстояния Левенштейна является исправление ошибки в слове или во фразе. Алгоритм позволяет найти ближайшее словарное слово, и предложить замену неверного слова, что становится крайне важным в поисковых системах, при вводе текста в различных редакторах и базах данных (в частности, геоинформационной системе GIS-Lab), при проверке правописания, при автоматическом распознавании отсканированного текста или речи и в других сферах.

Этот же алгоритм позволяет сравнить между собой файлы, измерять количество ошибок при передаче информации, если допускается возможность утери или вставки битов в файлы.

Отдельно можно упомянуть такую прикладную задачу, как поиск фишинговых доменных имен. Как правило, фишинговые доменные имена несущественно отличаются от доменных имен известных компаний. Фишинговые доменные имена могут содержать бренды таких организаций с опечатками, на которые среднестатистический пользователь сети Интернет может не обратить внимание. В частности, такой алгоритм реализован в программном комплексе для анализа фейковой активности (ООО «Арборсофт»).

Кроме того, к брендам могут добавляться слева или справа различные цифры, слова «order», «personal», «account», «payment», «promo» и др. Конкретный набор таких слов зависит от предметной области атакуемого бренда. Для обнаружения таких доменных имен используют не алгоритм определения сходства строк, а алгоритм поиска подстроки, имеющей не более K несовпадений с искомой строкой (алгоритм Ландау-Вишкина).

Если к списку разрешённых операций добавить транспозицию (два соседних символа меняются местами), получается расстояние Дамерау — Левенштейна. Оно довольно часто используется в биоинформатике.

Уже существует множество сервисов, позволяющих вычислить и тот, и другой вариант редакционного расстояния. Но почему бы не проверить – способен ли ChatGPT на подобные вычисления? Это не геометрическая задача, не решение ЕГЭ по математике, где нет однозначного и гарантированного подхода к решению. Вычисление расстояния Левенштейна – это строго алгоритмическая задача, то есть сводящаяся к определенную набору действий всегда приводящим к верному результату.

При проверке были использованы следующие варианты запросов:

1) Найди расстояние Левенштейна между словами "X" и "Y". Напиши только ответ.

2) Найди расстояние Левенштейна между словами "X" и "Y"

1) Найди расстояние Левенштейна между словами "кусок" и "колбаса"

Правильный ответ: 6.

Посмотрим теперь, что предложит ChatGPT.

Уже с первого пункта понятно, что при выполнении операций замены символов что-то пошло не так.

В целом, при различных попытках отправить вопрос про эти два слова, ChatGPT дает ответ от 3 до 5.

Но, может быть, стоит попробовать более простой вариант?

2) Найди расстояние Левенштейна между словами "кусок" и "кусочек"

Здесь фактически нужно только вставить два символа. Правильный ответ: 2.

Можно попытаться спрогнозировать, что ответом искусственного интеллекта будет 3, то есть произойдёт замена "к" на "ч", а потом вставка оставшихся букв. Посмотрим, что же будет происходить в ChatGPT.

Ответ, конечно, не совпадает с правильным, но совпадает с предполагаемым. В то же время путь, который ChatGPT прошёл в этот раз, выглядит еще более странным. По завершению третьего шага бот так и не смог получить требуемое слово, но уже готов выдать ответ.

В ходе экспериментов ChatGPT выдавал ответы от 2 до 4. Иногда он пытался построить таблицу (по-видимому, желая реализовать вариант алгоритма, основанный на построении матрицы), иногда представлял набор необходимых действий по преобразованию слов. Все эти действия выглядели хаотично и иногда даже не приводили к правильному ответу.

Может быть, будет верным результат, когда речь пойдёт только об ответе на запрос? В конце концов, решение арифметических примеров у бота получается ведь.

Увы, здесь тоже в большинстве случаев нас ждет провал.

1) Найди расстояние Левенштейна между словами "машина" и "колонка". Напиши только ответ.

Правильный ответ: 5

Ответ ChatGPT: от 4 до 6.

2) Найди расстояние Левенштейна между словами "камаз" и "масло". Напиши только ответ.

Правильный ответ: 4

Ответ ChatGPT: от 3 до 5

3) Найди расстояние Левенштейна между словами "программа" и "редактор". Напиши только ответ.

Правильный ответ: 8

Ответ ChatGPT: от 7 до 10.

Пока еще ChatGPT не способен к решению подобных алгоритмических задач. Этот факт наглядно показывает, что даже для некоторых рутинных задач использовать чат-бот недопустимо.

Вполне возможно, что дальнейшее развитие сферы искусственного интеллекта позволит отказаться от некоторых профессий, однако до этого момента пока еще достаточно далеко.