Yan_Alex 29 мар 2012 в 05:46

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

4 мин

16K

PHP * Веб-разработка * Клиентская оптимизация *

Из песочницы

+16

Комментарии 49

OdaN 29 мар 2012 в 06:00

function clearAddr($addr) { } — не проще было-бы использовать регулярные выражения?

Yan_Alex 29 мар 2012 в 06:02

мне казалось что проще массив собрать чем писать под это все регулярку

Yan_Alex 29 мар 2012 в 06:04

хотя я сейчас явно вижу свою опрометчивость )) надо было реально все водномерный массив загнать и заменить прег релайсом на пустоту, ну я писал 2 года назад в некоторой спешке )) стугодумил )))

OdaN 29 мар 2012 в 06:08

а если будет не 9-я, а 10-я? =) я уже не говорю про те-же опечатки.
А вообще нет смысла городить свои велосипеды. Есть готовые алгоритмы:

OdaN 29 мар 2012 в 06:12

И еще

sergeypid 29 мар 2012 в 06:27

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

В алгоритме Yan_Alex мне понравилось сравнение по двойкам букв — это такой марковский подход, работает почти всегда хорошо. Только надо справочник адресов в базе сразу обработать — разбить на такие марковские цепочки, чтобы поиск быстро происходил.

OdaN 29 мар 2012 в 06:30

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

Yan_Alex 29 мар 2012 в 06:37

тоесть предлагаете писать лингвистический парсер? и сколько это займет по времени и чем обоснован такой подход?

OdaN 29 мар 2012 в 07:16

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

<?php

$word = 'никотинамидадениндинуклеотидфосфатгидрин';

preg_match_all('#(([бвгджзйклмнпрстфхцчшщъь]{1,}|)[аеёиоуыэюя]{1,})#u',$word,$syllable);

var_dump($syllable[1]);

Yan_Alex 29 мар 2012 в 07:22

АБ РИ КОС — как алкоритм поймет что первый слог кончается на согалсную а второй на гласную? )

Yan_Alex 29 мар 2012 в 07:23

если я не ошибаюсь ваш код выдаст АБ РИК ОС

OdaN 29 мар 2012 в 07:26

этот код выдаст А БРИ КО С. Но это было написанно за две минуты на коленке для примера. При необходимости все это можно доработать, не сильно усложняя код…

Yan_Alex 29 мар 2012 в 07:31

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

OdaN 29 мар 2012 в 07:36

Когда слово разбито на слоги, можно эти слоги и сравнивать, те-же расстоянием Хемминга и|или Левенштейна. И допустим суммировать совпадения для слогов в слове. По моему это сведёт ошибки к минимому, и будет точнее нежели пары букв…

Yan_Alex 29 мар 2012 в 07:42

да но ошибка в слоге откажет в совпадении слога, а если ошибок 3 в 8 мибуквенном слове то это -3 слога из области совпадения, а при сравнении букв мы имеем еще 5 символов для сравнения, когда 3 слога это уже минимум максимум 4 символа, при длинне слога в 2 буквы. Незнаю правда как эжто будет работать в комбине с другими алгоритмами. Фактически данный алгоритм уже работает 2 года — пока все впорядке, вроде )))

OdaN 29 мар 2012 в 07:44

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

Yan_Alex 29 мар 2012 в 10:28

)))) ну так то да, но пока я сам вводил все это в систему я был в шоке от разнообразных вариаций на тему коверкай название улицы )))

OdaN 29 мар 2012 в 10:34

У себя я сильно не заморачивался, просто ввел select, а при выборе улицы аяксом подгружается список домов. Все адреса изначально есть в базе. Если нет, то отдельный интерфейс по добавлению (это менее удобно для операторов, но зато никаких ошибок =). Еще можно рассмотреть вариант когда в поле input человек вводит или начинает вводить название, и при этом в процесе написания вываливается список релевантных записей. И выбирать можно ТОЛЬКО из предложенного списка. Так кстати реализован выбор города в поиске людей во вконтакте. Единственный минус ИМХО — в процессе написания больно много запросов к серверу.

Yan_Alex 29 мар 2012 в 10:40

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

«к тому же вполне позволительным был адрес на подобии («Ололошское ш. 5км», «ТЦ Весельчак У» или даже «Центральный рынок»)»

Yan_Alex 29 мар 2012 в 10:41

чего КЛАДР предложить мне неможет, нюансы в них всегда вся соль.

guyfawkes 29 мар 2012 в 11:15

Он не выдает «С» в конце:

array(3) {
  [0]=>
  string(2) "а"
  [1]=>
  string(6) "бри"
  [2]=>
  string(4) "ко"
}

Yan_Alex 29 мар 2012 в 11:20

потому что маска на гласную кончается, то есть там подразумевается что первая согласная либо вообще ничего и затем одна гласная, а ее и нет.

guyfawkes 29 мар 2012 в 11:57

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

Yan_Alex 29 мар 2012 в 12:02

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

Yan_Alex 29 мар 2012 в 07:23

Ой блин я еще не проснулся извиняюсь )

Yan_Alex 29 мар 2012 в 07:24

Хотя нет я прав, мне казалось неправильно по слогам написал ))) Деление слова на слоги (перенос слова): аб-ри-кос

Yan_Alex 29 мар 2012 в 06:33

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

Yan_Alex 29 мар 2012 в 06:16

Я не интересовался чужими алгоритмами, хотел реализовать сам. + у нас нету 10-й парковой их там уже некуда городить ))

Yan_Alex 29 мар 2012 в 06:18

Готовый код может быь в студию? А то у мен яощющение что в моем коде разберется и ребенок, не говоря о том, что тут ненужны знаничя в математике.

OdaN 29 мар 2012 в 06:28

php.net/manual/ru/function.gmp-hamdist.php
ru.wikibooks.org/wiki/Расстояние_Левенштейна

Yan_Alex 29 мар 2012 в 06:34

спасибо большое

OdaN 29 мар 2012 в 07:30

Кстати есть интересные плюшки у MySQL:
project.net.ru/mysql/article3/gl6_8.html

К сожалению не знаю как там это реализованно…

Yan_Alex 29 мар 2012 в 07:33

По поводу поиска MYSQL напишу отдельнуюж статью как я обошелся без Фултекста при неточном поиске в базе данных )

DemonH 29 мар 2012 в 06:08

Спасибо.

Zeldan 29 мар 2012 в 06:34

Суффиксные деревья луше строить, будет быстро работать. Ваш алгоритм удобен для коротких строк.

Yan_Alex 29 мар 2012 в 06:36

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

Yan_Alex 29 мар 2012 в 06:41

Если знаете хорошую статью про суффиксные деревья я бы почитал

OdaN 29 мар 2012 в 07:19

potapov.com.ua/library/31/ — это не то?

Yan_Alex 29 мар 2012 в 07:26

О да вот это крутая штука, пасиба. Но опять же не спасет если в корне слова допущена ошибка, если я не ошибаюсь

OdaN 29 мар 2012 в 07:32

Ну да, но у стеммера немного другие задачи =)
Возможно актуально использовать в связке с другими алгоритмами… Тут уже исходя из задачи…

Yan_Alex 29 мар 2012 в 07:33

Тру

Zeldan 29 мар 2012 в 07:45

Могу написать про суффиксные деревья на java или clojure, php понимаю, но не люблю. Просто я думал, что про них все знают, есть понятие longest common extension которое позволяет делать поиск с заданным числом ошибок, есть несколько алгоритмов, я использовал для анализа рнк и днк последовательностей.

OdaN 29 мар 2012 в 07:48

А можно про сам алгоритм, без привязки к языкам?) Раньше просто не приходилось сталкиваться, не очень пока в нем разобрался…

Zeldan 29 мар 2012 в 07:59

Строится суффиксное дерево для строки и подстроки, оно обходится за линейное время, поэтому можно сравнить в цикле элементы дерева с простым счетчиком разности элементов. Если же обрабатывать как цикл в цикле, как и в статье — это квадратная, а в более сложных задачах кубическая зависимость.