Я вам не рассказывал как устроен поиск похожих документов?
Линейное векторное пространство знаете что такое?
А евклидово?
Так вот набор документов представляется евклидовым пространством.
В котором введена метрика.
И собственно похожие документы это те у которых скалярное произведение стремится к нулю :-)
Всё дело лишь в том - как метрику определить :-)
Ну и не надо забывать про "нормированость" метрики.
Ну и "продолжеение" - http://programmingmindstream.blogspot.ru/2014/07/blog-post_7.html
Линейное векторное пространство знаете что такое?
А евклидово?
Так вот набор документов представляется евклидовым пространством.
В котором введена метрика.
И собственно похожие документы это те у которых скалярное произведение стремится к нулю :-)
Всё дело лишь в том - как метрику определить :-)
Ну и не надо забывать про "нормированость" метрики.
Ну и "продолжеение" - http://programmingmindstream.blogspot.ru/2014/07/blog-post_7.html
Этот комментарий был удален автором.
ОтветитьУдалитьПолнотекстовый поиск?
ОтветитьУдалитьЕсть Oracle Text, Lucene, Sphinx наконец...
Векторные пространства - это всё правильно конечно, но IMHO для того, чтобы воспользоваться холодильником не обязательно знать, как устроен компрессор...
Впрочем, конечно же, всё зависит от задачи. И если требования - заоблачные, а бюджет - открытый, то вполне можно поэкспериментировать и на этом поприще... ;-)
Вы к сожалению путаете "поиск похожих" и "полнотекстовый поиск".
УдалитьПро Lucene и Sphinx - мы конечно же в курсе.
А что до "экспериментировать", то это не совсем верное слово.
Вы к сожалению путаете "поиск похожих" и "полнотекстовый поиск".
УдалитьНемудрено спутать. Вы же не определили понятие похожести :-)
Если речь идёт о сравнении документов, то есть вполне работающие решения на основе расчёта расстояния Левенштейна и аналогов.
Боюсь соврать, но возможно, в Oracle даже есть решения на этот счёт. Кое-что мы сами применяем, но тут уверенно говорить не могу, поскольку не я курировал эту тему...
Круто. Вот это мне нравится.
ОтветитьУдалитьНо ведь про самое интересное - саму метрику - ты ни слова не сказал.
ОтветитьУдалитьОстальное вроде и так понятно :)
Ну, Ром. Главное - идея. :-) Привязанная к методике. А вот метрика это как раз то, что не рассказывается :-)
УдалитьИмхо, расстояние Левенштейна не годится для поиска похожих документов, а только для поиска похожих слов (даже не строк). Причем, сам алгоритм очень медленный, нормально работает только в узко очерченных рамках. Для одной задачки (поиск подобных коротких фраз) сначала использовал РС, а потом пришлось написать свой алгоритм, который выдавал результат намного чище и работал на порядок быстрее - потому что был заточен именно под эту задачу.
ОтветитьУдалитьИнтересно, как была решена задача для поиска подобных текстов.
«расстояние Левенштейна не годится для поиска похожих документов, а только для поиска похожих слов (даже не строк).»
Удалить-- Для фраз подходит, и неплохо, но без модификации - будет давать нестабильные результаты. Например, перестановки слов приводят сразу к большим расстояниям.
У себя использовали расстояние Джаро-Винклера.
Сам алгоритм работает быстро (что Левенштейна, что аналоги, основанные на вычислении метрик), проблемы производительности обусловлены способом обработки: расстояние вычисляется для двух фрагментов текста, что не позволяет применять индексный поиск (ну точнее, я не знаю как :-) и вообще сомневаюсь, что это возможно).
Но ускорить можно, и существенно, выполнив ограничение выборки по дополнительным критериям.
Введение в тему нечёткого поиска (сопоставления) текстов неплохо обозначена в этой статье. Вот ещё неплохая подборка.
Ну и, разумеется интересно, если Александр что-нибудь добавит...
Этот комментарий был удален автором.
ОтветитьУдалить"Например, перестановки слов приводят сразу к большим расстояниям".
ОтветитьУдалитьИменно так. Причем, если фраза короткая (2 - 5 слов), то можно, например, отсортировать слова по алфавиту, убрать предлоги и союзы, удалить окончания, а потом сравнить строки. В коротких фразах перестановка слов обычно большой роли не играет: "мама мыла раму", "мыла раму мама", "раму мыла мама" - смысл один и тот же. Но если фраза длинная (сложноподчиненное, сложносочиненное предложение), то сортировка слов просто искажает смысл и алгоритм будет находить "похожие" фразы, которые могут быть противоположными по смыслу.
Вообще, нюансов нужно учитывать огромное количество. А то для документа, где много раз встречается слово "кубометр", программа будет находить подобный документ, где говорится об острове Куба. Это, кстати, реальный пример, из жизни ). Поэтому и интересны подробности алгоритма.
"А то для документа, где много раз встречается слово "кубометр", программа будет находить подобный документ, где говорится об острове Куба"
Удалить-- а вот тут мы наблюдаем "ошибку".
"кубометр" не стоит приводить к "Кубе".
Но это уже зависит от того, как построена "морфология" и/или нормализация.
Интересно... Как Вы отличите собственное "Кубе", в смысле государства в дательном или предложном падеже от существительного "куб" в предложном?
УдалитьIMHO без контекста можно ориентироваться только на регистр первого символа, который может быть простой опечаткой или стремлением акцентировать внимание (Вы например, любите заглавные буквы), а это - очень ненадёжно.
Спасёт то обстоятельство, что тексты, в которых встречаются словосочетания вида "оттянулся по полной на Кубе" нечасто содержат сентенции о геометрии и/или мерах объёма, тем более, в таких единицах измерения... :-)
простите, о "кубе" и "Кубе" - я НИЧЕГО не говорил.. Я говорил о "кубометре" и "Кубе".. А ведь это "две большие разницы"... Понятное дело, что "в рамках предметной области"...
УдалитьНу и потом - насчёт БОЛЬШИХ БУКВ - большие буквы и "маленькие" - сначала опускаются ВНИЗ, а потом капитализируются "для сравнения со словарём". Понятно?
кпСС или КПсс или кПсС - становится КПСС, но не наоборот...
УдалитьМысль понятна?
И потом - СНАЧАЛА всё "нормализуется", а потом только считаются "нормы".
Т.е. СНАЧАЛА текст становится НАБОРОМ НОРМ. Потом "канонизируется". А потом - "всё остальное".
"Цепочки" или "словосочетания" или "устойчивые цепочки".
Ну и понятно, что "нормализация" она - неоднозначна.
Удалить"Суд" и "суда" - это норма от "судов".
Т.е. текст ИЗНАЧАЛЬНО превращается в "список цепочек норм".
А ПОТОМ - "канонизация" и выделение "словосочетаний".
Ну и что касается "словосочетаний".
Удалить"Верховный суд РФ" - это "нормально".
А "Верховные суда РФ" - это НЕ "нормально".
Учитывая нашу "предметную область".
«Я говорил о "кубометре" и "Кубе".. А ведь это "две большие разницы"...»
Удалить-- Разумеется. Но известно, что "кубометр" и "куб" часто используются как синонимы. В цитатах простой речи, в литературе например. Впрочем,если предметная область - правовая база, это не существенно и никакие это не синонимы.
Но я совершенно не об этом. Конечно, это "две большие разницы", но в общем случае разница может быть выявлена только семантически, т.е. с учётом контекста, о чём я и говорил. Слова могут совпасть, если их нормализовать по реальным или возможным словоформам, но контекст - вряд ли.
Соответственно, тексты с упоминанием государства Куба, будут сильно отличаться (в смысле расстояния) от текстов, в которых упоминаются кубы-кубометры.
«Ну и потом - насчёт БОЛЬШИХ БУКВ - большие буквы и "маленькие" - сначала опускаются ВНИЗ, а потом капитализируются "для сравнения со словарём". Понятно?»
-- Откровенно говоря - нет. Не понятно, что значит "опускаются ВНИЗ" (приводятся к нижнему регистру?) и зачем после этого их "капитализировать" (т.е. приводить к верхнему) - почему сразу не привести к верхнему регистру...
То, что со словарём сравниваете - понятно, не понятно только зачем. Для нормализации? Но в таком случае операций с регистром символов недостаточно... Впрочем, всё зависит от способа поиска в словаре...
В общем - непонятно.
Пока я писал - Вы уже ответили. Спасибо.
УдалитьМного общего с алгоритмом, основанным на шинглах...
"Много общего с алгоритмом, основанным на шинглах..."
Удалить-- логично :-) "ничего нового"...
"Соответственно, тексты с упоминанием государства Куба, будут сильно отличаться (в смысле расстояния) от текстов, в которых упоминаются кубы-кубометры."
Удалить-- конечно! :-) За счёт того, что я описал выше.
"То, что со словарём сравниваете - понятно, не понятно только зачем."
Удалить-- как раз "понятно зачем" :-)
Чтобы "суда" и "суд" отличить. И "куб" от "Куба".
"Словарь" это ВАЖНЫЙ элемент "нормализации".
«Причем, если фраза короткая (2 - 5 слов), то можно, например, отсортировать слова по алфавиту, убрать предлоги и союзы, удалить окончания, а потом поискать расстояние Левенштейна.»
ОтветитьУдалить-- Есть модификации алгоритма, которые частично устраняют это свойство. Например, слова можно нормализовать (привести к канонической форме, т.е. без приставок-окончаний) и рассматривать как символы - в таком случае расстояние может существенно сократится...
«Но если фраза длинная (сложноподчиненное, сложносочиненное предложение), то сортировка слов просто искажает смысл и алгоритм будет находить "похожие" фразы, которые могут быть противоположными по смыслу.»
-- Сортировка - изначальное искажение смысла. Вряд ли это приемлемо в большинстве случаев...
Алгоритмы основанные на вычислении расстояний неплохо работают и с документами. Только вместо в качестве символов нужно использовать слова (или, IMHO ещё лучше - нормализованные слова) и даже строки. Diff-ы всяческие, как следует из Википедии, работают именно так.
Альтернативные подходы изложены по ссылкам которые я привёл выше. Разумеется - не все.
У нас несколько иная предметная область, документы по подобию нам искать не приходится, а вот похожие фразы (в широком смысле) - очень даже. Модификация алгоритма Джаро-Винклера вполне устраивает в рамках той предметной области, где мы работаем.
А для сопоставления именно документов (нормализованных текстов, в сущности) IMHO неплохо подходят те же шинглы.
Критику последних очень хотелось бы услышать...
Друзья мои... Мы про "расстояния" и "перестановки" не говорим.
ОтветитьУдалитьВот это:
"Только вместо в качестве символов нужно использовать слова (или, IMHO ещё лучше - нормализованные слова) и даже строки. "
-- уже "ближе к истине".
Просто "слова" или "цепочки слов" как раз в вычислении метрики и участвуют.
«"слова" или "цепочки слов" как раз в вычислении метрики и участвуют.»
Удалить-- Ну, где-то так и работают алгоритмы, основанные на шинглах.
Там берутся равные последовательности канонизированных слов "в нахлёст", по ним считаются хэши.
Имея последовательности хэшей шинглов для искомого документа и проверяемого, можно выполнить их сравнение. Вычислить расстояние того же Левенштейна, например. Проблема в количестве сравнений, поскольку понятно, что чем их больше - тем, вероятно, точнее результат...
Вот здесь - простым языком...