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

Тема в разделе "PHP", создана пользователем myweb, 4 июн 2009.

Статус темы:
Закрыта.
Модераторы: latteo
  1. myweb

    myweb Среда обитания WEB

    Регистр.:
    10 сен 2007
    Сообщения:
    539
    Симпатии:
    246
    Нашол класс на PHP : Алгоритм Шинглов - определяем уникальность текста
    http://techforweb.ru/archives/218

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

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

    Вот мой код
    PHP:
    $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();
          }
      }
     }
     
  2. vivid

    vivid Постоялец

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

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

    upandhigh

    Регистр.:
    11 фев 2009
    Сообщения:
    235
    Симпатии:
    89
    урл он ведь дал: http://techforweb.ru/archives/218
    2ТС
    там юзается МД5 функция, она весьма медленная и ресурсоемкая, тамже ниже в коментах человек говорит о том что успешно заменил ее на crc32, кстати как вариант ее предлагает заменить и автор попробуй тоже и сравни результаты. там в одной строчке в самой либе найди md5 и замени на crc32

    вот это
    PHP:
            $shingles[] = md5(implode(' 'array_slice($words$i$length)));
    на вот так
    PHP:
            $shingles[] = crc32(implode(' 'array_slice($words$i$length)));
     
    myweb нравится это.
  4. vivid

    vivid Постоялец

    Регистр.:
    13 апр 2009
    Сообщения:
    143
    Симпатии:
    18
    хм. там нет метода 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 снабжено индексом.
     
  5. myweb

    myweb Среда обитания WEB

    Регистр.:
    10 сен 2007
    Сообщения:
    539
    Симпатии:
    246
    вот именно нужно как раз похожесть текста, поиск происходит по базе объявлений и нужно удалить похожие объявление.
     
  6. vivid

    vivid Постоялец

    Регистр.:
    13 апр 2009
    Сообщения:
    143
    Симпатии:
    18
    я бы переписал этот класс следующим образом (или расширил бы при помощи наследования:(
    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), вот эта задача не триваильна, скоро допишу и здесь опубликую.

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

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

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

    myweb Среда обитания WEB

    Регистр.:
    10 сен 2007
    Сообщения:
    539
    Симпатии:
    246
    длину шингла поставил 7 потому что длина объявлений не большая.

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

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

    vivid Постоялец

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