Оптимизация поиска дубликатов

[myweb]

Нашол класс на PHP : Алгоритм Шинглов - определяем уникальность текста

Для просмотра скрытого содержимого вы должны войти или зарегистрироваться.

работает нормально НО очень медленно проверка 5 записей занимает 100 сек за условия что в базе 13000 записей.

Возможно есть лучшие реализации?

Вот мой код

$setting  = parse_ini_file($_SERVER["DOCUMENT_ROOT"].'/lib/shingles.ini');
$arr=array();
$result = mysql_query("SELECT id,text FROM  msg");
while ($info = mysql_fetch_array($result)){$arr[$info['id']]= $info['text'];}

 $shingles = new Shingles($setting);
 foreach ($arr as $key1 => $value1) {
  $shingles->setText($value1,0); 
  foreach ($arr as $key2 => $value2) {
  	if ($key1 != $key2){
  		$shingles->setText($value2,1);
  		$p = $shingles->compaire($shingles->getShigles()); 
  		if ($p>0) echo  $p.' % #'.$key1.' #'.$key2.'<br>';
  		flush();
  	}
  }
 }

 

[vivid]

хм, а зачем двойной цикл, что-то не пойму, 13000 записей это 13000 * 13000 итераций вложенного цикла код O(n^2), по идее эти результаты надо складывать в ассоциативный массив. и сравнивать из массива, итак у тебя будет 13000 вызовов посчитать значение в вызове setText и 13000 * 13000 вызовов сравнений, если сравнение бысрее чем вычисление, то есть выигрышь в производительности значительный

Добавлено через 1 минуту
хотелось бы еще код библиотеки шиндлов вот этой узнать или урл

 

[upandhigh]

хм, а зачем двойной цикл, что-то не пойму, 13000 записей это 13000 * 13000 итераций вложенного цикла код O(n^2), по идее эти результаты надо складывать в ассоциативный массив. и сравнивать из массива, итак у тебя будет 13000 вызовов посчитать значение в вызове setText и 13000 * 13000 вызовов сравнений, если сравнение бысрее чем вычисление, то есть выигрышь в производительности значительный
Добавлено через 1 минуту
хотелось бы еще код библиотеки шиндлов вот этой узнать или урл

урл он ведь дал:

Для просмотра скрытого содержимого вы должны войти или зарегистрироваться.

2ТС
там юзается МД5 функция, она весьма медленная и ресурсоемкая, тамже ниже в коментах человек говорит о том что успешно заменил ее на crc32, кстати как вариант ее предлагает заменить и автор попробуй тоже и сравни результаты. там в одной строчке в самой либе найди md5 и замени на crc32

вот это

        $shingles[] = md5(implode(' ', array_slice($words, $i, $length)));

на вот так

        $shingles[] = crc32(implode(' ', array_slice($words, $i, $length)));

 

[vivid]

хм. там нет метода setText, как его реализовали?

ммм... разбирательство займет время.

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

select GROUP_CONCAT(DISTINCT id SEPARATOR ' ') from queries group by extra_value having count(*)>1;
.........................
| 35209 4261 6344 17777 1055 42822                          |
| 35870 37302                                               |
| 901 5572                                                  |
| 43050 1958                                                |
| 1056 38517                                                |
| 5521 371                                                  |
| 23754 325                                                 |
| 1461 9759 4478                                            |
+-----------------------------------------------------------+
8460 rows in set (0.45 sec)
mysql> select count(*) from queries;                                            +----------+
| count(*) |
+----------+
|    42673 |
+----------+
1 row in set (0.00 sec)
mysql> show columns from queries;                                               +-----------------+--------------+------+-----+---------------------+----------------+
| Field           | Type         | Null | Key | Default             | Extra          |
+-----------------+--------------+------+-----+---------------------+----------------+
| id              | int(11)      | NO   | PRI | NULL                | auto_increment |
| value           | varchar(255) | NO   | UNI |                     |                |
| disabled        | tinyint(1)   | NO   |     | 0                   |                |
| extra_value     | varchar(255) | NO   | MUL |                     |                |
| create_datetime | datetime     | NO   |     | 0000-00-00 00:00:00 |                |
+-----------------+--------------+------+-----+---------------------+----------------+

довольно быстро и ни какого PHP, естественно поле extra_value снабжено индексом.

 

[myweb]

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

вот именно нужно как раз похожесть текста, поиск происходит по базе объявлений и нужно удалить похожие объявление.

 

[vivid]

я бы переписал этот класс следующим образом (или расширил бы при помощи наследования
1. метод addTextWithId($text,$id);
при добавлении текста сразу происходит канонизация и вычисление шинглов (_canonizeString и _getShinglesFromString) далее каждый шингл добавляем в массив ассоциаций шингл- идентификаторы строк, к классу добавляется поле var $_shingle2ids - ассоциативный массив устанавливающий связи между значением шингла и идентификаторами строк ( $this->_shingle2ids[$shingle][$id] = true, так хитро чтоб исключить повторение подстрочки в одной строчке). Я думаю ради оптимизации следует создать массив, в котором хранятся случаи поимки дубликатов шинглов, чтоб в функции «вернуть дубликаты» не обходить все шинглы впустую, а обработать сразу те, которые дублируются $_shingleDuplicates ( перед добавлением производить проверку if(isset($this->_shingle2ids[$_shingle2ids])) $this->_shingleDuplicates[$shingle] = true; ).

2. и метод getDuplicates() – вернуть дубликаты
проходим массив _shingleDuplicates и группируем тексты по дублирующимся шинглам (чтоб отлавливать в одну группу XXABCXX, XXXBCDXX, XXABCDXX), вот эта задача не триваильна, скоро допишу и здесь опубликую.

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

ппс. в оригинале класс не годится т.к. он разработан для сравнения только пары строк. а это не масштабируемое решение.

и вопрос в догонку: каков размер шингла вы определили?

 

[myweb]

длину шингла поставил 7 потому что длина объявлений не большая.

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

Но существуют еще проблема если динамически генерировать весь массив при добавлении объявления это может не понравиться хостеру, а если хранить в базу то таблица шинглов получилася большей чем таблица объявлений

 

[vivid]

Но существуют еще проблема если динамически генерировать весь массив при добавлении объявления это может не понравиться хостеру, а если хранить в базу то таблица шинглов получилася большей чем таблица объявлений

лучше всё таки хранить в базе (как никак пересчитывать шинглы для 10000 объявлений не разово, а каждый раз при попытке добавить объявление), не думаю что таблица шинглов будет много больше таблицы объявлений
к примеру L средняя длинна объявления в байтах, средняя длина слова 5.2 по корпусу текстов. ну округлим до 5, итого должно быть 11 байт на слово(если utf-8). (L/11)-6 столько шинглов одно объявление генерит, плюс это же пары 4-байтных чисел - одно число значение шингла, второе число идентификатор объявление. итого ((L/11)-6)*8 = (8*L/11 - 48) байтов для каждого объявления. плюс индексация по значению шинглов, так что не похоже что таблица шинглов будет больше чем таблица объявлений.
сравни две таблицы по месту занимаемому ими на диске.