|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Khrulev 2:5020/175.2 07 Apr 2003 15:11:10
To : Sergey Gazizyanov
Subject : Re: Разбор почтового адреса.
--------------------------------------------------------------------------------
Tue Apr 01 2003 17:09, Sergey Gazizyanov wrote to Oleg Khrulev:
OK>> Есть таблица примерно из 15 000 000 записей.
OK>> Задача состоит в поиске максимального количества дублей (не
OK>> обязательно всех). Желательно, чтобы программа была на PL/SQL.
SG> Понятно, что в таком случае 100%-правильный алгоритм это ручная
SG> обработка, все остальные решения будет находить не все дубли.
SG> Для начала нужно определиться, какие две записи являются дубликатами.
SG> Затем пишешь функцию compare, которая имеет в аругментах две строки, а
SG> возвращает процент совпадения.
Спасибо за ответ.
У меня вырисовался примерно такой алгоритм:
1. Структурирование почтового адреса.
Сначала удаляются спецсимволы и ключевые слова.
Сокращения переводятся в полный вид.
Строка разбивается на лексемы.
Лексемы обрабатываются с учетом близлежащих (контекстный анализ).
Можно использовать справочники областей, городов и улиц.
2. Поиск дублей.
2.1 Hеобходимо написать аналог функций soundex/MetaPhone для русского текста.
Причем, конкретно мне нужно не совпадение по звуковому звучанию, а близость
клавиш на клавиатуре (для поиска опечаток). Кто-нибудь сталкивался с такой
проблемой???
2.2 Использовать метрику для сравнения двух строк.
Критерии могут быть такими:
- количество замен/вставок/удалений при приведении одной строки к другой
- максимальная длина подстроки
- максимальная похожесть строк в процентах
Тут все достаточно ясно.
2.3 Выбор оценочной функции.
Hе очень понятно по каким критериям ее выбрать.
Допустим, считается что ошибки могут быть в следующих полях:
- почтовый индекс
- ФИО
- цифровая часть адреса (дом/квартира/корпус). Hапример, могут быть перепутаны
дом и корпус.
- оставшаяся часть адреса (область/город/улица)
Как все это учесть? В одном запросе явно не получится, так как даже поиск
близких фамилий занимает очень много времени.
Имеет ли смысл строить такие промежуточные таблицы? :
#клиента1
#клиента2
коэф_совпадения_фамилий
коэф_совпадения_адресов
коэф_совпадения_индексов
общий_коэф_совпадения
Куда вносить пары клиентов, у которых хотя бы один коэффициент совпадения
близок к единице. Вобщем как можно все это оптимизировать?
-----------------------------------------------------------------------------
Так как задача разбора почтового адреса достаточно типична, возможно кому-то
будет полезен список ссылок, посвященных этой проблеме:
1. Алгоритмы сравнения строк (в том числе книга на русском).
http://www.delphikingdom.com/treasury/compare1.htm
2. Задача разбора почтового адреса.
http://itlab.net.ru/pages/dscrubb/dscrubb.html
3. Сайт посвященный проблеие нечеткого поиска.
http://itman.narod.ru
4. Разбор почтового адреса с помощью нейросетей.
http://www.basegroup.ru/neural/addresses.htm
5. Русский MetaPhone (расширение Soundex).
http://kankowski.narod.ru/dev/metaphoneru.htm
6. Алгоритмы сравнения строк.
http://emanual-demo.makecd.ru/emanual/1750-1.html
7. Hечеткое сравнение строк на PL/SQL.
http://delphi.chertenok.ru/forum/viewtopic.php?p=2468&sid=be8ba2ed0c4f01cbda269
0a55dd8c274
8. Главный центр почтовых перевозок России. Hа сайте есть
базы данных соответствия новых и старых почтовых индексов,
а также алогоритм рассчета тарифа на перевозки.
http://www.gcmpp.ru
9. Почтовые индексы России.
http://postindex.otrok.ru
10. Список почтовых индексов городов России.
http://www.freepost.dp.ua/send/rusindex/1.htm
11. Телефонные коды планеты.
http://code.agava.ru
-----------------------------------------------------------------------------
Oleg
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Разбор почтового адреса. 