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

Предисловие



Есть у нашей компании своя собственная 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 !, спасибо за то что выдержали.
Share post

Comments 49

    0
    function clearAddr($addr) { } — не проще было-бы использовать регулярные выражения?
      0
      мне казалось что проще массив собрать чем писать под это все регулярку
        0
        хотя я сейчас явно вижу свою опрометчивость )) надо было реально все водномерный массив загнать и заменить прег релайсом на пустоту, ну я писал 2 года назад в некоторой спешке )) стугодумил )))
          0
          а если будет не 9-я, а 10-я? =) я уже не говорю про те-же опечатки.
          А вообще нет смысла городить свои велосипеды. Есть готовые алгоритмы:
            0
              0
              Плохо работают расстояния Левенштейна. Я добился нормального качества «нечеткого сравнения» только путем комбинации двух алгоритмов — по Левенштейну и процент совпадения начальных подстрок. То есть, «Дорынинская» и «Добрынинская» по Левеншнейну совпадут сильно, а по подстрокам — только первые два символа из 11 (букв в слове). Пример с добрынинской вроде говорит против моего метода, но в реале начало слова важнее общего числа совпадений букв, например «Егорьевская» и «Егеревская» — очень разные улицы, но по Левенштейну будут сильно похожи.

              В алгоритме Yan_Alex мне понравилось сравнение по двойкам букв — это такой марковский подход, работает почти всегда хорошо. Только надо справочник адресов в базе сразу обработать — разбить на такие марковские цепочки, чтобы поиск быстро происходил.
                0
                Ну если есть необходимость подобных сравнений, может имеет смысл сравнивать не по парам букв, и именно по слогам.
                  0
                  тоесть предлагаете писать лингвистический парсер? и сколько это займет по времени и чем обоснован такой подход?
                    0
                    Это обоснованно более высокой точность определения похожих слов. Я не вижу больших проблем в разбиении слов на слоги. Нужно всего-лишь гласные и согласные. Приведенный код в этом случае увеличится на пару строк. По времени:

                    <?php
                    $word = 'никотинамидадениндинуклеотидфосфатгидрин';
                    preg_match_all('#(([бвгджзйклмнпрстфхцчшщъь]{1,}|)[аеёиоуыэюя]{1,})#u',$word,$syllable);
                    var_dump($syllable[1]);
                      0
                      АБ РИ КОС — как алкоритм поймет что первый слог кончается на согалсную а второй на гласную? )
                        0
                        если я не ошибаюсь ваш код выдаст АБ РИК ОС
                          0
                          этот код выдаст А БРИ КО С. Но это было написанно за две минуты на коленке для примера. При необходимости все это можно доработать, не сильно усложняя код…
                            0
                            Да я что то неправильно заметил, но суть в том что совпадение по слогам уменьшит количество совпавших процентов т.к. слог может быть из 4х символов. надо много додумывать относительно этого.
                              0
                              Когда слово разбито на слоги, можно эти слоги и сравнивать, те-же расстоянием Хемминга и|или Левенштейна. И допустим суммировать совпадения для слогов в слове. По моему это сведёт ошибки к минимому, и будет точнее нежели пары букв…
                                0
                                да но ошибка в слоге откажет в совпадении слога, а если ошибок 3 в 8 мибуквенном слове то это -3 слога из области совпадения, а при сравнении букв мы имеем еще 5 символов для сравнения, когда 3 слога это уже минимум максимум 4 символа, при длинне слога в 2 буквы. Незнаю правда как эжто будет работать в комбине с другими алгоритмами. Фактически данный алгоритм уже работает 2 года — пока все впорядке, вроде )))
                                  0
                                  Дык надо не сами слоги сравнивать, а их похожесть. Если в каждом слоге из трех букв по две ошибки, это уже другое слово получится =)
                                    0
                                    )))) ну так то да, но пока я сам вводил все это в систему я был в шоке от разнообразных вариаций на тему коверкай название улицы )))
                                      0
                                      У себя я сильно не заморачивался, просто ввел select, а при выборе улицы аяксом подгружается список домов. Все адреса изначально есть в базе. Если нет, то отдельный интерфейс по добавлению (это менее удобно для операторов, но зато никаких ошибок =). Еще можно рассмотреть вариант когда в поле input человек вводит или начинает вводить название, и при этом в процесе написания вываливается список релевантных записей. И выбирать можно ТОЛЬКО из предложенного списка. Так кстати реализован выбор города в поиске людей во вконтакте. Единственный минус ИМХО — в процессе написания больно много запросов к серверу.
                                        0
                                        я сейчас точно так же из кладра показываю инфу, но я не мог оставить это как единственно возможный вариант ибо

                                        «к тому же вполне позволительным был адрес на подобии («Ололошское ш. 5км», «ТЦ Весельчак У» или даже «Центральный рынок»)»
                                          0
                                          чего КЛАДР предложить мне неможет, нюансы в них всегда вся соль.
                              0
                              Он не выдает «С» в конце:

                              array(3) {
                                [0]=>
                                string(2) "а"
                                [1]=>
                                string(6) "бри"
                                [2]=>
                                string(4) "ко"
                              }
                              
                                0
                                потому что маска на гласную кончается, то есть там подразумевается что первая согласная либо вообще ничего и затем одна гласная, а ее и нет.
                                  0
                                  Это очевидно из регулярного выражения, я лишь указал на баг. И да, в общем случае разбиение на слоги должно быть сложнее, как мне кажется. Кто знает хороший алгоритм для русского языка?
                                    0
                                    Алгоритм явно сложнее, я уверен есть библиотеки для работы с языками, нодо поискать. Но юзать библиотекую в столь маленьком скрипте при его хорошей работе невижу смысла.
                            0
                            Ой блин я еще не проснулся извиняюсь )
                              0
                              Хотя нет я прав, мне казалось неправильно по слогам написал ))) Деление слова на слоги (перенос слова): аб-ри-кос
                      0
                      Спасибо, «Егорьевская» и «Егеревская» я расчитывал что такого рода исключения уже возлагают ответственность на юзера, хотя есь выод, исакть в базе улицу сначала с точно таким же адресом и если таковой нет то искать похожие, делов то доработать. А по поводу первых букв, то если даже написать орынинская то при превышении порога мы все равно попадем куда надо. Спасибо за комент.
                    0
                    Я не интересовался чужими алгоритмами, хотел реализовать сам. + у нас нету 10-й парковой их там уже некуда городить ))
                      0
                      Готовый код может быь в студию? А то у мен яощющение что в моем коде разберется и ребенок, не говоря о том, что тут ненужны знаничя в математике.
                0
                Спасибо.
                  0
                  Суффиксные деревья луше строить, будет быстро работать. Ваш алгоритм удобен для коротких строк.
                    0
                    А он и был реализован для коротких строк, адрес из нас пункта и номера строения скорее будет коротким, чем длинным, хотя у меня предположение что и с длинными строками все будет отлично работать.
                      0
                      Если знаете хорошую статью про суффиксные деревья я бы почитал
                        0
                        potapov.com.ua/library/31/ — это не то?
                          0
                          О да вот это крутая штука, пасиба. Но опять же не спасет если в корне слова допущена ошибка, если я не ошибаюсь
                            0
                            Ну да, но у стеммера немного другие задачи =)
                            Возможно актуально использовать в связке с другими алгоритмами… Тут уже исходя из задачи…
                              0
                              Тру
                                0
                                Могу написать про суффиксные деревья на java или clojure, php понимаю, но не люблю. Просто я думал, что про них все знают, есть понятие longest common extension которое позволяет делать поиск с заданным числом ошибок, есть несколько алгоритмов, я использовал для анализа рнк и днк последовательностей.
                                  0
                                  А можно про сам алгоритм, без привязки к языкам?) Раньше просто не приходилось сталкиваться, не очень пока в нем разобрался…
                                    0
                                    Строится суффиксное дерево для строки и подстроки, оно обходится за линейное время, поэтому можно сравнить в цикле элементы дерева с простым счетчиком разности элементов. Если же обрабатывать как цикл в цикле, как и в статье — это квадратная, а в более сложных задачах кубическая зависимость.
                                      0
                                      Не не не пишите ка статью Пипец как интересно!
                                    0
                                    Я не тру программист ). ОБЯЗАТЕЛЬНО напишите ппц как интересно! кстати я помоему ранее видел статья про анализ ДНК на хабре, может даже ваши.
                                      0
                                      не, не мои, в хабрапоиске «суффиксные деревья» есть пяток нужных статей, до меня уже написали:-)
                                        0
                                        Поищю, спасибо )
                        0
                        Дружише, спасибо тебе за алгоритм и статью! Переписал твой код на Python для поиска адреса(ов) по «непричесанной» базе из 8000+ адресов

                        Only users with full accounts can post comments. Log in, please.