Помоему данная тема не поднималась... На мой взгляд достаточно нужная вещь и то что я встречал и использовал не удовлетворяло тем минимальным условиям которые были. К примеру нужно сделать выбор ФИО. Самый простой способ это инкрементальный поиск - но иногда пользователь жмет буквы меняя их местами или просто пропускает одну. В данном случае можно было бы сделать нечеткий поиск по строке...

ЗЫ На этом народ дисеры защищает... Просто интересно кто че пользовал.

Классика(strcmp и std::string::operator=() )
только инкрементальный

ЗЫ
эТО ж кАкие такие условия такие ставили?

Если надо выбрать ФИО, то занчит наверняка это выбирается из БД.
А значит можно использвать запрос с поиском по контексту...

Брр ниче не понял. Естественно выбираем из базы например сотрудников их ФИО в каждое поле. Далее вводим побуквам П е р т о в. (должно быть П е т р о в ) Ессно такой фвмилии нет в списке - выдается пустой выпадающий список. А надо чтобы при пустой выборке шел нечеткий поиск...

Это я так. Нафантазировал.

Воообще вопрос более широкий - именно кто какие нечеткие алгоритмы сравнения использовал. Сами понимаете что например в Яндексе оно как раз и работает только там гораздо все более наворочено вплоть до разбора корней слов и т.д.

Более интересна тема функций.

Например на входе даем 2 строки и она возвращает процент их соответствия.

Функция LIKE %Пет% вернёт из базы все имена в которых содержится такое сочетание. Петров, Ровпет, и т.п. Чем меньше сочетание тем меньше вернётся. Если %Пет то будет искать то что начинается на "Пет", если Пет% то то что кончается.

Короче поиск по контексту... Можно вообще не вводить имя полностью, а ввести часть и потом из возвращённых данных выберут то что им нужно...

Мдеее, первые постеры ЯВНО проблему не поняли А задаче действительно нетривиальная, мне с ней уже пришлось столкнуться... Другое дело, что я ее замучился решать сам, и просто вбил готовый алгоритм из вот этой книги: Dan Gusfield "Algorithms on Strings, Trees and Sequences" (Ден Гасфилд "Строки, деревья и последовательности в алгоритмах"), что и рекомендую сделать автору топа!


И как взять эту подпоследовательность? С начала? С конца? А если именно В НЕЙ юзер сделает ошибку?

Обычно берётся всё вхождение символов, а не сначала и с конца. А сделает ошибку - увидет это сразу и исправится. Это уже проблемы пользователя. Никаких "специальных алгоритмов" в воих программах я использовать не собираюсь Этого вполне достаточно! Сколько ни делали программ - пока юзеры и от этого счастливы, поскольку строка которую нужно наёти обычно имеет длину от 10 до 180 символов. В Последнем случае именно такой подход просто необходим.

Гыгыгыгы, да вы, мин херц, ещё не работали на юзеров, которые бы за такой подход вас на счетчик поставили как за наезд Такой обычно юзер говорит - ну ты че, мужик, это ж так просто! делаешь, как я сказал, а я плачУ! И показывает пресс И после этого программер бежит, нарывает ЛЮБУЮ литературу, все делает и потом как сыр в масле катается

Этого я не отрицаю. Как говорил известный песонаж в известном фильме: "Ну ты же знаешь, когда мне платят я всегда довожу дело до конца"(с). Конечно, если от меня такое затребуют за соответствующую плату... А наши пользователи и этому рады. Наверно просто не делают таких ошибок...

Можно почитать еще про регулярные выражения...

Я тоже надеялся услышать что-то новое... Жаль, идей почти нет

Вопрос посвящался нечёткому поиску- я прав?

В своё время я решал похожую задачу (распознавание кодировки и языка на автомате), но решение было топорное- я строил частоты встреч символов и сравнивал распределения с фонемами словарей.

Данная задача реализована, кстати, в Microsoft Word- не очень хорошо, но всё же..

Очевидно, такое решение можно применить и здесь. Надо сделать так:
*далее идёт чисто дилетантское высказывание - просто идеи.*

Алгоритм 1:
1) Берём словарь всех слов ;-)
2) Ищем слово в словаре (отдельно - склонения и спряжения - не буду отвлекаться, ок? )
3) Если нашли - ищем его корень полным вхождением. Иначе - находим наиболее подходящее и ишем его (способ ниже).
Алгоритм 2:
Просто ищем наиболее подходящее в запросе... Алгоритм тот же и ниже. Этот вариант проще, но более долог (потенциально)..

Алгоритм поиска наиболее подходящего: функция, возвращающая, на сколько похожи слова. Например, нормированная от 0 до 1: 1- полное соотвествие.
Результат функции, как видно, будет определяться как взвешенная сумма соответствий.
Думаю, следует выделить два типа соответствий-
1) Частоты встреч букв и фонем. При этом, чем длинее фонема, тем вес больше; чем реже буква встречается в языке- тем вес больше.
2) Их взаимное расположение -анализируем список встреченных совпадающих фонем и добавляем их коэфициенты, с учётом того, что вес фонемы больше.

Пример.
Слова "АББРЕВИАТУРА" и "АБРАКАДАБРА"
1) Программа собирает таблицу частот встреч всех букв в первом и втором словах. Очевидно, что не встреченные буквы получают частоту 0
блин... как тут таблицы рисовать...
Так... Короче, первая цифра- в первом слове, вторая- во втором, третья- частота встречи в русском языке данной буквы (нормированная) (коэфициенты от балды... лень искать их)
A:3:5:0.1
Б:2:2:0.08
В:1:0:0.05
Г:0:0:0.06 (не заносим её)
Д:0:1:0.009
.......
Затем двухбуквенные последовательности:
АБ:1:2:0.005
ББ:1:0:0.0001
....
Торёхбуквенные:
....
Далее. Вычисляем общий коэфициент соответствия частоты встреч. Это будет взвешенная сумма чисел, зависящих от количества совпадений с учётом частоты встреч фонемы в языке (то есть, для редкой фонемы при совпадении вес будет больший. Например, буква "Ц", встреченная и там, и там, намного более значима, чем буква "А", встреченная и там и там, пусть даже и в равных больших количествах

Далее: Для всех найденных фонем сравниваем их относительное положение в слове и так же взвешенно складываем. Естественно, считаем не по позициям, а по долям слова...

Вот. Потом перемножаем эти два коэфициента и получаем результат.

Конец идеи.
Плюсы: Явно довольно чёткий поиск соответсвия.
Минусы: есть подозрение, что это будет не просло лагать, а ЛАГАТЬ... Возможно, стоит оптимизировать это как-то, или убрать один из этапов. Несомненно, сильно влияет на производительность максимальная длина фонемы...

Нечёткая логика рулит.
Фух....

Первый пункт меня порадовал Третий тоже ни хрена се: а что, если это не слова вовсе, а список названий фирм, причем сделанный СКАНЕРОМ? Т.е. там и сям могут быть неправильные буквы, а то и вовсе одна буква вместо двух, и наоборот! А у названий поди определи, где там корень...

Я, собственно, второй способ и реализовал, что всем и рекомендую!

2NT_Denis
Гениально !
1) А ты представляеш сколько этот словарь будет весить ?
Я открою тебе тайну он будет весить порядка >6TB чистого текста с словами от 3х до где то 20 символов латиницей
2) См. 1 пункт и думай сколько будет длится поиск
3) Если через пару месяцев - нашли .... то это уже прогресс

Упс! Я имел в виду не второй способ, а последний - тот, что без номера


Это ты зря, кстати все зависит от конкретной задачи - не стоит умирать раньше времени! Моя прога была рекомендована заказчику к запуску еженедельно - и в пределах накладных, полученных за неделю, она не так уж и зашивалась: ну, часа три от силы на нахождение и раскидывание ВСЕХ названий компаний в списке

ComboBox рулит.
Если из БД выбока, то выбираю все фамилии из списка (у меня их ~4000), добавляю в Combobox. При вводе фио, курсор динамически перемещается на ближайщую найденную фамилию.

И что? Читаем внимательно - если пользователь УЖЕ ввел буквы которых нет в списке... Например поменял местами.

как то все сложно..
а может проще, с помощью Excel?
в ячейке А1 находится искомое значение, в таблице (Таблица1) находится перечень значений и соответствие им.
ставив в ячейке, куда надо поставить соответствие следующую формулу
=ВПР(А1;Таблица1;2;ложь)

вот и все