Поиск неточных совпадений, поиск с учетом ошибок ввода

Предисловие

Есть у нашей компании своя собственная CRM и периодически в эту систему добавляются данные о неких организациях с точным адресом, и главное что адреса эти по сути уникальны, то есть в системе не должно быть нескольких организаций по одному адресу (специфика, на самом деле могут, но контролируется челфаком*). С недавнего времени в систему был прикручен КЛАДР, но и он не мог быть панацеей, т.к. КЛАДР имеет кучу неточностей, многие нас. пункты остались без номеров домов итд. итп., хотя адреса эти в реальности есть (данные предоставляют сотрудники компании и они достоверны). В общем ввод адреса оставили в свободной форме с подсказкой из КЛАДр. Сразу хочу сказать, что от комбинации полей мы отказались, т.к. многообразие аббревиатур сокращений не сулило ничего хорошего, к тому же вполне позволительным был адрес на подобии («Ололошское ш. 5км», «ТЦ Весельчак У» или даже «Центральный рынок»). И наконец главный враг программиста — челfuck, подразумевающий от неграмотности и опечаток до залипающей клавиатуры и опечаток. Остальное под катом…

Что имеем

Имеем с одной стороны: БД заполненную некими адресами в одном поле с другой спешащего отчитаться в системе сотрудника со всеми вытекающими. Хотелось максимально обезопасить данные от дубликатов и было решено выводить пользователю предупреждение о возможном дублировании записи.

Решение проблемы

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

• Берем исходный текст и удаляем «лишнее»
• Разбиваем слова в адресе на так называемые слоги
• Делаем тоже самое с входными данными
• Проверяем совпадение слогов в процентах
• Делаем дополнительную проверку на номера в адресе, чтобы отбросить, т.к. даже ошибочно напечатанная улица но с другим номером дома или корпуса уже не должна была считаться дубликатом
• Выносим вердикт после сравнения
• Отдаем похожие совпадения, если нашли
• Берем с полки пирожок

Как это устроено

Далее просто код:

function clearAddr($addr) {
	
	$associate = array(
	" " => "", // Заодно и пробелы
	"д." => "",
	"стр." => "",
	"корп." => "",
	"ул." => "",
	"ул." => "",
	"пр." => "",
	"ш." => "",
	"г." => "",
	"пр-т." => "",
	"пр-т" => "",
	"пр-д." => "",
	"пр-д" => "",
	"пл-д." => "",
	"пл-д" => "",
	"пер." => "",
	"пер" => "",
	"микр.р-н" => "",
	"мкрн." => "",
	"мкрн" => "",
	"мкр." => "",
	"пл." => "",
	"пос." => "",
	"ст." => "",
	"с." => "",
	"б-р." => "",
	"б-р" => "",
	"пер-к" => "",
	"пер-к." => "",
	"1-й" => "",
	"2-й" => "",
	"3-й" => "",
	"4-й" => "",
	"5-й" => "",
	"6-й" => "",
	"7-й" => "",
	"8-й" => "",
	"9-й" => "",
	"1-я" => "",
	"2-я" => "",
	"3-я" => "",
	"4-я" => "",
	"5-я" => "",
	"6-я" => "",
	"7-я" => "",
	"8-я" => "",
	"9-я" => ""
	);

	$clrd_addr = strtolower(strtr($addr, $associate));
	
return $clrd_addr;
}

function getNums($search) {
	preg_match_all("/[0-9]*/", $search, $matches);
	$matches = array_diff($matches[0], array("")); // Удаляем пустые значения из $matches
return $matches;
}

function getMatchAdress($addr_string, &$Addr_array) {

	if(!isset($addr_string) || strlen($addr_string) < 1) return false;

	$list = array();
	$nums = getNums($addr_string); // Узнаем какие номера использованы в адресе
	$addr_string = clearAddr(preg_replace("/[0-9]*/", "", $addr_string)); // Удаляем сокращения и номера
	$word_parts = explode("n", chunk_split(trim($addr_string), 2)); // Получаем массив с разбитым адресом по 2 символа
	array_pop($word_parts);

	// Пробегаем список имеющихся адресов
	foreach($Addr_array as $row) {
	
		$word_match = 0;
		$last_pos = 0;
		
		// Чистим попавшийся адрес
		$clr_row = clearAddr($row);
		$row_nums = getNums($row);
		
		// Пробегаемся по т.н. слогам входного адреса
		foreach($word_parts as $syllable) {
		
			$match_in = strpos($clr_row, strtolower(trim($syllable)), $last_pos); // Ищем слева-направо совпавший слог
			
			// Ловим совпадение слога с поправкой на ошибку
			if($match_in > -1 && $match_in < $last_pos + 4) {
				$last_pos = $match_in + strlen(trim($syllable));
				$word_match++;
			}
		
		}
		
		$all_percents = count($word_parts); // Количество частей в исходном слове
		$found_percents = $word_match; // Найдено совпадений подряд
		$match_perc = round($found_percents * 100 / $all_percents); // Считаем совпавший процент
		$max_point = 70; // Устанавливаем порог совпадения
		
		// Сверяем результаты и заполняем список для вывода результатов
		if($match_perc >= $max_point) {
		
			if(!empty($nums)) { // Если в адресе были номера
			
				foreach($nums as $num) {
					if(in_array($num, $row_nums)) $list[] = $row;
				}
			}
			else { // Если номеров небыло
				$list[] = $row;
			}
		}

	}

return $list;
}

Как это выглядит

Что есть в базе:

ул. Зацепа, д.40
ул. Плющиха, д.14
4-й Добрынинский пер., д.1
ул. Зоологическая, д.15
Благовещенский пер., д.6
ул. Б.Серпуховская, д.48
...
...
...
ул. Таганская, д.31/22
ул. Бакунинская, д.23, стр. 41
ул. Садово-Самотечная, д.11
Пр-т Мира, д.39, стр.1
4-й Добрынинский пер., д.4
Рогожский Вал, д.2


Даем на вход: Дорынинсий

На выходе у нас:

Array
(
    [0] => 4-й Добрынинский пер., д.1
    [1] => 4-й Добрынинский пер., д.4 
)

Если бы поисковый запрос выглядел так Дорынинсий д.1, то мы бы видели лишь нулевой ключ.

PROFIT !, спасибо за то что выдержали.

Автор: Yan_Alex