Каким способом можно ускорить выполнение скрипта по поиску похожих записей и их удаление из базы (пример скрипт в вопросе)?

Question

[Имя Фамилия]

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

//берем записи по порядку и пробегаем базу
$row_res = mysql_query("SELECT id, title FROM blog WHERE st = 0 ORDER by id");

         while ($row = mysql_fetch_assoc($row_res)) {

                   $str = $row['title'];    
 
                   //ставим в базу 2, означает - запись уже обработана
                   mysql_query("UPDATE blog SET st = 2 WHERE id = $row['id']");



                              //пробегам все записи и сверяем с взятой записью
                              $rows_res = mysql_query("SELECT id, title FROM blog WHERE st = 0 ORDER by id");

                                               while ($rows = mysql_fetch_assoc($rows_res)) {

                                                         $sim = similar_text($row['title'], $rows['title'], $perc);
                                                         $sims = round($perc);
                                                         if($sims > 73) {mysql_query("DELETE FROM blog WHERE id = $rows['id']");}
}
}

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

Есть ли способ ускорить?

Comments

[Akina]

Бессмысленный и беспощадный скрипт... 9 триллионов итераций. К тому же он даже не думает над тем, какую запись из пары похожих удалить.
Ну и similar_text, с его O(N^3), тоже не подарок.

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

Я бы пошёл по пути разборки записей на токены (слова) и выделения групп записей со значительным совпадением набора токенов. Тоже не сахар, но на 3кк записей речь шла бы, наверное, о нескольких часах.

[Spartak (Web-StyleStudio)]

SELECT id, title FROM blog WHERE st = 0 ORDER by id

Во-первых зачем один и тот же запрос два раза выполнять? Особенно второй в цикле...
Ну и во-вторых зачем ORDER by id если всеравно по всем записям будет проход.

[Spartak (Web-StyleStudio)]

WHERE st = 0 ORDER by id

mysql_query("UPDATE blog SET st = 2 WHERE id = $row['id']");

Если избавиться от этого, то будет точно быстрее. И лучше использовать mysqli

[Имя Фамилия]

Spartak (Web-StyleStudio), от ORDER можно избавиться,
но надо в запись добавлять 2 чтобы она больше никак не участвовала в скрипте

[Spartak (Web-StyleStudio)]

User782,

но надо в запись добавлять 2 чтобы она больше никак не участвовала в скрипте

3млн записей это вообще ниочем, если оптимизировать скрипт, то на обработку уйдёт меньше минуты, так что этот статус 2 и нафиг не нужен будет

[Имя Фамилия]

Spartak (Web-StyleStudio), а как вы представляете алгоритм скрипта, который хотя бы за день всё сделает?

[Spartak (Web-StyleStudio)]

User782,
Надо как минимум знать структуру таблицы, тип (MyISAM или innodb) и принцип по которому вы хотите определить дубли. Без этих вводных данных - это гадание на кофейной гуще

[Имя Фамилия]

Spartak (Web-StyleStudio), MyISAM
принцип наверно similar_text

[Spartak (Web-StyleStudio)]

User782,
https://www.php.net/manual/ru/function.similar-text.php
Смотрите пример, даже в нем показан разный результат, если изменить порядок аргументов (сравниваемых строк)

[Spartak (Web-StyleStudio)]

User782,

принцип наверно similar_text

Ну это наверное пальцем в небо...

[Имя Фамилия]

Spartak (Web-StyleStudio), принцип такой, что по порядку берется запись и проверяется со всеми записями, если процент совпадает с установленным, то запись удаляется и так далее.
первая запись пробежала, берется вторая запись и так далее

[Spartak (Web-StyleStudio)]

similar_text

Пример использования similar_text() с заменой аргументов

В этом примере показано, что изменение порядка аргументов string1 и string2 может дать разные результаты.

71% и 42% при сравнении двух строк.
Вас устраивает такой результат?

[Имя Фамилия]

Spartak (Web-StyleStudio), да, меня устраивает любой результат

[Spartak (Web-StyleStudio)]

User782,
Вы проверяли на уникальность столбец title в вашей таблице blog?
Я бы для начала удалил из таблицы 100% дубли title.
Потом бы выполнил запрос и занёс все строки в массив, и дальше работал с этим массивом сравнивая поэтапно строки через similar_text (раз уж вас устраивает её принцип)
Ключ id, значение title

$arr = [];
$result = $mysqli->query("SELECT `id`, `title` FROM `blog`");
while ($row = $result->fetch_assoc()) {
	$arr[$row["id"]] = $row["title"];
}

далее работаем с массивом
находим все ключи (id) значение title у которых similar_text proc > 73 и удаляем из таблицы эти строки
similar_text для array или как оставить логически ...

[Имя Фамилия]

Spartak (Web-StyleStudio), правильно ли сделал?)

$array = array();
$result = mysql_query("SELECT id, title FROM blogs");
while ($row = mysql_fetch_assoc($result)) {
  $array[$row["id"]] = $row["title"];
}

$num = count($array);

for($i=0; $i < $num; $i++) {
	for ($u = $i+1; $u < $num; $u++) {
	    if(isset($array[$i]) && isset($array[$u])) {
			similar_text($array[$i], $array[$u], $prc);
			if ($prc > 73) {mysql_query("DELETE FROM blogs WHERE id = {$array[$row["id"]]}");}
		}
	}
}

[Spartak (Web-StyleStudio)]

User782,

mysql_query("DELETE FROM blogs WHERE id = {$array[$row["id"]]}");

здесь ошибка id = должно быть значение ключа из цикла $u

[Spartak (Web-StyleStudio)]

User782,
И сделайте бекап таблицы на всякий случай

[Spartak (Web-StyleStudio)]

User782,

$num = count($array);

Вот это и далее работа с циклом тоже не верно. У вас ключ (id) максимальное не факт что будет равно количеству значений массива

[Spartak (Web-StyleStudio)]

User782,
Если работать с массивом через for, то тогда как-то так

ini_set('error_reporting', E_ALL);
ini_set('display_errors', 1);

$array = array();
$result = mysql_query("SELECT `id`,`title` FROM `blogs`");
while ($row = mysql_fetch_assoc($result)) {
	$array[] = array("id" => $row["id"], "title" => $row["title"]);
}

$num = count($array);

for($i = 0; $i < $num; $i++) {
	for ($u = $i + 1; $u < $num; $u++) {
		if (isset($array[$i]["title"], $array[$u]["title"])) {
			similar_text($array[$i]["title"], $array[$u]["title"], $prc);
			if ($prc > 73) {
				mysql_query("DELETE FROM `blogs` WHERE `id`='{$array[$u]["id"]}'");
				unset($array[$u]);
			}
		}
	}
}

P/S: для начала запустите скрипт без удаления записей, для проверки

if ($prc > 73) {
	echo "id = {$array[$i]["id"]}; title = 
{$array[$i]["title"]}<br>";
	echo "id = {$array[$u]["id"]}; title = 
{$array[$u]["title"]}<br>";
	unset($array[$u]);
}

[Spartak (Web-StyleStudio)]

User782,
В таблице blog индекс для id - PRIMARY KEY ?

[Имя Фамилия]

Spartak (Web-StyleStudio), да id - PRIMARY KEY
я данный скрипт он только попарно сверяет?

[Spartak (Web-StyleStudio)]

User782,
Нет, сравнение со всеми значениями в массиве

[Имя Фамилия]

спасибо, отпишу как что получится

[Имя Фамилия]

Spartak (Web-StyleStudio), скрипт работает хорошо, но по времени так же, месяц нужен как минимум

[Имя Фамилия]

Akina,

Я бы пошёл по пути разборки записей на токены (слова)

то есть каждому слову нужно присвоить уникальный номер и занести в таблицу?

[Akina]

User782, да, именно, это резко понизит длины подстрок, и, как следствие, ускорит обработку.

[Имя Фамилия]

Akina, и так же использовать similar_text?

[Akina]

User782, поскольку similar_text безразличен к семантике, орфографии, словоформам и пр, и оперирует только символами - да. Но т.к. изменение алфавита приведёт к изменению "похожести" - нет.

similar_text даёт нечто, посчитанное по двум параметрам и измеренное в попугаях, от чего толку, как по мне, ноль. Но если Вам нравится - используйте.

[Имя Фамилия]

Akina, да я хотел просто уточнить, в вашем первом комментарии, вы имели в вижу similar_text или что-то другое?)

Answer 1

[Rsa97]

Считать разом все пары (`id`, `title`) в ассоциативный массив, обработать его, занося в новый массив id уникальных записей, затем порциями, например по сотне id, установить признак уникальности в базе, потом удалить все записи, где этот признак не установлен.
Но всё равно, в худшем случае будет 3 000 000*3 000 000/2 = 4 500 000 000 000 сравнений. Так что, в первую очередь надо ускорять функцию similar_text.

Answer 2

[Виталий Качан]

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