| Вопрос: SELECT ... WHERE в MySQL - неточное совпадение | Добавлено: 19.04.10 21:52 |
Автор вопроса:  Programmer
|
|
Допустим, в таблице chatbot есть такие записи в поле messages: добрый день завтра
добрый дядя добрый вечер [B]будет ли добрый день сегодня[/B] доброе время суток завтра не сегодня И есть строка в переменной (юзаю PHP): "сегодня добрый день". Как составить SELECT, чтобы получить по этой строке максимальное совпадение (в данном случае это "будет ли добрый день сегодня" - в этой строке совпадает больше всего слов с начальной строкой)? Поддержка окончаний пока не требуется - это следующий этап) Оператор LIKE вроде как не подходит, так как он позволяет искать %вхождение%, но если оно не точное... Поиск примерно как в гугле - сначала выдается строка, максимально релевантная данной, потом менее и т.д. Перебирать все строки не катит - их может быть очень много. Заранее спасибо! P.S. Не уверен, может я не в тот раздел запостил, надеюсь Павел на меня не обидится) |
| Ответы | Всего ответов: 15 |
|
Номер ответа: 1 Автор ответа:  Дмитрий Юпатов Вопросов: 4 Ответов: 457 |
Web-сайт: Профиль | | #1 | Добавлено: 19.04.10 22:44 |
| разбивай строку, которая типа входит, и проверяй с каждой фразой - где больше всего отдельных слов совпадет. | ||
|
Номер ответа: 2 Автор ответа: Дмитрий ЮпатовВопросов: 4 Ответов: 457 |
Web-сайт: Профиль | | #2 | Добавлено: 19.04.10 22:46 |
|
Перебирать все строки не катит - их может быть очень много а есть варианты? Ты сам бы как делал? (ну, мысленно)
|
||
|
Номер ответа: 3 Автор ответа: ProgrammerВопросов: 71 Ответов: 246 |
Профиль | | #3 | Добавлено: 20.04.10 00:21 |
|
Пока вижу вариант: разбить строку на слова и сделать SELECT ... WHERE ... LIKE %...% для каждого из них. Запись в таблице, которая будет показана на больше всего слов - та, что нужна. Но в строке может быть и 100 слов, а это 100 запросов на ровном месте. Меня интересует, есть ли более оптимальный алгоритм. Структуру таблицы менять еще не поздно, так что... А есть у MySQL возможность выводить не "записи, кооторые содержат %подстроку%", а записи, которые "являются подстрокой для %$s%"? Типа WHERE "abcd" IN messages.
Тогда сразу хочу спросить: слышал кто-нибудь про алгоритм на PHP для нахождения и удаления окончаний слов? Не хочу изобретать велосипед. |
||
|
Номер ответа: 4 Автор ответа:   Администратор ICQ: 278109632 Вопросов: 42 Ответов: 3949 |
Web-сайт: Профиль | | #4 | Добавлено: 20.04.10 08:25 |
| Извлекать всю строку и использовать техники fuzzy string compare | ||
|
Номер ответа: 5 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #5 | Добавлено: 20.04.10 11:12 |
|
В БД можно хранить инвертированный индекс (нормализованное слово, количество вхождений в строку, номер строки). Потом просто исполняешь запрос
select line, sum(num) as s from ii where word in ("сегодня", "добрый", "день"  group by line order by s desc
и получаешь результат. |
||
|
Номер ответа: 6 Автор ответа: ProgrammerВопросов: 71 Ответов: 246 |
Профиль | | #6 | Добавлено: 20.04.10 16:06 |
|
Executioner, для этого надо получить все строки из бд. А если их миллион? Миллиард?
Sharp, идея интересная, но видимо моих познаний в MySQL не хватает, чтобы полностью ее понять. Можешь объяснить подробнее? Пока что понял, что можно сделать отдельную таблицу с полями word, count и msgid, где, при добавлении новой строки в основную таблицу, будут отдельно добавляться слова, их количество и id строки, в которой они находяться. Тогда поиск упрощается... Правильно я понял? |
||
|
Номер ответа: 7 Автор ответа: ProgrammerВопросов: 71 Ответов: 246 |
Профиль | | #7 | Добавлено: 20.04.10 17:10 |
| А если будет несколько вариантов - в одном меньше "воды", в другом больше, при этом "релевантность" одинаковая - как опредилить это и выбрать первый? | ||
|
Номер ответа: 8 Автор ответа: ProgrammerВопросов: 71 Ответов: 246 |
Профиль | | #8 | Добавлено: 20.04.10 18:09 |
| А что если искать так: ... WHERE message LIKE %добрый% AND message LIKE %сегодня% AND message LIKE %день% ? Правда, тогда частичные совпадения не будут найдены. Но перед тем как пользоваться предложением Sharp, я думаю, можно сделать 1 такой запрос, что может сократить количество запросов в случаях, когда в message те же слова, но переставлены местами. Или так нельзя? Пошел проверять... | ||
|
Номер ответа: 9 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #9 | Добавлено: 20.04.10 21:59 |
|
Дело тут не в MySQL, а в хранении специально подготовленной структуры данных — inverted index, в которой хранятся тройки (слово; документ, в котором оно встречается; количество раз, которое оно в этом документе встречается).
Если тебе нужна более-менее хорошая релевантность документа запросу, можно использовать сумму весов TF-IDF (http://en.wikipedia.org/wiki/Tf%E2%80%93idf). Оказывается, из inverted index по многословному запросу можно получить тексты, отсортированные по такой релевантности, одним запросом:
Сначала мы берем таблицу WxWxT, выбирая из W только записи о наших словах, сворачиваем по упоминанию, получая в count(*) количество документов, в которых есть текущее слово. Из количества слов в текущем документе и количестве упоминаний текущего слова получаем TF, с помощью подзапроса к длине таблицы T и log2 получаем IDF и тут же их перемножаем. Чтобы снова свернуть результат по text_id, используем вложенный запрос, запрашивая sum(tfidf). |
||
|
Номер ответа: 10 Автор ответа: ProgrammerВопросов: 71 Ответов: 246 |
Профиль | | #10 | Добавлено: 20.04.10 22:59 |
|
Проверяю... странно как-то работает. Хотя... по количеству слов может быть так и надо?
По запросу "добрый" и "сегодня" возвращает: (Мне надо, чтобы второй пункт здесь был первым.) text_id txt relevancy По возрастанию
6 завтра не сегодня 0.611196210565174 4 будет ли добрый день сегодня 0.3611962104106 3 добрый вечер 0.111196210256025 2 добрый дядя 0.111196210256025 5 доброе время суток 0.0741308068373503 1 добрый день завтра 0.0741308068373503 При таких записях в texts text_id txt nword
1 добрый день завтра 3 2 добрый дядя 2 3 добрый вечер 2 4 будет ли добрый день сегодня 4 5 доброе время суток 3 6 завтра не сегодня 2 words id text_id word ncount
1 1 добрый 1 2 2 добрый 1 3 3 добрый 1 4 4 добрый 1 5 5 добрый 1 6 1 день 1 7 4 день 1 8 1 завтра 1 9 6 завтра 1 10 2 дядя 1 11 3 вечер 1 12 4 будет 1 13 4 сегодня 1 14 6 сегодня 1 15 5 время 1 16 5 суток 1 17 6 не 1 Так и надо? Если да - то как сделать, чтобы в моем случае второй пункт выводился первым? |
||
|
Номер ответа: 11 Автор ответа: ProgrammerВопросов: 71 Ответов: 246 |
Профиль | | #11 | Добавлено: 20.04.10 23:01 |
| P.S. "ли" я не считаю за слово, а "не" - считаю, поскольку оно меняет смысл текста. | ||
|
Номер ответа: 12 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #12 | Добавлено: 20.04.10 23:05 |
| Слово "сегодня" встречается гораздо реже, чем "добрый", который есть почти везде, поэтому его вес значительно выше. А т.к. фраза "завтра не сегодня" содержит почти в два раза больше слова "сегодня", чем "будет ли добрый день сегодня", релевантность "завтра не сегодня" оказывается выше. Допустим, есть запрос "и трансформаторы", какой документ будет релевантнее, в котором один раз упомянуто "и" и один "трансформаторы", либо же в котором нет ни слова про "и", зато полно "трансформаторов"? | ||
|
Номер ответа: 13 Автор ответа: ProgrammerВопросов: 71 Ответов: 246 |
Профиль | | #13 | Добавлено: 20.04.10 23:10 |
|
Пардон, поправка:
texts: 6 завтра не сегодня 3 Это кардинально не меняет результаты. |
||
|
Номер ответа: 14 Автор ответа: ProgrammerВопросов: 71 Ответов: 246 |
Профиль | | #14 | Добавлено: 20.04.10 23:14 |
| Я думаю, что наиболее релевантный результат все-таки должен содержать по возможности все слова из запроса. Теперь понятно, почему я в гугле ищу "несколько слов", но на некоторых страницах бывает некоторых из этих слов вообще нету) | ||
|
Номер ответа: 15 Автор ответа: ProgrammerВопросов: 71 Ответов: 246 |
Профиль | | #15 | Добавлено: 20.04.10 23:26 |
| В любом случае спасибо! Буду выбирать текст случайно от max_relevancy/2 до max_relevancy. Как ты уже наверное догадался, это будет чат-бот. | ||
Страница: 1 |