Комментарии 42
Забыл еще добавить идеи по улучшению алгоритма. Слова текста неплохо было бы нормализовать с помощью морфологического анализатора. И еще хорошо бы учитывать глобальную частоту встречаемости слова, т. е. не учитывать общеупотребительные слова и давать буст редким словам при расчете «степени схожести».
> морфологического анализатора
Рекомендую вот этот модуль морфологического анализа (http://aot.ru/download.php). Сам использую в поисковом проекте, доволен.
> т. е. не учитывать общеупотребительные слова
Есть общедоступные списки т.н. стоп-слов — предлогов, союзов и проч. Могу выложить свой, если не найдёте. Поисковики, например, их напрочь игнорируют в запросах.
> WHERE (word_hash = %cur_doc_hash1% OR word_hash = %cur_doc_hash2% OR… )
Лучше WHERE word_hash IN (%cur_doc_hash1%, %cur_doc_hash2%,..) — как минимум логичней смотрится, как максимум возможно СУБД это лучше оптимизирует, т.к. задача более узкая.
Рекомендую вот этот модуль морфологического анализа (http://aot.ru/download.php). Сам использую в поисковом проекте, доволен.
> т. е. не учитывать общеупотребительные слова
Есть общедоступные списки т.н. стоп-слов — предлогов, союзов и проч. Могу выложить свой, если не найдёте. Поисковики, например, их напрочь игнорируют в запросах.
> WHERE (word_hash = %cur_doc_hash1% OR word_hash = %cur_doc_hash2% OR… )
Лучше WHERE word_hash IN (%cur_doc_hash1%, %cur_doc_hash2%,..) — как минимум логичней смотрится, как максимум возможно СУБД это лучше оптимизирует, т.к. задача более узкая.
> Рекомендую вот этот модуль морфологического анализа (http://aot.ru/download.php)
Да, знаю про этот модуль и именно его планирую использовать.
> Есть общедоступные списки т.н. стоп-слов
Список стоп-слов у меня есть, спасибо. Но тут я хотел сказать немного о другом. Например, у меня документы — это объявления, там часто встречаются слова типа продам, куплю и т.д. Было бы логично их игнорировать при анализе или учитывать, но с меньшим весом.
> WHERE word_hash IN
О, спасибо. Все время забываю про эту конструкцию, а она действительно быстрее работает по крайней мере в MySQL.
Да, знаю про этот модуль и именно его планирую использовать.
> Есть общедоступные списки т.н. стоп-слов
Список стоп-слов у меня есть, спасибо. Но тут я хотел сказать немного о другом. Например, у меня документы — это объявления, там часто встречаются слова типа продам, куплю и т.д. Было бы логично их игнорировать при анализе или учитывать, но с меньшим весом.
> WHERE word_hash IN
О, спасибо. Все время забываю про эту конструкцию, а она действительно быстрее работает по крайней мере в MySQL.
а можно попросить выложить списки стоп-слов?
Вот хороший: snowball.tartarus.org/algorithms/russian/stop.txt (только кодировка там koi8-r, но я думаю перекодировать не проблема)
Список стоп слов для украинского и русского языков есть в Яндекс Сервер
Так ведь в MySQL не работает WHERE IN () с паттернами ("%a%")? Какую СУБД вы используете?
%cur_doc_hash1% — это как бы переменная, которую вы должны подставить в запрос в скрипте.
я например сделал врапер для MySQL, который использует синтаксис плайс холдеров
$db->query('select id, ?# from ?# where id = ?d ', 'text', 'table', 10);
далее на плайсхолдеры накладываются фильтры:? — просто как текст берется в кавычки и эскейпится
?d приводится к числу
?# эскейпится и берется в обратные кавычки
?f — в число с точкой
?a — если числовой массив, то через запятую значения фильтрованные как? или если ассц массив то как пары ?# =? очень удобно в запросах класса where in (?a) — тут список или insert… set (?a) — тут ассоц массив
Если самому писать лень можете взять на dklab.ru, но мне там не нравится =)
$db->query('select id, ?# from ?# where id = ?d ', 'text', 'table', 10);
далее на плайсхолдеры накладываются фильтры:? — просто как текст берется в кавычки и эскейпится
?d приводится к числу
?# эскейпится и берется в обратные кавычки
?f — в число с точкой
?a — если числовой массив, то через запятую значения фильтрованные как? или если ассц массив то как пары ?# =? очень удобно в запросах класса where in (?a) — тут список или insert… set (?a) — тут ассоц массив
Если самому писать лень можете взять на dklab.ru, но мне там не нравится =)
> Поисковики, например, их напрочь игнорируют в запросах.
вы абсолютно в этом уверены?
вы абсолютно в этом уверены?
Грамотно и полезно. Спасибо.
а алгоритмом определения нечетких копий документов для текстов побольше — не поделитесь? :)
А вон в самом начале этого поста есть ссылка на алгоритм шинглов и его реализацию на пайтоне. И, кстати, можно попробовать модифицировать мой алгоритм, взять не 15, а побольше слов и выбирать не самые длинные слова, а самые высокочастотные. Вполне возможно, что это будет работать для длинных текстов тоже.
ох пардон, не увидел ссылку…
я в свое время пытался реализовывать алгоритм 3+5 отсюда, но что-то так пороху и не хватило…
я в свое время пытался реализовывать алгоритм 3+5 отсюда, но что-то так пороху и не хватило…
Давно думаю эту мысль применимо к более коротким текстам (два-три слова), так, чтобы для малоотличающихся наборов слов значение хэш-функции было бы близким — но результатов (удовлетворительных) пока нету…
Может soundex попробовать? ru.wikipedia.org/wiki/Soundex
он и используется в текущей реализации. принципиальное ограничение — только английский.
А русский текст вы в транслит перегоняете? Неужели это плохо работает? Я думал, что именно так поисковики опечатки поправляют в запросах.
Да, вот кстати ссылка на тот пост про русский soundex habrahabr.ru/blogs/php/28752/
точнее, используется Double MetaPhone, улучшенная версия этого алгоритма, но это все равно не спасает.
P.S. Это мой первый топик на хабре, так что не бейте больно если что-то не так.
Эта фраза уже по-моему давно у всех ассоциируется примерно с: -«отсыпьте кармы плз чуток» :)
В конкретно этом посте с удовольствием это делаю.
Вообще очень хорошая тема поднята, возможно, даже, имеет смысл сделать отдельный блог — fuzzy logic или как-то более понятно
Исходник на PHP + возможность проверки 2-х текстов на схожесть utext.rikuz.com/
Отличается от моей реализации на пайтоне.
Проблема сравнения коротких текстов заключается в нехватке материала (шинглов) для сравнения. Ставится задача — увеличить их.
По поводу закольцовки текста — я несколько несколько с вами не согласен, можно получить хорошие результаты уменьшив дллину шингла (3-5 слов).
Так же в моей реализации для сравнения коротких текстов можно разбивать текст на шинглы не по словно, а посимвольно, например по 10 символов. При хорошей канонизации текста — результат отличный!
А в целом благодарю за материал — очень интересно!
Проблема сравнения коротких текстов заключается в нехватке материала (шинглов) для сравнения. Ставится задача — увеличить их.
По поводу закольцовки текста — я несколько несколько с вами не согласен, можно получить хорошие результаты уменьшив дллину шингла (3-5 слов).
Так же в моей реализации для сравнения коротких текстов можно разбивать текст на шинглы не по словно, а посимвольно, например по 10 символов. При хорошей канонизации текста — результат отличный!
А в целом благодарю за материал — очень интересно!
А где можно посмотреть на вашу реализацию?
Так ссылка в начале этого поста на мою статью :)
www.codeisart.ru/python-shingles-algorithm/
www.codeisart.ru/python-shingles-algorithm/
> По поводу закольцовки текста — я несколько несколько с вами не согласен
Мне просто кажется, что это не совсем разумное использование ресурсов сервера. Т.е. если у нас почти все документы длинные и только несколько коротких, то это хорошее решение, чтобы не писать отдельный алгоритм под короткие. Но когда все короткие, то по идее мы будем делать много лишних вычислений.
> разбивать текст на шинглы не по словно, а посимвольно, например по 10 символов.
Да, конечно, есть варианты как адаптировать шинглы под короткие тексты. Я бы даже сказал, что у меня по сути и есть вариация на тему шинглов. Только чешуйки не наслаиваются друг на друга ;)
Мне просто кажется, что это не совсем разумное использование ресурсов сервера. Т.е. если у нас почти все документы длинные и только несколько коротких, то это хорошее решение, чтобы не писать отдельный алгоритм под короткие. Но когда все короткие, то по идее мы будем делать много лишних вычислений.
> разбивать текст на шинглы не по словно, а посимвольно, например по 10 символов.
Да, конечно, есть варианты как адаптировать шинглы под короткие тексты. Я бы даже сказал, что у меня по сути и есть вариация на тему шинглов. Только чешуйки не наслаиваются друг на друга ;)
А зачем в таблице хешей слов использовать суррогатный ключ, занимающий треть таблицы? Не лучше бы так:
У меня сейчас в проекте на миллион страниц алгоритм попроще: текст без тегов, берутся все слова > 4 символов в строчных буквах, сортируются по алфавиту, склеиваются в строчку и md5 на неё. Получается 32 символа подписи на страницу.
На миллион страниц порядка 2% выявленных дубликатов. Алгоритм обрабатывает всю базу меньше минуты, даже учитывая нахождение базы на другом компьютере.
На миллион страниц порядка 2% выявленных дубликатов. Алгоритм обрабатывает всю базу меньше минуты, даже учитывая нахождение базы на другом компьютере.
Я бы добавил пару замечаний — складывая длинные слова я полагаю вы пытаетесь выдрать те слова которые характерны для текущего текста?
Мне кажется было бы чуть чуть лучше делать так:
1) Тянуть не сами слова а их стеммы.
2) Не просто самые большие слова — а самые частые слова. В данном случае вы сформируете коллекцию ключевых слов. (Важно — нельзя забывать про стоп-лист, а также — словарь синонимов).
Мне кажется было бы чуть чуть лучше делать так:
1) Тянуть не сами слова а их стеммы.
2) Не просто самые большие слова — а самые частые слова. В данном случае вы сформируете коллекцию ключевых слов. (Важно — нельзя забывать про стоп-лист, а также — словарь синонимов).
Хех, делал такой трюк for fun — в IRC на канале викторина была: бот выдаёт определение, надо ответить, что за термин определяется.
Недолго думая, сделал из трёх энциклопедических словарей почти такую же БД (даже словоформы не использовал, не говоря уже о стоп-словах и синонимах), написал подобный запрос:
Было смешно смотреть на IRC-шников, удивлявшихся скорости ответа в полсекунды :-)
Недолго думая, сделал из трёх энциклопедических словарей почти такую же БД (даже словоформы не использовал, не говоря уже о стоп-словах и синонимах), написал подобный запрос:
SELECT COUNT(definer_id) AS matches, word FROM defs JOIN words ON (term_id = word_id)
WHERE definer_id IN(SELECT word_id FROM words WHERE word IN (%(word_list)s)) AND LENGTH(word) = %(word)s
GROUP BY term_id,word HAVING COUNT(definer_id) > 1 ORDER BY matches DESC LIMIT 10
Было смешно смотреть на IRC-шников, удивлявшихся скорости ответа в полсекунды :-)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Определение нечетких дубликатов для коротких документов