fuzzy search

[Алексей Данченков]

Приветствую благородное собрание.

Прошу больно не пинать, опыта ноль, а работу делать надо.

Имеется база postgres (~100К записей) ФИО клиентов, со смешанными вариантами написания фамилий - на английском (с разными транскрипциями, вроде "Gluschenkov" и "Glushenkov") и русском.
Посоветуйте алгоритм поиска ФИО похожих на заданную (с целью поиска возможных дубликатов в базе и дальнейшего объединения данных о клиенте).

Пока возникают мысли:
- сделать trigram-индекс на некоторую комбинацию (Russian::translit(xxx).downcase) фамилии и имени (отчество может и отсутствовать).
- каким-то образом рассчитывать расстояния по Левенштейну или Джаро-Винклеру для всех записей (медленно?)

Прошу ткнуть в литературу/примеры.

Алексей

[Pavel Pavlov]

Транслитерация одной и той же фамилии может быть разной, будет считаться как разные люди. можно попробовать алгоритм шинглов, но тогда будут объединяться однокоренные фамилии. И как быть с полными тезками?
Может подойти к проблеме с другой стороны- сортировать по адресу, номеру телефона или другим параметрам?

18.07.2012 21:54 пользователь "Алексей Данченков" <adanc...@gmail.com> написал:

--
--
Данное сообщение отправлено Вам, так как Вы являетесь подписчиком группы "RubyOnRails to russian" на группах Google.
FAQ группы находится по адресу: http://ru.wikibooks.org/wiki/RubyFAQ
 
Для того, чтобы отправить сообщение в эту группу, пошлите его по адресу
ror...@googlegroups.com
Чтобы отменить подписку на эту группу, отправьте сообщение по адресу: ror2ru-un...@googlegroups.com
Дополнительные варианты находятся на странице группы http://groups.google.com/group/ror2ru?hl=ru

[Алексей Данченков]

Теоретически, проблемы с разной транслитерацией и должны быть устранены через fuzzy search.
Далее - три ветки:
1. При несовпадении даты рождения или другой подобной уникальной характеристики (жены с ФИО?) у полных тёзок они считаются различными.
2. При совпадении ФИО, даты рождения и какой-то части адреса (скажем, города), клиент полагается одним и остальные данные объединяются.
3. Во всех остальных случаях новую запись предполагается отдать на "ручное" сравнение, но необходимо вывести некий набор вариантов для объединения.
Далее "ниггеры", просматривая остальные данные о клиентах, будут принимать важные решения - объединить записи в одну (и выберут, с каким уже существующим клиентом объединиться) или создать новую запись.
В идеале задача в том, чтобы свести труд "ниггеров" к нулю.

19 июля 2012 г., 1:13 пользователь Pavel Pavlov <pave...@gmail.com> написал:

[undr]

https://github.com/undr/fuzzzy
Только пока нет адаптера для AR

четверг, 19 июля 2012 г., 0:54:15 UTC+7 пользователь danchenkov написал:

[Dmitry Lihachev]

Да, действительно проблемы с транслитерацией скорее всего будут устранены. Соответственно у вас два варианта - либо реализовывать fuzzy search самостоятельно, либо воспользоваться готовым решением. В своё время решал подобную задачу (надо было проставить соответствия вколоченных руками адресов адресам в КЛАДР) при помощи sunspot / solr. 

Алгоритм будет примерно такой - 

1. индексируем всех клиентов

2. достаём по одному и ищем всех похожих

далее всё то же что и раньше

19 июля 2012 г., 4:27 пользователь Алексей Данченков <adanc...@gmail.com> написал:

--
Regards

[Dmitry Lihachev]

Кстати, можно наверное ещё проще сделать через http://www.postgresql.org/docs/8.3/static/fuzzystrmatch.html

24 июля 2012 г., 13:10 пользователь Dmitry Lihachev <l...@openteam.ru> написал:

--
Regards

[Алексей Данченков]

Вопрос, собственно, и был в том, насколько быстро такой поиск будет работать, и если медленно, то как грамотно составить индекс.
SELECT * FROM clients WHERE levenshtein(client.name, params[:search]) < 5;?

Также, ФИО - русские. "Soundex is not very useful for non-English names".

24 июля 2012 г., 11:41 пользователь Dmitry Lihachev <l...@openteam.ru> написал:

[Dmitry Lihachev]

Fuzzy поиск в solr достаточно быстр (только индексировать 100k записей будет относительно медленно - у меня объекты индексируются со скоростью 50-100шт/сек) и работает с русским

За постгресовский fuzzy ничего сказать не могу, наверное тебе надо сделать тестовую базу и провести замеры производительности и оценить качество поиска. Если устроит - не парить себе мозг и юзать postgres.

explain analize в помощь

24 июля 2012 г., 16:22 пользователь Алексей Данченков <adanc...@gmail.com> написал:

--
Regards