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

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

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

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

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