Comments 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 IN

О, спасибо. Все время забываю про эту конструкцию, а она действительно быстрее работает по крайней мере в MySQL.
> учитывать глобальную частоту встречаемости слова, т. е. не учитывать
> общеупотребительные слова
Мысль верная, но по опыту сильно усложняет архитектуру, производительность, и вообще жизнь.
Список стоп слов для украинского и русского языков есть в Яндекс Сервер
Так ведь в 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, но мне там не нравится =)
> Поисковики, например, их напрочь игнорируют в запросах.

вы абсолютно в этом уверены?
Хмм, ну год или два назад так и было, в этом я уверен.
Однако сейчас яндекс с гуглом стал давать разные результаты на запросы «краска для машины» и «краска машины».

При чём, что интересно, разница именно в сортировке результатов.

Так что спасибо за поправку, и извиняюсь за дезинформацию.
а алгоритмом определения нечетких копий документов для текстов побольше — не поделитесь? :)
А вон в самом начале этого поста есть ссылка на алгоритм шинглов и его реализацию на пайтоне. И, кстати, можно попробовать модифицировать мой алгоритм, взять не 15, а побольше слов и выбирать не самые длинные слова, а самые высокочастотные. Вполне возможно, что это будет работать для длинных текстов тоже.
ох пардон, не увидел ссылку…

я в свое время пытался реализовывать алгоритм 3+5 отсюда, но что-то так пороху и не хватило…
Давно думаю эту мысль применимо к более коротким текстам (два-три слова), так, чтобы для малоотличающихся наборов слов значение хэш-функции было бы близким — но результатов (удовлетворительных) пока нету…
он и используется в текущей реализации. принципиальное ограничение — только английский.
А русский текст вы в транслит перегоняете? Неужели это плохо работает? Я думал, что именно так поисковики опечатки поправляют в запросах.
где-то в районе полугода здесь пролетала статья о soundex для русской речи.
Проблема сложнее и комплекснее, чем фонетический поиск — вообще говоря, количество поддерживаемых языков малоограничено, по сути, это как минимум все индоевропейские языки (в более узком смысле — вся романо-германская группа). Поэтому единого решения пока нет.
точнее, используется Double MetaPhone, улучшенная версия этого алгоритма, но это все равно не спасает.
P.S. Это мой первый топик на хабре, так что не бейте больно если что-то не так.

Эта фраза уже по-моему давно у всех ассоциируется примерно с: -«отсыпьте кармы плз чуток» :)

В конкретно этом посте с удовольствием это делаю.

Вообще очень хорошая тема поднята, возможно, даже, имеет смысл сделать отдельный блог — fuzzy logic или как-то более понятно
это практически первый мой коммент, просьба не минусовать сильно
Отличается от моей реализации на пайтоне.

Проблема сравнения коротких текстов заключается в нехватке материала (шинглов) для сравнения. Ставится задача — увеличить их.

По поводу закольцовки текста — я несколько несколько с вами не согласен, можно получить хорошие результаты уменьшив дллину шингла (3-5 слов).

Так же в моей реализации для сравнения коротких текстов можно разбивать текст на шинглы не по словно, а посимвольно, например по 10 символов. При хорошей канонизации текста — результат отличный!

А в целом благодарю за материал — очень интересно!
> По поводу закольцовки текста — я несколько несколько с вами не согласен

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

> разбивать текст на шинглы не по словно, а посимвольно, например по 10 символов.

Да, конечно, есть варианты как адаптировать шинглы под короткие тексты. Я бы даже сказал, что у меня по сути и есть вариация на тему шинглов. Только чешуйки не наслаиваются друг на друга ;)
А зачем в таблице хешей слов использовать суррогатный ключ, занимающий треть таблицы? Не лучше бы так:
CREATE TABLE `items_hashes` (
`doc_id` int(11) NOT NULL,
`word_hash` int(11) NOT NULL,
PRIMARY KEY (`doc_id`,`word_hash`)
);
И в редком случае, когда хеши двух разных слов совпадают, не помещать дубликат в таблицу.
У меня сейчас в проекте на миллион страниц алгоритм попроще: текст без тегов, берутся все слова > 4 символов в строчных буквах, сортируются по алфавиту, склеиваются в строчку и md5 на неё. Получается 32 символа подписи на страницу.

На миллион страниц порядка 2% выявленных дубликатов. Алгоритм обрабатывает всю базу меньше минуты, даже учитывая нахождение базы на другом компьютере.
Мне кажется что сортировка по алфавиту — лишняя. Зачем она тут? Может имелось ввиду удаление слов-дубликатов?
чтобы предложения выстраивались в одну цепочку. Да, и array_unique тоже там же, забыл :)
Тогда получается, что разница в одно слово сразу этот хеш порушит, не? То есть нечеткий он получается только относительно слов из <= 4 букв.
UFO landed and left these words here
Я бы добавил пару замечаний — складывая длинные слова я полагаю вы пытаетесь выдрать те слова которые характерны для текущего текста?

Мне кажется было бы чуть чуть лучше делать так:

1) Тянуть не сами слова а их стеммы.
2) Не просто самые большие слова — а самые частые слова. В данном случае вы сформируете коллекцию ключевых слов. (Важно — нельзя забывать про стоп-лист, а также — словарь синонимов).
Хех, делал такой трюк for fun — в 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-шников, удивлявшихся скорости ответа в полсекунды :-)
Only those users with full accounts are able to leave comments. Log in, please.