Ускорить поиск дублей

Для 5000 записей поиск дублей работал всю ночь.

Обработал 12%.

Предлагаю ускорить.

Отлично, есть предположения как?

Отлично, есть предположения как?

Может быть есть алгоритмы, которые дают менее точный результат, но при этом работают быстрее чем текущий?

То есть можно сделать light-версию на основе другого алгоритма.

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

Как один из вариантов многомерной хэш-функции, одним из параметров считать количество слов.

Если в двух статьях количество слов сильно отличается, то относить их к разным непересекающимся множествам.

Может быть есть алгоритмы, которые дают менее точный результат, но при этом работают быстрее чем текущий?

ну есть у меня одно такое предположение, но точность упадет примерно в 3 раза.

[quote:2glfan37]Может быть есть алгоритмы, которые дают менее точный результат, но при этом работают быстрее чем текущий?

ну есть у меня одно такое предположение, но точность упадет примерно в 3 раза.[/quote:2glfan37]

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

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

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

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

Сейчас ориентировочно неделя работы нужна на проект из 5000 записей, будет три с половиной дня.

Мне кажется в данном случае дело все-таки в слишком прямолинейном алгоритме.

Ощущение что время работы растет по экспоненте в зависимости от числа записей в проекте.

Сейчас алгоритм примерно такой:

1. Берется первый текст

2. Разбивается по указанному числу шинглов на фразы нужной длины (точнее их хеши)

3. Берутся по очереди все следующие за текущей статьи и аналогично разбиваются на шингы и сверяются хеши

Дальше берется второй текст, разбивается и сверяется со всеми следующими, третий и т.д. Т.е. чем ближе к концу, тем скорее движется полоса прогресса. Каждый текст сверяется с каждым один раз (без повторений).

Есть замечания к алгоритму?

Я бы делал через многомерную хеш-функцию и БД.

То есть берем несколько параметров (хеш).

Один раз проходим все тексты.

Потом вводим понятие расстояния между хешами.

С помощью SQL-запроса вытаскиваем все подозрительно похожие пары, к ним применяем более точное сравнение для конкретной пары.

Добавил сегодня многоядерность в функцию поиска дублей. На моем 4-ядерном компе, при использовании 3 ядер (одно оставляю для комфортной работы за компьютером во время обработки) скорость поиска дубликатов по сравнению с 1 ядром (как было раньше) выросла на 115%, т.е. больше чем в два раза. Уже не плохое начало :)