Здравствуйте, punches, Вы писали:
P>Здравствуйте!
P>Есть две строки и надо узнать: похожи они или нет с некоторой точностью. Нужно для того, чтобы определить, что слово хоть и с опечаткой, но нужно нам.
Можно так:
введем функцию расстояния между 2мя строками — минимальное количество элементарных действий, которые нужно произвести над строкой 1 для получения строки 2.
Как правило, элементарными действиями считают: удаление символа, вставка символа, изменение символа, перестановка двух соседних символов.
Иногда последнее действие исключают. Также можно действиям назначать меру значимости — вес.
После этого задача решается методом динамического программирования.
Когда найдено расстояние между строками, функцию похожести можно вычислить так: f = 1 — distance(a, b)/max(strlen(a), strlen(b)).
Есть еще одна реализация в виде исходника, встретил как-то в фидо лет 7 назад. К сожалению, подходящего официального алгоритма для нее найти не удалось.
