Меню
Что нового?

Поиск максимально похожих текстовых данных

MagicGTS

Новичок
Поиск максимально похожих текстовых данных

Вот такая задачка образовалась. Как определить на сколько сообщение от пользователя похоже на сообщения уже присутствующие в базе? Пробывал полнотекстовый поиск, но мне несовсем ясно получаемое значение релевантности.
После какого порога можно считать результат действительно похожим? Пробывал поиск как с короткими текстами (5-7 слов) так и длинными (40 и более). При этом при поиске в коротких предложениях при поиске действительно одинаковых данных получал значение чуть выше 20, а при длинных за 100.
При этом поиск типа LIKE (100% соответствие искомому) не подходит, так как сообщения могут незначительно отличаться (несколько слов изменены).
Есть какие нибудь идеи? Делать смопальный индексатор нехочется...
 

Kelkos

Сам себе программер
Автор оригинала: A-Lex[FM]
Попробуй FULLTEXT
Нажмите для раскрытия...
чел уже пишет - "пробывал".

вообще, ТС, эта задачка далеко не так проста.
Если напишешь такой скрипт или разработаешь универсальный алгоритм, то можешь продавать его за денежки.
 
A-Lex[FM]

A-Lex[FM]

Web/Highload/DataScience
когда я пытался делать похожий функционал, мне посоветовали сделать скрипт синтаксического анализа и складывать в определённую таблицу слова и хэши.
Потом создать таблицу соответствия и через неё выбирать записи по хэшам, одновременно считая колличество совпадений, получая при этом релевантность. вроде идея такая, как я помню. полнотекстовый поиск, в принципе может помочь, если правильно собирать поисковый запрос, указывать включения слов и регулировать вес слова. я остановился на fulltext, но как опцию оставил и like поиск
 

MagicGTS

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

Sergey_Al

Новичок
Автор оригинала: A-Lex[FM]
когда я пытался делать похожий функционал, мне посоветовали сделать скрипт синтаксического анализа и складывать в определённую таблицу слова и хэши.
Потом создать таблицу соответствия и через неё выбирать записи по хэшам, одновременно считая колличество совпадений, получая при этом релевантность. вроде идея такая, как я помню. полнотекстовый поиск, в принципе может помочь, если правильно собирать поисковый запрос, указывать включения слов и регулировать вес слова. я остановился на fulltext, но как опцию оставил и like поиск
Нажмите для раскрытия...
А зачем хэши ? Можно просто индекс на слова и выбирать по нему.
И можно подробнее про fulltext, примерный вид запроса к примеру ?
 

Sergey_Al

Новичок
Итак, мой способ:

Сравниваем два тектса на похожесть.
Тогда, если релевантностью, например, считать "количество совпадающих слов / количество слов из текста с большим количеством слов", то можно сделать так:

Таблица с сообщениями: text(id, text, count - количество слов в тексте)
Таблица слов: words(id, word)
Таблица связей: twc(text_id, word_id, count - количество этого слова в тексте)

А потом примерно так: делаем временную таблицу с искомыми словами и их количествами, пусть это search(word, count), а потом следующим запросом выбираем два самых релевантных текста:

PHP: 
SELECT
	twc.text_id, 
	SUM(
		((twc.count+search.count - ABS(twc.count-search.count))/2) / 
		((text.count+13 + ABS(text.count-13))/2)
	) AS rel
FROM words
LEFT JOIN twc ON(twc.word_id = words.id)
LEFT JOIN search ON(words.word = search.word)
LEFT JOIN text ON(twc.text_id = text.id)
GROUP BY twc.text_id
ORDER BY rel DESC
LIMIT 2
Те ужасные выражения под суммой - минимум и максимум (минимум из количеств двух слов, максимум из слов в тексте).
13 - количество слов в тексте, который мы сравниваем с остальными.
Релевантность изменяется от 0 до 1 включительно :)

-~{}~ 02.05.07 16:57:

Можно ещё заменить SUM(...) на такое, может быть более понятное:

PHP: 
    SUM(        
	((twc.count<=search.count)*twc.count+(twc.count>search.count)*search.count) /  
	((text.count<=13)*13+(text.count>13)*text.count)
    ) AS rel
 

MagicGTS

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

Sergey_Al

Новичок
Левенштайна тут ничем не поможет ... А конкретнее критерии по которым обламывается способ выше?
 

MagicGTS

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

Alexandre

PHPПенсионер
см. Статья Алексея Рыбака PHPInside #7
там есть идеи по использованию словаря Лебедева для релевантного посика.

Материалы PHPConf 5 (последняя), выступление про написание UDF функций, приведен пример функции "вычисление индекса похожести" заданного слова.

в общем надо рулить где-то там...
 

kruglov

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

-~{}~ 03.05.07 13:26:

Просто интересно - какова собственно решаемая проблема.
 

MagicGTS

Новичок
Задача именно как вы написали. Пользователь вводит некий текст (типа на форуме), система ищет похожие, и если совпадений больше 70% показывает пользователю пост который похож на то, что он ввел. Если юзер считает, что его пост всё равно уникален, то он ео добавляет.
 
Войдите или зарегистрируйтесь для ответа.
Сверху