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