Высокопроизводительная проверка сималираты PHP на большой базе данных - PullRequest
1 голос
/ 01 июня 2011

У меня 30 000 строк в базе данных, которые необходимо проверить на сходство (используя similar_text или другую такую ​​функцию).

Для этого потребуется 30 000 ^ 2 проверок для каждого столбца.

По моим оценкам, я буду проверять в среднем 4 столбца.

Это означает, что мне придется выполнить 3 600 000 000 проверок.

Что является лучшим (самым быстрым и самым надежным)способ сделать это с помощью PHP, имея в виду ограничения памяти и ограничения времени запросов и т. д.

Сервер должен по-прежнему активно обслуживать веб-страницы одновременно с этим.

PS.Используемый нами сервер - это 8-ядерный Xeon 32 ГБ оперативной памяти.

Редактировать:

Размер каждого столбца обычно не превышает 50 символов.

Ответы [ 2 ]

1 голос
/ 01 июня 2011

Полагаю, вам нужен только ПОЛНЫЙ ТЕКСТ.

Если это вас не устраивает, у вас есть только один шанс решить эту проблему: кэшировать результаты. Таким образом, вам не придется анализировать 3bil записей для каждого запроса

В любом случае вот как вы можете это сделать:

   $result = array();       

   $sql = "SELECT * FROM TABLE";
   while( $row = ... ) {
      $result[] = $row;    //> Append the current record     
   }

Теперь результаты содержат все строки из вашей таблицы.

В этот момент вы сказали, что хотите similar_text() все столбцы друг с другом.
Для этого и кеширования результатов вам понадобится хотя бы таблица (как я уже говорил в комментарии).

   //> Starting calculating the similarity
   foreach($result as $k=>$v) {
      foreach($result as $k2=>$v2) {

           //> At this point you have 2 rows, $v and $v2 containing your column

           $similarity = 0;

           $similartiy += levensthein($v['column1'],$v2['column1']);
           $similartiy += levensthein($v['column2'],$v2['column2']);               
           //> What ever comparison you need here between columns

           //> Now you can finally store the result by inserting in a table the $similarity
           "INSERT DELAYED INTO similarity (value) VALUES ('$similarity')"; 

      }                      
   }

2 Вещи, на которые вы должны обратить внимание:

  • Я использовал levensthein , потому что он намного быстрее, чем Similar_text (обратите внимание, что это значение противоположно Similar_text, потому что чем больше значение, которое возвращает levensthein, тем меньше сходство между строками)

  • Я использовал INSERT DELAYED , чтобы значительно снизить стоимость базы данных

0 голосов
/ 01 июня 2011

oy ... Similar_text () - это O (n ^ 3)!

вам действительно нужно процентное сходство для каждого сравнения или вы можете просто сделать быстрое сравнение первого / среднего / последнего Xбайтов строк, чтобы сузить поле?

если вы просто ищете дупс, скажите ... вы, вероятно, можете сузить количество сравнений, которое вам нужно сделать, и это будет наиболее эффективным способом imho.

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