[Из песочницы] Нахождение похожих имен средствами MySQL+PHP02.05.2017 12:48

Не так давно возникла следующая задача:

• Есть в составе информационной системы (ИС) база данных (БД) актеров, музыкантов, DJ-ев, а так же иногда политиков, ученых и других публичных лиц.
• ИС заполнялась любителями и дилетантами, многие из которых затруднялись правильно перевести на русский язык ту или иную фамилию. А иногда случалось и такое, что имя звучало по-русски совсем не так, как писалось на иностранном языке.
• В БД имена заносились в достаточно свободной форме. Порядок слов в имени часто менялся (особенно для азиатских имен), дополнительно могли указываться (или не указываться) прозвища и псевдонимы.
• Бывали и просто описки — замены, пропуски или добавления букв. Иногда часть букв по какой-то причине писалась латиницей.
• Акцидентных символов, к счастью, не было.
• Имена хранились в MyISAM таблицах MySQL в кодировке UTF-8.
• Общее число имен в БД составляло примерно 138,5 тысяч.

Это то, что «дано». А «требовалось» следующее:

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

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

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

• Фонетическое кодирование (в частности, «Русский Метафон» Петра Каньковского и его модификации[1]).
• Мера схожести, основанная на дистанциях редактирования Левенштейна[2].
• Выделение общих форм[3].
• Алгоритм Джаро-Винклера[4].
• N-граммный анализ.[5].

По здравому размышлению принято было следующее:

Вот приходит в наш родной паспортный стол капитан третьего ранга Jeannette Devereaux[6] и представляется по уставу четко и громко. И паспортистка может на слух записать ее фамилию и «Диверю» и «Девирю» и даже «Дивиру». Да еще удвоенные согласные в имени пропустить. Все эти «слуховые галлюцинации» прекрасно отслеживаются алгоритмами нечеткого поиска с фонетическим кодированием.

Но вот горе-«переводчик», не знающий специфики французского языка (но знакомый с английским языком), переписывая данные из военного билета, запросто может написать «Жэннетт Деверокс». А особо одаренные могут указать позывной или записать фамилию впереди имени.

Или даже многие англоязычные «переводчики» не знают, что имя «Ralph Fiennes» следует читать не «Ральф», а «Рэйф Файнс».

Так что, фонетическое кодирование здесь не подходит, потому что в данном случае ошибочные имена пишутся не «так, как слышаЦЦа», а «так, как видRTCR».

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

Так, может быть, использовать расстояние редактирования?

Приходится в таком случае разбивать имена на отдельные слова и сравнивать уже каждое из них. А это существенно усложняет (и замедляет) работу алгоритма, даже если предварительно привести эти отдельные слова к их фонетическому индексу. Так же дополнительную сложность привносит то, что количество слов в имени является непостоянной величиной. С учетом возможных пропусков и перестановок слов уже сложно даже представить трудоемкость этого процесса.

Другие методы

Опять таки, при перемене словами мест, релевантность резко уменьшается.

Вычисление дистанции Джаро-Винклера работает существенно быстрее. Но, к сожалению, так же не является устойчивым к перемене слов местами.

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

Написание и тестирование скрипта проводилось в домашних условиях на компьютере восьмилетней давности еще с одноядерным Intel Pentium D 925 на материнской плате ASUS P5B-E и с обычными заезженными хардами Seagate примерно того же возраста.

Скрипт этот работал, что называется, в лоб. Считывал БД, каждое имя, предварительно нормализованное, разбивал на уникальные триграммы и подсчитывал число их вхождений в каждое из предыдущих имен (т.е., находящихся в БД ранее испытуемого). Если результат деления удвоенного числа совпадений на сумму уникальных триграмм в каждом из этих имен превышал некоторый порог (например, 0,75 или 0,8), то это фиксировалось в файле.

Нормализация имени заключалась в следующем:

• Английские буквы и некоторые цифры заменялись сходными по написанию русскими буквами.
• Все строчные буквы заменялись прописными.
• Буква «Ё» заменялась на «Е», а «Ъ» на «Ь».
• Все прочие буквы, знаки, непечатные символы и их последовательности заменялись двумя пробелами.
• Имя обрамлялось двойными пробелами.

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

В нормализованном имени выделялись всевозможные уникальные триграммы — сочетания из расположенных подряд трех символов (включая пробелы).

Затем для двух имен вычислялся следующий коэффициент релевантности: удвоенное число общих триграмм делилось на сумму уникальных триграмм в каждом имени.

Требование к уникальности триграмм озвучено неспроста. С одной стороны, подсчет общего количества триграмм в именах без учета их уникальности позволит уверенно различать такие имена, как «Джон Смит» и «Джон Джон Смит». А учет только уникальных триграмм приведет к тому, что эти имена будут считаться идентичными.

С другой стороны, во-первых, потребность в различении подобных имен будет возникать не часто. А, во-вторых, подсчет релевантности по всем триграммам, а не только по уникальным, значительно усложнит эту процедуру. Потому что вместо удвоенного числа общих триграмм придется считать сумму вхождений триграмм из первого имени во второе и триграмм из второго имени в первое. Т.е., грубо это увеличит временные расходы на вычисление релевантности примерно в 2 раза. Ну и, в-третьих, это не позволит применить к процедуре вычисления релевантности некоторые оптимизации, о которых пойдет речь далее.

Итак, лобовой алгоритм был написан и опробован на первых нескольких тысячах имен. Результат был удручающим. Как и следовало ожидать, время поиска совпадений по всему массиву имен имело ярко выраженную квадратичную зависимость от его размера. Прогноз тренда на обработку всего массива из 130–140 тысяч имен составил около двух лет. Многовато будет!

Зато появилась начальная оценка производительности алгоритма.

1. Начальная выборка из БД должна выдавать не весь массив имен, а только те, которые уже хоть чуть сходны с тестируемым, для уменьшения числа прочих операций. Анализ времени выполнения различных участков кода показал, что запросы к БД и являются «бутылочным горлышком». Необходимо было уменьшать, как время выполнения каждого запроса, так и число выдаваемых имен-претендентов в каждой выборке.
2. Операции сравнения и копирования подстроки, проводимые со строками в мультибайтной кодировке UTF-8, по производительности в несколько раз уступают тем же операциям со строками в однобайтной кодировке.
3. Не обязательно производить точное вычисление коэффициента релевантности, если доля общих триграмм мала. В этом случае появляется возможность прервать этот процесс, как только станет ясно. что даже если все остальные триграммы окажутся общими, это не приведет к превышению требуемого граничного значения.
4. Прочее по мелочам.

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

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

Ну и, самое главное, обработанные имена индексировались триграммным индексом. Т.е. в дополнительной таблице перечислялись все уникальные триграммы, присутствующие в нормализованном имени. При этом, сами триграммы, чтобы не хранить их в «медленной» кодировке UTF-8, хранились в виде целочисленного хеша — трем младшим байтам числа соответствовали числовые значения соответствующих символов в кодировке Windows-1251.

Но при этом был допущен совершенно неэффективный, как было выяснено в дальнейшем, подход — для каждой триграммы из проверяемого имени делалась своя собственная выборка имен-претендентов, которые потом объединялись в единый массив. При этом каждое имя в этом массиве сопровождалось счетчиком — в скольких выборках оно встретилось. Предполагалось, что это даст некоторый выигрыш в вычислении релевантности за счет того, что не надо будет затем раскладывать эти имена на триграммы — достаточно было использовать этот счетчик, чтобы сразу вычислить релевантность.

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

Применение триграммного индекса для начальной выборки сократило прогноз результирующего времени с двух лет до менее чем трех месяцев. Использование в его качестве числовых значений вместо подстрок в формате UTF-8 позволило дополнительно сократить время общей обработки еще на 10–12%. Но все равно 2,5 месяца непрерывной работы представлялись слишком большим сроком. Тонким местом оставалась начальная выборка похожих имен.

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

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

Далее была изменена процедура вычисления релевантности. На основании нижней границы релевантности и числа уникальных триграмм в именах вычислялось максимально допустимое число «промахов» — число триграмм в имени-претенденте, не входящих в проверяемое имя. Затем все триграммы имени-претендента проверялись на вхождение в проверяемое имя. Как только число «промахов» превышало максимально допустимое, сравнение прекращалось. Это позволило сократить прогноз времени еще на несколько процентов. Но до промышленных значений было все равно очень далеко.

Найти подход помог простой просмотр найденных пар сходных имен. Практически во всех таких парах находились общие подпоследовательности длиной 6–7 символов (включая окаймляющие двойные пробелы). Путем нехитрых рассуждений (которые здесь не приводятся ввиду их нестрогости) можно прийти к выводу, что для достижения релевантности более 0,75, нормализованные имена должны иметь общую подстроку из 5 символов или длиннее.

Таким образом, от индексации предварительного поиска триграммами переходим к индексации пентаграммами (5-символьными подстроками). Чтобы уместить хеш пентаграммы в целочисленной переменной, имеющей в 32-разрядной версии PHP размер 32 бита, каждый символ представляем в виде 5-бит, благо символов всего 31 (без «Ё» и «Ъ») и пробел.

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

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

Это несколько спорное усовершенствование. При задании граничного значения релевантности 0,75 оно не приводит к ускорению, а, наоборот, приводит к потере производительности на 3% за счет увеличения сложности выборки. Но если задать границу релевантности 0,8, то получаем уже 3% выигрыша.

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

В принципе, можно было бы осуществлять первоначальный поиск даже гексаграммами (индексными подстроками из 6 символов). Это давало ускорение еще в несколько раз. Но возникло обоснованное опасение, что могут отсеяться много пар азиатских коротких имен (и не только их). Да и смысла особого нет, т.к. последующий ручной анализ полученных пар (а их набралось более 11 тысяч) займет в любом случае несколько месяцев.

Зато индексация гексаграммами вполне пригодна для подсказок вида «Возможно, Вы имели в виду …», когда излишняя параноидность не требуется, а наоборот, следует находить минимальное количество наиболее подходящих имен.

В принципе, при работе с длинными именами можно использовать индексы семисимвольных подстрок. А чтобы поместить их в 32-битные переменные произвести предварительное фонетическое кодирование с целью сокращения числа символов до 15 и пробела. Но такая задача в тот момент не стояла.

К сожалению, вскоре после написания скрипта, сайт был заблокирован по обвинению в нарушении авторских прав. Хотя вскоре он переехал на другой адрес, из-за навалившихся проблем стало не до поиска дублирующих имен.

Фрагменты алгоритма:

CREATE TABLE IF NOT EXISTS `prs_persons` (
  `id` int(10) unsigned NOT NULL,
  `name_ru` varchar(255) collate utf8_unicode_ci default NULL, //Переведенное на русский язык имя
//Прочие поля
  PRIMARY KEY  (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;

CREATE TABLE IF NOT EXISTS `prs_normal` (
  `id` int(10) unsigned NOT NULL,
  `name` varchar(255) collate utf8_unicode_ci default NULL, //Нормализованное имя
  `num` int(2) unsigned NOT NULL, //Число уникальных триграмм в нормализованном имени
  PRIMARY KEY  (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;

CREATE TABLE IF NOT EXISTS `prs_5gramms` (
  `code` int(10) unsigned NOT NULL, //Числовой код пентаграммы
  `id` int(10) unsigned NOT NULL, //Идентификатор имени, в котором присутствует
  KEY `code` (`code`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;

	$opt_debug_show_sql = 0;
	$opt_debug_mode = 0;
	$opt_table_prefix = "prs";

	define('MIN_RELEVANT', 0.8);
	define('SITE_PREFIX', "…"); //Здесь храним префикс страницы персоны на сайте.

//Максимально допустимое соотношение количества уникальных триграмм,
//чтобы имена еще могли быть схожими.
	$len_ratio = MIN_RELEVANT / (2 - MIN_RELEVANT);

	$suitablesin = iconv("Windows-1251", "UTF-8",
"АаБбВвГгДдЕеЁёЖжЗзИиЙйКкЛлМмНнОоПпРрСсТтУуФфХхЦцЧчШшЩщЬъЫыЪьЭэЮюЯяAaBbCcEegHKkMmnOoPprTuXxYy03468");
	$suitablesout =
"ААББВВГГДДЕЕЕЕЖЖЗЗИИЙЙККЛЛММННООППРРССТТУУФФХХЦЦЧЧШШЩЩЬЬЫЫЬЬЭЭЮЮЯЯААВЬССЕЕДНККМТНООРРГТИХХУУОЗЧБВ";

	$charcode = array( ' ' => 0, 'А' => 1, 'Б' => 2, 'В' => 3, 'Г' => 4, 'Д' => 5, 'Е' => 6, 'Ж' => 7,
		'З' => 8, 'И' => 9, 'Й' => 10, 'К' => 11, 'Л' => 12, 'М' => 13, 'Н' => 14, 'О' => 15,
		'П' => 16, 'Р' => 17, 'С' => 18, 'Т' => 19, 'У' => 20, 'Ф' => 21, 'Х' => 22, 'Ц' => 23,
		'Ч' => 24, 'Ш' => 25, 'Щ' => 26, 'Ь' => 27, 'Ы' => 28, 'Э' => 29, 'Ю' => 30, 'Я' => 31); //Пятибитные коды символов.

	set_time_limit(0); //Время выполнения скрипта неограниченно.

	function message_die($errno, $error, $file, $line)
	{
		if ($errno)
		{
			print "
Error " . $errno . " " . $file . "(" . $line . "): " . $error;
			die();
		}
	};

	$fout = fopen("…", "w"); //Открываем файл для записи похожих пар.

//Здесь должны находиться подготовка списка имен к анализу и основной цикл сравнения.

	fclose($fout);

//Для каждого еще непроанализированного имени:

	$id = …; $name_ru = …; //Считываем ID персоны и имя в кодировке UTF-8.

	$rusn = "  "; //Нормализованное имя начинается двумя пробелами.
	$ischar = FALSE;

	for ($j = 0; $j < mb_strlen($name_ru, "UTF-8"); $j++)
	{
		$char = mb_substr($name_ru, $j, 1, "UTF-8");

		if (($pos = mb_strpos($suitablesin, $char, 0, "UTF-8")) === FALSE)
		{
			if ($ischar)
			{
			//Все недопустимые символы заменяем двойными пробелами.
				$rusn .= "  ";
				$ischar = FALSE;
			}
		}
		else
		{
		//Прочие перекодируем в Windows-1251 с учетом возможного транслита.
			$rusn .= $suitablesout{$pos};
			$ischar = TRUE;
		}
	}

	if ($ischar) $rusn .= "  "; //Добавляем два пробела в конце.

	if (strlen($rusn) < 5) continue; // Имена из одних пробелов не рассматриваются.

	$norm = iconv("Windows-1251", "UTF-8", $rusn); //Перекодируем в UTF-8 для записи в БД.

//Заносим в массив уникальные пентаграммы нормализованного имени:

	$subgramms = array();

//Нормализованное имя начинается с двух пробелов, имеющих код 0.
//Поэтому их просто не кодируем, а начинаем вычисление хеша пентаграммы с первой буквы.

	$code = ($charcode[$rusn{2}] << 5) | $charcode[$rusn{3}];

	for ($j = 4; $j < strlen($rusn); $j++)
	{
		$code = (($code << 5) | $charcode[$rusn{$j}]) & 0x1FFFFFF;

		$subgramms[$code] = $code; //Записываем хеш пентаграммы в массив.
	}

//Составляем список уникальных триграмм в нормализованном имени и подсчитываем их количество.

	$trigramms = array();

	for ($k = 0; $k < strlen($rusn) - 2; $k++)
		$trigramms[$trigramm = substr($rusn, $k, 3)] = $trigramm;

	$n = count($trigramms);

//Вычисляем граничные значения числа уникальных триграмм в сходных именах:

	$nmin = ceil($n * $len_ratio);
	$nmax = floor($n / $len_ratio);

//Считываем из БД список кандидатов на сходные имена.

	$similars = fquery("SELECT n.id AS id, n.name AS name, n.num AS num FROM prs_5gramms AS g, prs_normal AS n WHERE g.code IN (^N) AND n.id = g.id AND 

n.num >= ^N AND n.num <= ^N", $subgramms, $nmin, $nmax);

//Записываем в БД нормализованное имя и количество уникальных триграмм.

	fquery("INSERT INTO prs_normal (id, name, num) VALUES (^N, ^S, ^N)", $id, $norm, $n);

//Записываем в БД список пентаграмм этого нормализованного имени.

	foreach ($subgramms as $key=>$code)
		fquery("INSERT INTO prs_5gramms (code, id) VALUES (^N, ^N)", $code, $id);

	unset($subgramms); //И освобождаем его.

//Для каждого имени-кандидата:

	for ($i = 0; $i < @mysql_num_rows($similars); $i++)
	{
		$similar = @mysql_fetch_assoc($similars) OR
			message_die(@mysql_errno(), @mysql_error(), __FILE__, __LINE__);

		$name = iconv("UTF-8", "Windows-1251", $similar['name']);
		$simid = $similar['id'];
		$m = $similar['num']; //Количество уникальных триграмм.
		$nm = 0; //Число общих триграмм.
		$done = TRUE;
		$miss = floor($m - MIN_RELEVANT * ($n + $m) / 2); //Число допустимых "промахов".

		for ($k = 0; ($k < strlen($name) - 2) & ($miss >= 0); $k++)
		{
			if (strpos($name, $trigramm = substr($name, $k, 3), 0) == $k)
			{
			//Если триграмма встретилась впервые (уникальная):
				if (isset($trigramms[$trigramm])) $nm++; //Увеличиваем счетчик общих.
				else $miss--; //Иначе уменьшаем оставшееся число допустимых промахов.
			}
		}

		if ($miss >= 0)
		//Если число промахов не превышено, выводим в файл информацию о
		//схожей паре имен и величину релевантности.
			fwrite($fout, SITE_PREFIX . $id ."\t" . $rusn ."\t" . SITE_PREFIX . $key . "\t" . $name . "\t" . ($nm + $nm) / ($m + $n) . "\r\n");
	}

	@mysql_free_result($similars) OR message_die(@mysql_errno(), @mysql_error(), __FILE__, __LINE__);

	unset($trigramms); //Освобождаем список триграмм для повторного использования.

	fclose($fout); //Закрываем файл со списком схожих пар.

// Syntax: fquery($query_template_text, $argument's_1_value, $argument's_2_value, ...)
// Special characters for a query template:
// ^@TableName - indicates that the combination ^@ is to be replaced with table prefix
// ^N - numeric parameter(s) (is not to be quoted), separated by comma if is array
// ^S - string parameter(s) (is to be quoted), separated by comma if is array
// ^0 - "NULL" or "NOT NULL"

// (c) Grigoryev Andrey aka GrAnd aka Pochemuk
// Thanks to Kamnev Artjom (Kamnium), Mesilov Maxim (Severus) for idea
// http://life.screenshots.ru

// When query successed returns Recordset for SELECT or True for others.
// When error occurs returns False.

function fquery()
{
	global $opt_debug_mode;
	global $opt_debug_show_sql;
	global $opt_table_prefix; // getting prefix from the site's options

	if (is_array(func_get_arg(0))) $args = func_get_arg(0);
	else $args = func_get_args();

	$qtext = $args[0]; // the first argument is always query template text
	if (empty($qtext)) return false; // Hmm, nothing to do!

	$qtext = str_replace("^@", ($opt_table_prefix == "") ? "" : ($opt_table_prefix . '_'), $qtext); // replacing with table prefixes

	$i = 0; $curArg = 1;

	$query = "";

	while ($i < strlen($qtext)) // strlen is always up-to-date, even if special chars are replaced
	{
		if ($qtext{$i} == '^')
		{
			if ($curArg >= count($args)) return false; // too many parameters in the query template!

			$i++;

			switch ($qtext{$i})
			{
				case 'N':
				{
					if (is_null($args[$curArg]))
					{
						$query .= "NULL";
						continue;
					}

					if (is_array($args[$curArg])) $query .= implode(", ", $args[$curArg]);
					else $query .= $args[$curArg];

					break;
				}
				case 'S':
				{
					if (is_null($args[$curArg]))
					{
						$query .= "NULL";
						continue;
					}

					if (is_array($args[$curArg])) $query .= "'" . implode("', '", $args[$curArg]) . "'";
					else $query .= "'" . $args[$curArg] . "'";

					break;
				}
				case '0':
				{
  					if (is_null($args[$curArg])) return false; // incorrect parameter, nulls are not allowed!

					$args[$curArg] = strtoupper($args[$curArg]);

					if (($args[$curArg] != "NULL") && ($args[$curArg] != "NOT NULL")) return false; // incorrect parameter, "NULL" or 

"NOT NULL" only!

					$query .= $args[$curArg];

					break;
				}
				default: $query .= $qtext{$i};
			}

			$i++; $curArg++;
		}
		else $query .= $qtext{$i++};
	}

	if ($opt_debug_show_sql == 1) print('
Query string: "' . $query . '"
' . "\r\n");

	$ResultData = mysql_query($query);

	if (mysql_errno() <> 0)
	{
		if ($opt_debug_mode == 1)
		{
			print('
MySQL error: #' . mysql_errno() . ': ' . mysql_error() . '
');
			print('Query string: ' . $query . '
');
		}
	}

	return($ResultData);
} // End of fquery