Здравствуйте!

Есть две строки и надо узнать: похожи они или нет с некоторой точностью. Нужно для того, чтобы определить, что слово хоть и с опечаткой, но нужно нам.

fuzzy search ?

Здравствуйте, punches, Вы писали:

P>Есть две строки и надо узнать: похожи они или нет с некоторой точностью. Нужно для того, чтобы определить, что слово хоть и с опечаткой, но нужно нам.

Обсуждалось уже. Поищите по волшебным словам Metaphone и SoundEx

Здравствуйте, punches, Вы писали:

P>Здравствуйте!

P>Есть две строки и надо узнать: похожи они или нет с некоторой точностью. Нужно для того, чтобы определить, что слово хоть и с опечаткой, но нужно нам.

Пишу я здесь редко, но сейчас попробую вставить 5 копеек. Есть такая вещь — выравнивание последовательностей, используется для сравнения частей ДНК, например, но, безусловно, этим не ограничивается.

Почитать можно здесь

Не так давно лично сталкивался с подобной задачкой ( http://webcourse.cs.technion.ac.il/236703/Spring2004/hw/WCFiles/ex4.v1.02.html )
Есть мой вариант решения ( C++, template-based ).
Если интересно, могу прислать.

Здравствуйте, punches, Вы писали:

P>Здравствуйте!

P>Есть две строки и надо узнать: похожи они или нет с некоторой точностью. Нужно для того, чтобы определить, что слово хоть и с опечаткой, но нужно нам.

посмотри здесь

Автор: c-smile
Дата: 25.09.04

метод neighbour_search
может поможет

Здравствуйте, punches, Вы писали:

P>Здравствуйте!

P>Есть две строки и надо узнать: похожи они или нет с некоторой точностью. Нужно для того, чтобы определить, что слово хоть и с опечаткой, но нужно нам.

Ternary search tree, думаю, решит вашу проблему. В исходниках посмотрите или в гугле. Только из личного опыта могу сказать, что этого недостаточно на проверку очепяток (сам сейчас этим вопросом занимаюсь). Нужно с каким-то образцом сравнивать, верно? А где образец взять?

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

Скажем такая задача: есть БД с Ф И О и есть некий случайный текст — нужно выявить присутсвие людей из базы в тексте, невзирая на падеж — тут вышеизложенное — надежная метода сравнения строк.

---

данное сообщение получено с www.gotdotnet.ru
ссылка на оригинальное сообщение

Здравствуйте, Fagim, Вы писали:

F>Как самый грубый вариант — убрать из строки гласные и сравнивать. Очень во многих задачах оказывается, что этот немудрящий вариант с небольшими изменениями (скажем пополнить список Й и Ь, сравнение длины, сберегание первой буквы и т.п.) дает вполне корректный результат.

F>Скажем такая задача: есть БД с Ф И О и есть некий случайный текст — нужно выявить присутсвие людей из базы в тексте, невзирая на падеж — тут вышеизложенное — надежная метода сравнения строк.

Да, но для поиска по словарю, думаю, это не совсем то.
Пример: vanish, vanished, vanishing... Префиксы, суффиксы — вот проблема, т.к. хранить все комбинации, получаемые при добавлении к корню слова
приставок и суффиксов нереально.

Мне, к счастью, не нажо проверять орфографию . Задача ограничивается сравнением с существующей базой имен клиентов компании.

Всем спасибо за советы!

Я, кажется, нашел подходящий способ решения: буду использовать алгоритм Левентшейна.

Здравствуйте, punches, Вы писали:

P>Я, кажется, нашел подходящий способ решения: буду использовать алгоритм Левентшейна.
Левенштейн, вроде, только метрику придумал... Причём она является частным случаем того, что привёл я.

Здравствуйте, punches, Вы писали:

P>Здравствуйте!

P>Есть две строки и надо узнать: похожи они или нет с некоторой точностью. Нужно для того, чтобы определить, что слово хоть и с опечаткой, но нужно нам.

Можно так:

введем функцию расстояния между 2мя строками — минимальное количество элементарных действий, которые нужно произвести над строкой 1 для получения строки 2.

Как правило, элементарными действиями считают: удаление символа, вставка символа, изменение символа, перестановка двух соседних символов.

Иногда последнее действие исключают. Также можно действиям назначать меру значимости — вес.

После этого задача решается методом динамического программирования.


Когда найдено расстояние между строками, функцию похожести можно вычислить так: f = 1 — distance(a, b)/max(strlen(a), strlen(b)).


Есть еще одна реализация в виде исходника, встретил как-то в фидо лет 7 назад. К сожалению, подходящего официального алгоритма для нее найти не удалось.

Если интересуют исходники, могу выслать.

Здравствуйте, xtile, Вы писали:

X>Здравствуйте, punches, Вы писали:

P>>Здравствуйте!

P>>Есть две строки и надо узнать: похожи они или нет с некоторой точностью. Нужно для того, чтобы определить, что слово хоть и с опечаткой, но нужно нам.

X>Можно так:

X>введем функцию расстояния между 2мя строками — минимальное количество элементарных действий, которые нужно произвести над строкой 1 для получения строки 2.

X>Как правило, элементарными действиями считают: удаление символа, вставка символа, изменение символа, перестановка двух соседних символов.

На сколько я понимаю, алгоритм Левенштейна что-то такое и делает.

X>Когда найдено расстояние между строками, функцию похожести можно вычислить так: f = 1 — distance(a, b)/max(strlen(a), strlen(b)).

Спасибо за формулу

F>>Скажем такая задача: есть БД с Ф И О и есть некий случайный текст — нужно выявить присутсвие людей из базы в тексте, невзирая на падеж — тут вышеизложенное — надежная метода сравнения строк.

DG>Да, но для поиска по словарю, думаю, это не совсем то.
DG>Пример: vanish, vanished, vanishing... Префиксы, суффиксы — вот проблема, т.к. хранить все комбинации, получаемые при добавлении к корню слова
DG>приставок и суффиксов нереально.


Здесь нечетким поиском и неточным сравнением не обойтись, нужны морфологические энжины.

Здравствуйте, xtile, Вы писали:

F>>>Скажем такая задача: есть БД с Ф И О и есть некий случайный текст — нужно выявить присутсвие людей из базы в тексте, невзирая на падеж — тут вышеизложенное — надежная метода сравнения строк.

DG>>Да, но для поиска по словарю, думаю, это не совсем то.
DG>>Пример: vanish, vanished, vanishing... Префиксы, суффиксы — вот проблема, т.к. хранить все комбинации, получаемые при добавлении к корню слова
DG>>приставок и суффиксов нереально.


X>Здесь нечетким поиском и неточным сравнением не обойтись, нужны морфологические энжины.

Угу...В частности можно заюзать вот это

Здравствуйте, fAX, Вы писали:

fAX>Если интересно, могу прислать.

Дико интересно. Пришли пожалуйста. Он до ума доведен? Если да, то какая лицензия и все такое... Спасибо.

Здравствуйте, Kaa, Вы писали:

Kaa>Дико интересно. Пришли пожалуйста. Он до ума доведен? Если да, то какая лицензия и все такое... Спасибо.
Доведён. По крайней мере, получил за функциональность полный балл
Нет проблем. Только я не вижу, как их выложить на этом сайте

Здравствуйте, Kaa, Вы писали:

fAX>>Если интересно, могу прислать.
Kaa>Дико интересно. Пришли пожалуйста. Он до ума доведен? Если да, то какая лицензия и все такое... Спасибо.
Я отправил на почту. Лизензия — GPL. Если понравится — можете выложить на этом сайте; я не нашёл как (наверняка, плохо искал).