Сообщений в теме: 40

[Contagion]

нужно создать поиск слова по полю

к примеру имеем поле в базе данных с названием организации

допустим "ТОО Светлый путь"

кто-то взял да написал не "Светлый" а "Свелтый", просто ошибся при вводе, или пропустил одну буковку "Свелый"

а вот юзер в поиске делает запрос как надо, то есть ищет по слову "Светлый"

как найти слова как нормальные так и с ошибками?

где-то видел такой поиск, кажется на http://www.amadeus.net, при поиске названия аэропортов.

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

далее делаем почти тоже самое, только убираем одну из буковок, и так несколько раз, в зависимости от количества буков в слове по каждой букве.

тока млин это жутко долго!!! и требует ресурсов

может есть другие варианты? не пинайте меня, я самоучка и в политехе не учился

[Shirson]

нужно создать поиск слова по полю
к примеру имеем поле в базе данных с названием организации
допустим "ТОО Светлый путь"
кто-то взял да написал не "Светлый" а "Свелтый", просто ошибся при вводе, или пропустил одну буковку "Свелый"
а вот юзер в поиске делает запрос как надо, то есть ищет по слову "Светлый"
как найти слова как нормальные так и с ошибками?
есть вариант такой, сплитим буковки и начинаем перебор строки, где есть все такие буквы, то есть найдем все названия, где могли перепутать положение букв как в примере "Свелтый".

Время обработки ->oo

далее делаем почти тоже самое, только убираем одну из буковок, и так несколько раз, в зависимости от количества буков в слове по каждой букве.

Время обработки ->oo

И в обоих случаях вываливается куча совпадений, которые совпадениями не являются.

тока млин это жутко долго!!! и требует ресурсов

Точно.

может есть другие варианты? не пинайте меня, я самоучка и в политехе не учился

В MSSQL есть оператор DIFFERENCE, который определяет уровень созвучности слов на основе SOUNDEX.
Приемлемо работает, к сожалению, только с ангийским.
Народ писал подобное для русских слов, но варианты тоже были не самыми лучшими. Поищи на http://www.sql.ru/

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

Сообщение отредактировал Shirson: 23.09.2004, 14:06:06

[Visual1]

нужно создать поиск слова по полю

к примеру имеем поле в базе данных с названием организации
допустим "ТОО Светлый путь"

кто-то взял да написал не "Светлый" а "Свелтый", просто ошибся при вводе, или пропустил одну буковку "Свелый"

а вот юзер в поиске делает запрос как надо, то есть ищет по слову "Светлый"

Если программа ищет в поле БД точное соответствие пользовательскому вводу, то она по-любому его не найдет, хоть вводи в поле поиска "Свелтый", хоть "Светлый": в БД, согласно условию, хранится название "ТОО Свелтый путь".

К счастью, в языке запросов SQL существует прекрасная конструкция LIKE, которая определяет, начинается ли строковое значение с одного или нескольких символов. Чтобы оператор с использованием LIKE правильно работал, туда следует добавить шаблон в виде символа "*" или одного или нескольких символов "?".

Например:

LIKE "TOO*" (возвратит значение "True" для кучи названий организаций, начинающихся с "ТОО")
LIKE "ТОО Све*" (возвратит "True" для "ТОО Свелтый путь", и возможно, еще для нескольких).
LIKE "??? Све*" (возвратит "True" не только для всех "ТОО Све...", но еще и для всяких разных ЗАО, ОАО, ООО, КСК и даже МЧП , начинающихся со "Све").

Если вы используете язык VBA, например, из MS Access 2000, то выражение LIKE "TOO*" будет эквивалентно функции Access VBA InStr(Left (FieldName,3), "TOO").

Вообще, лучше делать так, чтобы юзер видел названия (организаций, городов, областей и т.д.), а программа работала только с уникальными числовыми идентификаторами, которые с этими названиями однозначно связаны. К примеру, переименовали Акмолу в Астану - ничего страшного, переименуем ее и в БД для соответствующего числового идентификатора, при этом в БД никакой новый город, конечно, не появится.

Сообщение отредактировал Visual1: 23.09.2004, 21:53:51

[Da_ReBeL]

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

[lPhreon]

Думать паможыт виликий Кнут. У ниво на эту тему есть вариантаф.

"Искусство программирования"
Дональд Кнут
3 том
"Сортировка и поиск"

зы
есть в академкниге
очень серьезная книженция
нужно хорошо быть подкованным в математике
вобщем классика!!!

[Whistle]

На мой взгляд есть несколько решений проблемы:

1. Можно использовать метод, предложенный Visual1. С таким же успехом применимы регулярные выражения. По сути это одно и тоже...
Не знаю в какой среде ты пишешь, библиотека TRegExpr для Дельфи лежит здесь...
Краткое описание с примером - тут...

2. Функция приблизительного/нечеткого сравнения строк - реализована на Дельфи, лежит тут - с исходниками и примерами...
Наверное, самый подходящий способ в данном случае...

3. Нейронная сеть Хэмминга (ассоциативная память)...
Сложный (на стадии изучения ), но действенный метод ...
- Мат. аппарат;
- пример;
- откомпилированный пример, без исходников.

Надеюсь, чем-нибудь помог... Удачи!

З.Ы. Еще несколько статей по нечеткому поиску:
1 и 2.

Сообщение отредактировал Whistle: 24.09.2004, 13:07:42

[Shirson]

К счастью, в языке запросов SQL существует прекрасная конструкция LIKE, которая определяет, начинается ли строковое значение с одного или нескольких символов. Чтобы оператор с использованием LIKE правильно работал, туда следует добавить шаблон в виде символа "*" или одного или нескольких символов "?".

Это, простите, в каком SQL такое?
По стандату SQL любой символ идёт как "_" (подчёркивание), а любой набор символов - "%"

LIKE "TOO*" (возвратит значение "True" для кучи названий организаций, начинающихся с "ТОО")
LIKE "ТОО Све*" (возвратит "True" для "ТОО Свелтый путь", и возможно, еще для нескольких).
LIKE "??? Све*" (возвратит "True" не только для всех "ТОО Све...", но еще и для всяких разных ЗАО, ОАО, ООО, КСК и даже МЧП , начинающихся со "Све").

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

Вообще, лучше делать так, чтобы юзер видел названия (организаций, городов, областей и т.д.), а программа работала только с уникальными числовыми идентификаторами, которые с этими названиями однозначно связаны. К примеру, переименовали Акмолу в Астану - ничего страшного, переименуем ее и в БД для соответствующего числового идентификатора, при этом в БД никакой новый город, конечно, не появится.

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

[Contagion]

кстати, а почему бы не взять испеловский словарь и прикрутить его к скрипту?

[Visual1]

К счастью, в языке запросов SQL существует прекрасная конструкция LIKE, которая определяет, начинается ли строковое значение с одного или нескольких символов. Чтобы оператор с использованием LIKE правильно работал, туда следует добавить шаблон в виде символа "*" или одного или нескольких символов "?".

Это, простите, в каком SQL такое?
По стандату SQL любой символ идёт как "_" (подчёркивание), а любой набор символов - "%"

Символы подстановки, указанные Вами ("%" и "_"), действительно, используются в ANSI SQL. Однако в Jet SQL из настольной СУБД MS Access, на примере которой я и давал свой ответ, для описания произвольного количества символов и одного символа применяются символы "*" и "?" соответственно.

LIKE "TOO*" (возвратит значение "True" для кучи названий организаций, начинающихся с "ТОО")
LIKE "ТОО Све*" (возвратит "True" для "ТОО Свелтый путь", и возможно, еще для нескольких).
LIKE "??? Све*" (возвратит "True" не только для всех "ТОО Све...", но еще и для всяких разных ЗАО, ОАО, ООО, КСК и даже МЧП , начинающихся со "Све").

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

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

Вообще, лучше делать так, чтобы юзер видел названия (организаций, городов, областей и т.д.), а программа работала только с уникальными числовыми идентификаторами, которые с этими названиями однозначно связаны. К примеру, переименовали Акмолу в Астану - ничего страшного, переименуем ее и в БД для соответствующего числового идентификатора, при этом в БД никакой новый город, конечно, не появится.

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

Я именно и предполагал, что автор вопроса работает с какой-нибудь настольной СУБД и ограниченным числом записей, а не с мощными клиент-серверными базами (иначе он вообще вряд ли задавал бы подобные вопросы). Эвент можно прикрутить, это точно, а еще можно установить права пользователей, а еще можно не давать пользователям вводить названия организаций, а позволять им только чтобы выбирали готовые названия из раскрывающегося списка, формировать который может только админ в головном офисе... Нет предела совершенству.

[Shirson]

кстати, а почему бы не взять испеловский словарь и прикрутить его к скрипту?

А что это ?

Сообщение отредактировал Shirson: 24.09.2004, 18:45:36

[Shirson]

Символы подстановки, указанные Вами ("%" и "_"), действительно, используются в ANSI SQL. Однако в Jet SQL из настольной СУБД MS Access, на примере которой я и давал свой ответ, для описания произвольного количества символов и одного символа применяются символы "*" и "?" соответственно.

Честно говоря, не знал, что Jet SQL не отвечает стандарту SQL-92.
Учту.

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

Таки да. Я просто привык работать с ...э... несколько большими БД
Для конкретной задачи выбор из списка идёт.

Я именно и предполагал, что автор вопроса работает с какой-нибудь настольной СУБД и ограниченным числом записей, а не с мощными клиент-серверными базами (иначе он вообще вряд ли задавал бы подобные вопросы).

(мечтает о маленькой БД на 50000 записей...)

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

Можно поудобнее сделать.
В таблице, где выводится список, поставить FastFind. Пользователь набирает имя, таблица автоматом прокручивается по введённым частям слова (как Lingvo или в этом же роде).
Вообще да, для небольших решений можно придумать много всяких красивостей)

[Visual1]

Честно говоря, не знал, что Jet SQL не отвечает стандарту SQL-92.
Учту.

Что ж, таково Ваше (с недавних пор) мнение. Но не спешите - есть еще мнение Роджера Дженнингса (Roger Jennings), весьма авторитетного специалиста по Access, SQL Server и другим продуктам Microsoft. Открываем его книгу "Использование Microsoft Access 2000. Специальное издание", и на стр. 849 читаем:
"Access поддерживает не все ключевые слова ANSI SQL, но каждая модификация Jet отвечает стандарту SQL-92."

[Shirson]

Бррр....

Что-то я не втыкаюсь.
По стандарту wildchars идут как _ и %, а не ? и *

[Vaio]

http://delphiworld.n...re_strings.html
или то же самое
http://www.delphikin...ury/compare.htm

там примерчик на дельфи.

Я в свое время что то подобное пытался сделать (проверка фамилий), даже пытался на plsql переписать, но в виду огромной обрабатываемой базы - проще было сделать грамотный ввод данных и долбить пользователей на уровне распоряжений.

[Visual1]

Бррр....

Что-то я не втыкаюсь.
По стандарту  wildchars идут как _ и %, а не ? и *

Честно говоря, и я тоже. Просто процитировал дословно, как сказано в книге. Там вообще-то есть e-mail автора, но беспокоить его по такому поводу мне бы не хотелось. Уж очень он уважаемый человек - автор свыше 20 книг, один из ведущих бета-тестеров Access и SQL Server, редактор программерского журнала, один из составителей электронной справочной системы MSDN Library, президент консалтинговой компании в Калифорнии, и т.д.

[Gloomy]

Visual1, я конечно сорри - но Вы не правы!
И Roger Jennings либо ламо последнее, либо (более вероятно) переводили наши гениЯльные переводчики

А теперь - ВНИМАНИЕ! Ни одна версия MS Access никогда небыла ANSI SQL XX level 1 compliant! ANSI SQL - это видишь ли четкий стандарт, и нельзя быть слегка беремменной

Чтобы не обвинили в голословности вот вам цитата от самих MS:
"This mode conforms closely to the ANSI-92 Level 1 specification but is not ANSI-92 Level 1 compliant. This query mode has more of the ANSI syntax, and the wildcard characters conform to the SQL specification."

Это про MS Access 2002 ANSI-92 query mode. Там вилдкарды уже по ANSI SQL. Про 2003 пока сказать не могу - оно как то само отвалилось Не юзаю я их терерь _вообще_

Всем спасибо за внимание, и с каждого по рублю за лекцию

[BIGGboss]

Метод у Кнута называется SOUNDEX и его реализация по моему не особа сложная... даже Функцией в СУБД реализовываться может.. только проблема со статистиками русских букв. Так же и встроенная функция есть.

С wildcards ами запаришься, чуть база разрастется.. караул.. такие тормоза будут, индексы не помогут.

Сообщение отредактировал BIGGboss: 28.09.2004, 14:32:01

[Коляныч]

ребят, не парьтесь. Транслитерируйте Свелтый и Светлый в что-нибудь типа Sleltiy и Svetliy, а дальше уже soundex'ом. У этого метода есть несколько плохих особенностей в плане транслитерации Ж и Дж, Ы, Й, Ё и т.п., то есть всё похожее нужно единообразно сводить к одному, особенно критично в первой букве. Но в принципе работает.

[Visual1]

Visual1, я конечно сорри - но Вы не правы!
И Roger Jennings либо ламо последнее, либо (более вероятно) переводили наши гениЯльные переводчики

Если я не прав, то укажите, плз, в чем? Что, нельзя применять LIKE и символы "*" и "?" для поиска подстроки, когда работаешь в Access?

Насчет того, что Roger Jennings "ламо последнее" - Вам, возможно, виднее. Правда, его нет на этом форуме, и ответить Вам он не может. А я, еще раз повторяю, лишь дословно процитировал, что было сказано в книге, а вовсе не настаивал на правильности приведенной цитаты.

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

А теперь - ВНИМАНИЕ! Ни одна версия MS Access никогда небыла ANSI SQL XX level 1 compliant! ANSI SQL - это видишь ли четкий стандарт, и нельзя быть слегка беремменной

Но уже в нескольких последних версиях есть средства для быстрой и легкой конвертации БД из формата MS Access в MS SQL Server, который из всех существующих наиболее близок к стандарту ANSI SQL. Так что, если кто на дух не переносит wildcards одного типа, а предпочитает другие - no problem.

Всем спасибо за внимание, и с каждого по рублю за лекцию

Лучше наоборот, с Вас - каждому.

[Gloomy]

>Если я не прав, то укажите, плз, в чем?
Вот в этом:
>"Access поддерживает не все ключевые слова ANSI SQL,
> но каждая модификация Jet отвечает стандарту SQL-92."

Кстати, если автор настолько проффесионал - почему же родную документацию не читает?-) Ссылку я приводил.

>MS SQL Server, который из всех существующих наиболее близок к стандарту ANSI SQL

Тоже перл Так что по рублику со всех, а то пивнушку закроют