Цитата(nworm @ 2.5.2011, 17:04  ) |
| Если в адресе есть индекс, то разумно ориентироваться строго по нему. |
Это снова-таки при корректном написании названия НП. А если будет индекс 398000, но в адресе - "ЛИПИТСК", то хрен там чего определишь.
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Поиск географических названий в строке |
| Автор: RodionGork 2.5.2011, 14:50 |
| Уважаемые товарищи, добрый день! В ходе автоматической обработки информации есть необходимость пытаться выделить из строк какие-либо топонимы. Например "моковкий р-н м. ленинск. пр. ул. Танкиста 25 на трамвае до угла 8 ост" (имелось в виду "московский район, метро Ленинский проспект, улица Танкистов"). Типовая задача, например, получить из строки название района, метро и улицы, а потом проверить их соответствие (улица и метро должны быть в указанном районе). Исходная строка, к сожалению, может быть составлена довольно криво (например, почему бы не написать район в конце?), некоторых составляющих может не быть. Тем не менее задачу надо порешать. Пока предполагаю что нужно перебирать списки улиц, районов, станций и с помощью нечёткого поиска подстроки смотреть, какие из списка лучше подходят. Однако есть ещё проблемы. Например "Крестовский остров" умудряются сокращать как до "Крестовский о-в" так и до "Кр. остров". Или например могут быть улицы "Б. Проспект ПС" и "М. Проспект ПС", либо "1-я Красноармейская" "3-я Красноармейская" и т.п. Тупое нечёткое сравнение тут не поможет, вроде. Нужно задавать специфические паттерны для поиска... В связи с этим вопрос - есть ли какие-то статьи/монографии по похожим задачам, чтобы почитать про возможные подходы. А может какие-то пакеты и т.п. часть задачи решающие? За разумные советы заранее спасибо, Родион |
| Автор: Данкинг 2.5.2011, 14:58 |
| Криво написанные названия никак не выцепишь, только ассоциацией вручную. Общепринятые же сокращения вроде о-в, пр-т, ул. следует тоже прописать самому, но тут проще. Добавлено через 35 секунд А вообще конечная цель какая? Почтовый индекс проставить, что ли? |
| Автор: nworm 2.5.2011, 16:04 |
| Сложная считается задачка. Если в адресе есть индекс, то разумно ориентироваться строго по нему. Если нет, то вручную. Можно пробовать как-то уменьшить ручной труд, с помощью замен одних подстрок на другие и т.д. |
| Автор: Данкинг 2.5.2011, 16:47 | ||
Это снова-таки при корректном написании названия НП. А если будет индекс 398000, но в адресе - "ЛИПИТСК", то хрен там чего определишь. |
| Автор: RodionGork 4.5.2011, 10:18 |
| Минуточку. Как я сказал, с некорректно написанными названиями я работать умею, благо это задачка несложная. Я считаю допустимым чтобы в слове было до 1/3 опечаток (от длины паттерна), поэтому подстрока ЛИПИТСК по паттерну ЛИПЕЦК определяется на ура за время O(pattern.length * source.length). Как я сказал, сложность возникает при попытке решить что дальше с этим делать. Поясняю - ручного труда там должно быть по минимуму. Желательно обрабатывать хотя бы 100 строк в секунду. |
| Автор: Данкинг 4.5.2011, 10:29 | ||||
Не понял. А пример можно (на любом языке) ?
Так если ты выделил название улицы, то и проверяй по базе наличие его в данном районе. В чём вопрос? |
| Автор: RodionGork 4.5.2011, 15:43 |
| Пример... Лучше дам ссылку на источник, имхо там грамотнее. Вкратце суть следующая. Мы считаем что опечатки могут быть нескольких типов: - пропуск буквы; - вставка лишней буквы; - замена одной буквы на другую; - перестановка двух соседних букв. С такой постановкой возникают (у меня возникли) две основные задачи: - нечёткое сравнение двух строчек - решить, одинаковы ли слова ЛИПИТСК и ЛИПЕЦК; - нечёткий поиск подстроки - найти ЛИПЕЦК в строчке "АБЛИПИСЯ УХИЛИПИТСКАЯ ПИЛИЦЕЯ". Посёрфив в википедии я нашёл вот это для первой задачи: http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance http://en.wikipedia.org/wiki/Levenshtein_distance - упрощённый вариант, без перестановок, он понятнее для второй задачи решение описано здесь: http://en.wikipedia.org/wiki/Approximate_string_matching#Problem_formulation_and_algorithms (после слов "a better solution" - оно ссылается на вышеуказанные алгоритмы) Я получаю значит разницу между словами (минимальное количество замен) и могу сказать что если ЛИПЕЦК и ЛИПИТСК превращаются друг в друга с помощью 3 замен, а 4 буквы совпали, то это похожие слова... В общем, порог можно задать повыше или пониже, уже не важно... Ессно если вместо ЛИПЕЦК написано по ошибке МОСКВА, тут уж никто не спасёт. В общем, всё оказалось просто, хотя существуют более хитрые методы, как там написано, основывающися на том что замена Е на И например это менее значимая замена чем Ж на А и т.п. Но этой ерундой я уж заниматься не хочу, это на кандидатскую диссертацию можно... ;-) А задача теперь в том, что названия могут состоять из нескольких слов и быть по-разному сокращены... Нужно придумывать множественные паттерны и как-то ими оперировать... Скажем ЛИПЕЦКАЯ ДУБРОВКА может быть сокращена до ЛИПЕЦКАЯ ДУБ. или ЛИП. ДУБРОВКА... А кто-то со слуха напишет ЕГИПЕЦКАЯ БОБРОВКА (ессно с паттерном ЛИПЕЦКАЯ AND ДУБРОВКА это совпадёт, но получается нужно уже 3 паттерна хранить - для полного и двух сокращённых вариантов... фиг поймёшь, в общем... отчасти это похоже на поиск сайтов - и как известно яндекс недурно похожие задачи решает - но тут немножко наоборот, не один паттерн и много документов, а одна строка и к ней много паттернов...) |
| Автор: Данкинг 4.5.2011, 17:48 | ||
Так с помощью этого алгоритма, как я понял, можно сравнить два конкретных слова. Но если мы видим "ЛИПИТСК", то откуда мы знаем, что это непременно "ЛИПЕЦК"-то? Не будет же программа перебирать все города в поисках подходящего совпадения. |
| Автор: RodionGork 5.5.2011, 09:13 |
| Естественно надо перебирать все города по списку и сравнивать, какой лучше подойдёт. Если программа не имеет списка городов, конечно она никогда не узнает вообще, является ли слово названием или нет. Вот как этот список организовать - это другой вопрос. Если бы слова были без ошибок, можно было бы в виде дерева его сделать для скорости. Но здесь не тот случай... Получается, например, если строка адреса в среднем 50 символов, а длина названий в среднем 10 символов и всего надо перебрать 1000 названий, то требуется 50*10*1000=500 тыс сравнений символов... Если предположить для определённости что это занимает 1 секунду, то для проверки 10000 строчек потребуется 3 часа. Это безобразие. И вопрос именно в том какие подходы позволяют это дело оптимизировать. |
| Автор: Данкинг 5.5.2011, 10:09 |
| Вот-вот. В КЛАДРе примерно 90000 населённых пунктов. Если каждый из них перебирать, да ещё буквы подставлять, боюсь, скорость программы намного упадёт. До такой степени, что быстрее будет определить НП вручную, что будет и надёжней, так как всякие Томск и Омск могут быть весьма похожи друг на друга. |