Добрый день. Помогите пожалуйста с комбинаторикой. На сайте есть строка запроса, куда пользователь вводит запрос. Запрос этот нужно проанализировать: выкинуть стоп-слова, и проверить данный запрос на соответствие записей в БД. Например, запрос таков: new york city mobile phone, в БД есть записи: phone и mobile phone, т.е. я должна как-то разбить это предложение и посмотреть в БД. Как я понимаю это перестановки или размещения. Дело еще в том, что в БД содержаться записи и из трех, четырех, пяти слов. Т.е. ввели : EXTERNAL OBLIQUE MUSCLE ABDOMINAL , а в БД есть запись ABDOMINAL EXTERNAL OBLIQUE MUSCLE. Т.е. сначала нужно посмотреть каждое слово из запроса в предложении, затем первое вместе со вторым, потом 1-3, потом 2-1, 2-3, 3-1, 3-2. И так до пяти слов ...

Ну так это же неправильно...

Исчерпывающий ответ ... =) БД меняться не будет ..

Это сообщение отредактировал(а) Manonia - 17.9.2010, 12:03

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


А вы что ждали? что к вашей кривой структуре вам найдётся гениальный алгоритм - быстрый и эффективный? нормализацию не от хорошей жизни придумали...

Если (совпадение=3 из 5 совпали), то размещения
Если (совпадение=в точности 5 из 5 совпали), то перестановки
Ищем программы для вычисления всех перестановок в интернете и проверяем

Если фраза из 5 слов - 120 проверок для перестановок (число перестановок из 5 символов)
Для размещений проверок больше чем для перестановок
------------------------------------
Если словарь и база маленькие - нормально

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

Akina, смотрите: у меня есть таблица dictionary, в ней содержатся слова, словосочетания, и есть таблица scenarios, где для каждого слова или словосочетания есть свой сценарий. Эти таблицы связаны. Поэтому слова так и хранятся в первой таблице. Есть такой вариант: берём первое слово, подставляем в запрос:
, потом добавляем второе, потом третье и т.д. Затем также делаем со вторым словом.

nworm, спасибо, постараюсь разобрать =)

Это сообщение отредактировал(а) Manonia - 20.9.2010, 05:13

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

А если задача - найти записи, в которых, скажем, не менее X% от введённых слов - то задача намного сложнее, и, видимо, разумнее использовать нечто вроде мускульного match() against либо внешние поисковые компоненты.

Так вот я и хочу составить наиболее оптимальный запрос =) Вот, например, пользователь ввёл: shopping in new york city, в базе есть и слово city, и словосочетание new york city и просто new york, нужно достать эти записи. А если пользователю стрельнуло и он ввёл: new shopping in york city/ shopping in york city new, результат должен быть таким же как в первом случае. Т.е. слова могут быть в произвольном порядке и у вас в запросе я вижу нужно обязательно подавать 4 слова, когда как мне нужно будет искать и слово и словосочетание из 2-ух, 3-ёх, 4-ёх слов..

Ну так


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

Определенного ответа я так и не получила, но всё равно всем спасибо =)

А FULLTEXT под такое, случайно не заточен? проиндексировать эти странные "ключевые" поля как FULLTEXT и вроде как и все. При сравнени выдается % совпадения, что-то вроде того, что и нужно... Может помешать разве только если база не mySql и "структуру базы менять не будем".

Нет. Под это заточен match - о нём я уже говорил выше.

ksnk, база не MySql и структуру менять не будем =)

Короче, общего инструмента или способа нет.
Так что указывайте конкретную СУБД и просите модератора перенести тему.

Спасибо, база - MS SQL Server =)