Перейти к содержимому


- - - - -

Сравнение строк


  • Авторизуйтесь для ответа в теме
Сообщений в теме: 16

#1 jellfish

jellfish

    Свой человек

  • Members
  • PipPipPipPipPipPip
  • 786 сообщений
  • Пол:Мужчина
  • Город:ССХ
  • Интересы:Программист СУБД

Отправлено 31 Май 2006 - 10:02

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

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

#2 flexcreator

flexcreator

    Хранитель форума

  • Members
  • PipPipPipPipPipPipPipPip
  • 1 920 сообщений
  • Пол:Мужчина
  • Город:ВОКЗАЛ )
  • Интересы:GAMES( Oni, TES, Max Payne, Half-Life )<br />CODE( asm, c/c++, c#, hlsl, misc )<br />ЛЮБИМЫЕ CODE-АВТОРЫ( Макконнел, Кнут, Ламот, Мейерс )<br />ЛЮБИМЫЕ CODE-UTILS( MSVS, Intel C++/VTune, Perforce )<br />любимые авторы: Стивен Кинг, Брэдбери, Джон Гришем<br />музыка: Sepultura, Slipknot, Fear Factory, BROKEN HOPE, Clawfinger, Pantera, Hatebreed, Cannibal Corpse и т.д.<br />фильмы: Зеленая Миля, Форест Гамп

Отправлено 31 Май 2006 - 14:16

Просмотр сообщенияjellfish (31.05.2006, 11:02) писал:

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

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

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

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

#3 Suzeren

Suzeren

    Хранитель форума

  • Members
  • PipPipPipPipPipPipPipPip
  • 3 189 сообщений

Отправлено 31 Май 2006 - 16:51

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

#4 jellfish

jellfish

    Свой человек

  • Members
  • PipPipPipPipPipPip
  • 786 сообщений
  • Пол:Мужчина
  • Город:ССХ
  • Интересы:Программист СУБД

Отправлено 31 Май 2006 - 17:32

Просмотр сообщенияSuzeren (31.05.2006, 17:51) писал:

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


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

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

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

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

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

#5 Suzeren

Suzeren

    Хранитель форума

  • Members
  • PipPipPipPipPipPipPipPip
  • 3 189 сообщений

Отправлено 31 Май 2006 - 17:49

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

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

#6 Gray

Gray

    Хранитель форума

  • Members
  • PipPipPipPipPipPipPipPip
  • 15 125 сообщений
  • Пол:Мужчина
  • Интересы:Kоллекционирование. Собираю статусы. Свои =) Сейчас в коллекции:

    1. 1е место в мире по ПВП в Lost Realms, 2004-2005г (lost-realms.org)
    2. 1е место на турнире Химкинского района по HoMM3, 2006г
    3. 2е место на всероссийском турнире по ПKМ:ВМЛ, 2005г (legend.seaward.ru)
    4. 8е место в мире по ПВП в MUME, 2003г (mume.org)

    И как бонус - позиция самого активного юзера этого форума ;)

Отправлено 31 Май 2006 - 21:34

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

Просмотр сообщенияSuzeren (31.05.2006, 18:49) писал:

Функция LIKE %Пет% вернёт из базы все имена в которых содержится такое сочетание. Петров, Ровпет, и т.п. Чем меньше сочетание тем меньше вернётся. Если %Пет то будет искать то что начинается на "Пет", если Пет% то то что кончается.
И как взять эту подпоследовательность? С начала? С конца? А если именно В НЕЙ юзер сделает ошибку? B)

#7 Suzeren

Suzeren

    Хранитель форума

  • Members
  • PipPipPipPipPipPipPipPip
  • 3 189 сообщений

Отправлено 31 Май 2006 - 22:48

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

Сообщение отредактировал Suzeren: 31 Май 2006 - 22:49


#8 Gray

Gray

    Хранитель форума

  • Members
  • PipPipPipPipPipPipPipPip
  • 15 125 сообщений
  • Пол:Мужчина
  • Интересы:Kоллекционирование. Собираю статусы. Свои =) Сейчас в коллекции:

    1. 1е место в мире по ПВП в Lost Realms, 2004-2005г (lost-realms.org)
    2. 1е место на турнире Химкинского района по HoMM3, 2006г
    3. 2е место на всероссийском турнире по ПKМ:ВМЛ, 2005г (legend.seaward.ru)
    4. 8е место в мире по ПВП в MUME, 2003г (mume.org)

    И как бонус - позиция самого активного юзера этого форума ;)

Отправлено 31 Май 2006 - 23:50

Просмотр сообщенияSuzeren (31.05.2006, 23:48) писал:

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

#9 Suzeren

Suzeren

    Хранитель форума

  • Members
  • PipPipPipPipPipPipPipPip
  • 3 189 сообщений

Отправлено 31 Май 2006 - 23:58

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

Сообщение отредактировал Suzeren: 01 Июнь 2006 - 00:03


#10 SerrNovik

SerrNovik

    Завсегдатай

  • Members
  • PipPipPipPipPip
  • 593 сообщений

Отправлено 01 Июнь 2006 - 06:37

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

#11 NT_Denis

NT_Denis

    Новичок

  • Members
  • Pip
  • 15 сообщений

Отправлено 01 Июнь 2006 - 12:57

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

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

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

Данная задача реализована, кстати, в 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
....
Торёхбуквенные:
....
Далее. Вычисляем общий коэфициент соответствия частоты встреч. Это будет взвешенная сумма чисел, зависящих от количества совпадений с учётом частоты встреч фонемы в языке (то есть, для редкой фонемы при совпадении вес будет больший. Например, буква "Ц", встреченная и там, и там, намного более значима, чем буква "А", встреченная и там и там, пусть даже и в равных больших количествах

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

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

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

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

#12 Gray

Gray

    Хранитель форума

  • Members
  • PipPipPipPipPipPipPipPip
  • 15 125 сообщений
  • Пол:Мужчина
  • Интересы:Kоллекционирование. Собираю статусы. Свои =) Сейчас в коллекции:

    1. 1е место в мире по ПВП в Lost Realms, 2004-2005г (lost-realms.org)
    2. 1е место на турнире Химкинского района по HoMM3, 2006г
    3. 2е место на всероссийском турнире по ПKМ:ВМЛ, 2005г (legend.seaward.ru)
    4. 8е место в мире по ПВП в MUME, 2003г (mume.org)

    И как бонус - позиция самого активного юзера этого форума ;)

Отправлено 04 Июнь 2006 - 01:15

Просмотр сообщенияNT_Denis (1.06.2006, 13:57) писал:

Алгоритм 1:
1) Берём словарь всех слов ;-)
2) Ищем слово в словаре (отдельно - склонения и спряжения - не буду отвлекаться, ок? )
3) Если нашли - ищем его корень полным вхождением. Иначе - находим наиболее подходящее и ишем его (способ ниже).
Первый пункт меня порадовал :P  B)  :lol: Третий тоже ни хрена се: а что, если это не слова вовсе, а список названий фирм, причем сделанный СКАНЕРОМ? Т.е. там и сям могут быть неправильные буквы, а то и вовсе одна буква вместо двух, и наоборот! А у названий поди определи, где там корень...

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

#13 echo

echo

    Втянувшийся

  • Members
  • PipPipPip
  • 253 сообщений

Отправлено 04 Июнь 2006 - 02:12

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

Сообщение отредактировал echo: 04 Июнь 2006 - 02:13


#14 Gray

Gray

    Хранитель форума

  • Members
  • PipPipPipPipPipPipPipPip
  • 15 125 сообщений
  • Пол:Мужчина
  • Интересы:Kоллекционирование. Собираю статусы. Свои =) Сейчас в коллекции:

    1. 1е место в мире по ПВП в Lost Realms, 2004-2005г (lost-realms.org)
    2. 1е место на турнире Химкинского района по HoMM3, 2006г
    3. 2е место на всероссийском турнире по ПKМ:ВМЛ, 2005г (legend.seaward.ru)
    4. 8е место в мире по ПВП в MUME, 2003г (mume.org)

    И как бонус - позиция самого активного юзера этого форума ;)

Отправлено 04 Июнь 2006 - 02:28

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

Просмотр сообщенияecho (4.06.2006, 03:12) писал:

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

#15 alexeyban

alexeyban

    Новичок

  • Members
  • Pip
  • 10 сообщений

Отправлено 14 Июнь 2006 - 05:05

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

#16 jellfish

jellfish

    Свой человек

  • Members
  • PipPipPipPipPipPip
  • 786 сообщений
  • Пол:Мужчина
  • Город:ССХ
  • Интересы:Программист СУБД

Отправлено 14 Июнь 2006 - 08:42

Просмотр сообщенияalexeyban (14.06.2006, 06:05) писал:

<_< ComboBox рулит.
Если из БД выбока, то выбираю все фамилии из списка (у меня их ~4000), добавляю в Combobox. При вводе фио, курсор динамически перемещается на ближайщую найденную фамилию.
И что?  :lol2:  Читаем внимательно - если пользователь УЖЕ ввел буквы которых нет в списке... Например поменял местами.  ;)

#17 RoMaN

RoMaN

    Хранитель форума

  • Members
  • PipPipPipPipPipPipPipPip
  • 2 776 сообщений
  • Пол:Мужчина

Отправлено 07 Март 2010 - 01:22

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

вот и все :D




Количество пользователей, читающих эту тему: 1

0 пользователей, 1 гостей, 0 анонимных