Нечеткий поиск

@kukuruku310 · Регистрация: 14.02.2010

Студворк — интернет-сервис помощи студентам

Добрый день!
Возможно ли в принципе полностью автоматически со 100% точностью "распознать" адреса?

Есть КЛАДР, содержащий правильные названия адресов с учетом их иерархии. Есть список объектов с адресами, введенными со всеми ошибками, какие только можно придумать: как орфографическими, так и логическими. Есть сокращенные названия вместо полных КЛАДР, или наоборот. Записи вроде "ул.Первого мая" вместо "1 Мая". Неправильные адреса ("от березы у поворота 100м за горизонт"). Неоднозначные адреса ("д.Тмутаракань" вместо "д.Новая Тмутаракань" или "д.Старая Тмутаракань"). Еще может быть разный мусор, вроде номера дома, или, например, "ранее адрес был такой-то", двойные названия улиц для угловых домов и т.д.

Задача условно решена, причем распознаны практически все правильные адреса, НО как "отделить зерна от г...". Пробовал около десятка (или больше) способов. От тупого поиска по LCS (largest common sequence) (в том числе разные его модификации) до супер-пупер алгоритма, вроде поиска отдельных элементов адреса всеми возможными способами с учетом результата при поиске следующего элемента этого же адреса. В конце концов, все упирается в выбор критерия отбора. Все попытки или сбрасывают число распознанных адресов до 55-65%, или в результат попадает мусор. И это с учетом того, что нормализованные адреса где-то на 30% абсолютно совпадают с наименованием КЛАДР.

Ковырял в общей сложности периодически, наверное, около месяца! Но в конце все равно пришлось ручками просматривать немаленький список из нескольких десятков тысяч строк - правда, с учетом полученных результатов ушло на это часа два. Блин!
Оно, конечно, сейчас имеется "список замен" для "существующего списка", и с его помощью задача решается, но вот осталось чувство мучительной боли за бесцельно... (и ощущение занозы в одном интересном месте).
Может кто подскажет литературу/метод/технологию/направление (даже из трех букв)
Спасибо!

Day · 18.03.2010, 21:53

Возможно ли в принципе полностью автоматически со 100% точностью "распознать" адреса?

Увы, помочь ничем не могу.
Но восхищен постановкой задачи.
А если задачи ставятся - они когда-нибудь и решатся.
С роботом, в голове которого решается такая задача, можно уже и поговорить.
И даже предложить ему чокнуться (в правильном смысле) рюмкой спирта для протирания оптической оси.
Удачи!
ЗЫ: Как говаривал граф Калиостро, имеет смысл решать только неразрешимые задачи
(возможно, я путаю персоонажи)

@kukuruku310 · 18.03.2010, 23:50 **[ТС]**

Задача, увы, не из области теории. Пока в базе было не более одного десятка тысяч записей как-то справлялся на полуатомате. А когда начались задачи по сравнению баз до сотни тысяч - такая вот проблема и возникла. Просто надоело каждый раз по-новому тренировать зрение.

И все-таки, думаю, что решение какое-то более-менее приемлемое должно существовать. К тому же не черезчур сложное и реально решаемое силами одной машины в течение не дольше хотя бы часов двух. В конце концов "набор" входных данных сильно ограничен, несмотря на разнообразие их форм. И вполне реально привести их все к сильно ограниченному и достаточно небольшому объему данных. До робота, с которым можно поговорить, конечно, и рядом не лежало. Да за такую задачу я бы, пожалуй, и браться не стал. (математике меня последний раз пытались научить лет этак с тридцать назад, так что...). Моя проблема попроще на несколько порядков.

Но за участие спасибо!

Day · 19.03.2010, 12:00

kukuruku310, Я думаю что некие эвристики тут могут возникнуть только у того, кто долго "тренировал зрение". А без эвристик тут никак - теорий то нету!
Я иногда делаю так - представляю как бы с этой задачей справлялся человек, например я
И, как ни странно, бывают положительные результаты.
Как я уже говорил, ничего кроме самых общих методологий, предложить не могу.
ЗЫ: но пообщаться приятно.

@alex_x_x · 19.03.2010, 19:02

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

07.02.2011, 00:45

Если вопрос еще актуален, то по теме можно добавить следующее.
В общем виде поставленную задачу со 100% точностью решить невозможно хотя бы потому, что зачастую адрес записывается так, что однозначно его интерпретировать нельзя. Плюс при настройке нечеткого поиска всегда возникает две крайности.

Либо Вы ослабляете критерии, по которым программа выполняет сопоставление исходного адреса с эталонным. В этом случае полнота поиска возрастает, но при этом возрастает процент ложных срабатываний, когда явный несуществующий "шлак" интерпретируется как якобы правильный адрес. В терминологии поисковых систем это соответствует росту полноты поиска, но падению его точности.
Либо Вы ужесточаете критерии сопоставления. В этом случае наоборот полнота поиска падает, но точность растет.

Все что вы можете сделать при фиксированном наборе критериев сопоставления, это найти своеобразную золотую середину, добившись приемлемых показателей как точности, так и полноты. Сделать это можно на основе обучающей выборки одним из методов машинного обучения.
Более подробно именно на эту тему мои коллеги написали несколько статей и сделали соответствующие доклады на RCDL. Ознакомиться с ними Вы можете здесь.
Практические результаты этих исследований реализованы в виде сервиса, который свободно доступен по адресу http://ahunter.ru.

@alex_x_x · 07.02.2011, 00:58

Bash
1
2
3
4
5
6
7
8
9
10
11
Саня Поддубный
Свидетель
Сейбер
Сейлормун
Синдзи
Смехуечки:Котопёс
Сотона
Спанчбоб
Странная Эмили
Суигинто
Суисейсеки

Bash
1
2
[alexxx@localhost ~]$ agrep -i2 "Ипдзи" 1.txt
Синдзи

вот вам стораз готовая библиотека

@kukuruku310 · 07.02.2011, 12:34 **[ТС]**

Orca, Спасибо, к этому уже и пришел: то, что опознано без вариантов, сразу принимается, остальное - с ручным подтверждением. Вот только задачу пока забросил и не сделал удобную форму подтверждения. Нажать Вам "Спасибо" не получилось - нет такой кнопки на посте.

alex_x_x,
Такой простой вариант не срабатывает, вернее выдает слишком много не того. Но все равно спасибо.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@kukuruku310 306 / 187 / 26 Регистрация: 14.02.2010 Сообщений: 547

	Нечеткий поиск 18.03.2010, 18:43. Показов 4686. Ответов 7 Метки нет (Все метки) Добрый день! Возможно ли в принципе полностью автоматически со 100% точностью "распознать" адреса? Есть КЛАДР, содержащий правильные названия адресов с учетом их иерархии. Есть список объектов с адресами, введенными со всеми ошибками, какие только можно придумать: как орфографическими, так и логическими. Есть сокращенные названия вместо полных КЛАДР, или наоборот. Записи вроде "ул.Первого мая" вместо "1 Мая". Неправильные адреса ("от березы у поворота 100м за горизонт"). Неоднозначные адреса ("д.Тмутаракань" вместо "д.Новая Тмутаракань" или "д.Старая Тмутаракань"). Еще может быть разный мусор, вроде номера дома, или, например, "ранее адрес был такой-то", двойные названия улиц для угловых домов и т.д. Задача условно решена, причем распознаны практически все правильные адреса, НО как "отделить зерна от г...". Пробовал около десятка (или больше) способов. От тупого поиска по LCS (largest common sequence) (в том числе разные его модификации) до супер-пупер алгоритма, вроде поиска отдельных элементов адреса всеми возможными способами с учетом результата при поиске следующего элемента этого же адреса. В конце концов, все упирается в выбор критерия отбора. Все попытки или сбрасывают число распознанных адресов до 55-65%, или в результат попадает мусор. И это с учетом того, что нормализованные адреса где-то на 30% абсолютно совпадают с наименованием КЛАДР. Ковырял в общей сложности периодически, наверное, около месяца! Но в конце все равно пришлось ручками просматривать немаленький список из нескольких десятков тысяч строк - правда, с учетом полученных результатов ушло на это часа два. Блин! Оно, конечно, сейчас имеется "список замен" для "существующего списка", и с его помощью задача решается, но вот осталось чувство мучительной боли за бесцельно... (и ощущение занозы в одном интересном месте). Может кто подскажет литературу/метод/технологию/направление (даже из трех букв) Спасибо! 1

@kukuruku310 306 / 187 / 26 Регистрация: 14.02.2010 Сообщений: 547
	18.03.2010, 23:50 [ТС]
	Задача, увы, не из области теории. Пока в базе было не более одного десятка тысяч записей как-то справлялся на полуатомате. А когда начались задачи по сравнению баз до сотни тысяч - такая вот проблема и возникла. Просто надоело каждый раз по-новому тренировать зрение. И все-таки, думаю, что решение какое-то более-менее приемлемое должно существовать. К тому же не черезчур сложное и реально решаемое силами одной машины в течение не дольше хотя бы часов двух. В конце концов "набор" входных данных сильно ограничен, несмотря на разнообразие их форм. И вполне реально привести их все к сильно ограниченному и достаточно небольшому объему данных. До робота, с которым можно поговорить, конечно, и рядом не лежало. Да за такую задачу я бы, пожалуй, и браться не стал. (математике меня последний раз пытались научить лет этак с тридцать назад, так что...). Моя проблема попроще на несколько порядков. Но за участие спасибо! 1

Day 1180 / 990 / 83 Регистрация: 29.10.2009 Сообщений: 1,385
	19.03.2010, 12:00
	kukuruku310, Я думаю что некие эвристики тут могут возникнуть только у того, кто долго "тренировал зрение". А без эвристик тут никак - теорий то нету! Я иногда делаю так - представляю как бы с этой задачей справлялся человек, например я И, как ни странно, бывают положительные результаты. Как я уже говорил, ничего кроме самых общих методологий, предложить не могу. ЗЫ: но пообщаться приятно. 1

@alex_x_x бжни 2473 / 1684 / 135 Регистрация: 14.05.2009 Сообщений: 7,162
	19.03.2010, 19:02
	есть программы решающие задачи нечеткого поиска, но не настолько сурового! как правило сводится к орфографическим ошибкам, искривлением написания, но не прям чтоб так например старый добрый agrep 0

Orca
	07.02.2011, 00:45
	Сообщение было отмечено как решение Решение Если вопрос еще актуален, то по теме можно добавить следующее. В общем виде поставленную задачу со 100% точностью решить невозможно хотя бы потому, что зачастую адрес записывается так, что однозначно его интерпретировать нельзя. Плюс при настройке нечеткого поиска всегда возникает две крайности. Либо Вы ослабляете критерии, по которым программа выполняет сопоставление исходного адреса с эталонным. В этом случае полнота поиска возрастает, но при этом возрастает процент ложных срабатываний, когда явный несуществующий "шлак" интерпретируется как якобы правильный адрес. В терминологии поисковых систем это соответствует росту полноты поиска, но падению его точности. Либо Вы ужесточаете критерии сопоставления. В этом случае наоборот полнота поиска падает, но точность растет. Все что вы можете сделать при фиксированном наборе критериев сопоставления, это найти своеобразную золотую середину, добившись приемлемых показателей как точности, так и полноты. Сделать это можно на основе обучающей выборки одним из методов машинного обучения. Более подробно именно на эту тему мои коллеги написали несколько статей и сделали соответствующие доклады на RCDL. Ознакомиться с ними Вы можете здесь. Практические результаты этих исследований реализованы в виде сервиса, который свободно доступен по адресу http://ahunter.ru.

@kukuruku310 306 / 187 / 26 Регистрация: 14.02.2010 Сообщений: 547
	07.02.2011, 12:34 [ТС]
	Orca, Спасибо, к этому уже и пришел: то, что опознано без вариантов, сразу принимается, остальное - с ручным подтверждением. Вот только задачу пока забросил и не сделал удобную форму подтверждения. Нажать Вам "Спасибо" не получилось - нет такой кнопки на посте. alex_x_x, Такой простой вариант не срабатывает, вернее выдает слишком много не того. Но все равно спасибо. 0

Нечеткий поиск

Решение