Определение нечетких дубликатов для коротких документов

Хочу поделиться простым, но эффективным алгоритмом определения нечетких копий документов. Есть много статей об использовании для этой цели алгоритма шинглов. Ходят слухи, что большие поисковые системы используют очень похожий алгоритм у себя. Однако, все признают, что шинглы плохо подходят для коротких (3-5 предложений) документов. А в моей задаче надо было работать именно с такими документами. В качестве решения предлагают закольцовывать текст, чтобы как бы сделать из него длинный, но мне кажется, что это не очень правильное решение, точность распознавания дублей все равно будет низкая.

Итак, описание алгоритма, который я использовал:

Сначала нужно проиндексировать коллекцию текстов

1. Преобразуем каждый текст коллекции в массив из слов этого текста, предварительно вырезав html-тэги, цифры и прочую ненужную информацию.
   
2. Отберем 15 самых длинных слов, причем те, что короче 4 символов, не берем в любом случае, даже если сам текст короче 15 слов.
   
3. Для каждого отобранного слова подсчитываем контрольную сумму, например crc32, и пишем суммы в базу данных в формате: «id суммы», «id документа», «сумма».
   
4. В другую таблицу запишем некоторые характеристики самого текста: «md5» и «кол-во слов, которые попали в таблицу с контрольными суммами». Второе поле нужно для тех текстов, для которых не удалось найти 15 слов подходящей длинны, условно это длинна документа в словах.
   

Я использую таблицы со следующей структурой:

CREATE TABLE `items_hashes` (
`id` int(11) NOT NULL auto_increment,
`doc_id` int(11) NOT NULL,
`word_hash` int(11) NOT NULL,
PRIMARY KEY (`id`)
);

CREATE TABLE `items_hashes_summary` (
`doc_id` int(11) NOT NULL,
`full_hash` char(32) NOT NULL,
`length` smallint(11) NOT NULL,
PRIMARY KEY (`doc_id`)
);


Проверка текста на уникальность

После того, как все документы проиндексированы, мы можем проверить любой текст на уникальность в пределах нашей коллекции. Для этого нужно:

1. Выполнить проверку на полное совпадение с каким-либо документом из коллекции используя данные в таблице items_hashes_summary. Если такое совпадение найдено, то следующие шаги смысла не имеют, иначе идем дальше.
   
2. Для проверяемого текста выполнить первые три шага из предыдущего списка, но пока не записывать контрольные суммы в базу.
   
3. Найти в базе документы, в которых есть совпадающие с анализируемым документом слова и количество этих совпадений. Сделать это можно примерно вот таким запросом:
   
   SELECT doc_id, COUNT(id) as intersects FROM items_hashes
WHERE (word_hash = %cur_doc_hash1% OR word_hash = %cur_doc_hash2% OR ... )
GROUP BY doc_id
HAVING intersects > 1

   (на больших коллекциях стоит писать, например HAVING intersects > 5 или даже больше, т.к. иначе дальнейшая обработка может тормозить)
   
4. Теперь находим «степень схожести» в процентом с каждым из найденных документов, которая вычисляется по формуле:
   
   $similarity = ($intersecs/$length)*100,
   
   где $length — длинна самого короткого из сравниваемых документов;
   $intersecs — количество совпадающих слов.
   
   Я считаю, что документ неуникален если его «степень схожести» с каким-либо документом коллекции более 80%, для ваших задач возможно нужно будет подобрать другое значение.
   

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

Все это работает довольно быстро. Во всяком случае на коллекции из 12 тыс. документов и очень слабом VPS никаких проблем нет. Тестировал также на 70 тыс. документов в виртуалке, тоже все было очень быстро.

Пощупать как оно реально работает можно здесь. Можете взять любое объявление, поменять что-то и попробовать добавить как новое. Должно сразу сказать, что очень похожее уже есть в базе. Только если вдруг вы измените объявление слишком сильно и оно добавится, то не забудьте его потом удалить пожалуйста ;)

Пользователи все-таки умудряются публиковать одинаковые по содержанию объявления, но для этого им приходится переписывать практически все другими словами. Ложных срабатываний пока замечено не было.

Реализация на PHP

Чтобы было понятнее, выдрал из проекта два класса, которые реализуют этот алгоритм и положил на pastebin.com: класс, для получения хэшей документа (универсальный и готовый к использованию в любом проекте) и класс модели (не совсем готов для использования в любом проекте, но думаю не сложно будет модифицировать).

P.S. Это мой первый топик на хабре, так что не бейте больно если что-то не так.

UPD: Спасибо всем за карму, теперь могу перенести в блог «Разработка».