Уважаемые товарищи, добрый день!

В ходе автоматической обработки информации есть необходимость пытаться выделить из строк какие-либо топонимы. Например "моковкий р-н м. ленинск. пр. ул. Танкиста 25 на трамвае до угла 8 ост" (имелось в виду "московский район, метро Ленинский проспект, улица Танкистов"). Типовая задача, например, получить из строки название района, метро и улицы, а потом проверить их соответствие (улица и метро должны быть в указанном районе).

Исходная строка, к сожалению, может быть составлена довольно криво (например, почему бы не написать район в конце?), некоторых составляющих может не быть.

Тем не менее задачу надо порешать. Пока предполагаю что нужно перебирать списки улиц, районов, станций и с помощью нечёткого поиска подстроки смотреть, какие из списка лучше подходят.

Однако есть ещё проблемы. Например "Крестовский остров" умудряются сокращать как до "Крестовский о-в" так и до "Кр. остров". Или например могут быть улицы "Б. Проспект ПС" и "М. Проспект ПС", либо "1-я Красноармейская" "3-я Красноармейская" и т.п. Тупое нечёткое сравнение тут не поможет, вроде. Нужно задавать специфические паттерны для поиска...

В связи с этим вопрос - есть ли какие-то статьи/монографии по похожим задачам, чтобы почитать про возможные подходы. А может какие-то пакеты и т.п. часть задачи решающие?

За разумные советы заранее спасибо,
Родион

Криво написанные названия никак не выцепишь, только ассоциацией вручную. Общепринятые же сокращения вроде о-в, пр-т, ул. следует тоже прописать самому, но тут проще.

Добавлено через 35 секунд
А вообще конечная цель какая? Почтовый индекс проставить, что ли?

Сложная считается задачка. Если в адресе есть индекс, то разумно ориентироваться строго по нему. Если нет, то вручную. Можно пробовать как-то уменьшить ручной труд, с помощью замен одних подстрок на другие и т.д.

Это сообщение отредактировал(а) nworm - 2.5.2011, 16:05

Это снова-таки при корректном написании названия НП. А если будет индекс 398000, но в адресе - "ЛИПИТСК", то хрен там чего определишь.

Минуточку.

Как я сказал, с некорректно написанными названиями я работать умею, благо это задачка несложная. Я считаю допустимым чтобы в слове было до 1/3 опечаток (от длины паттерна), поэтому подстрока ЛИПИТСК по паттерну ЛИПЕЦК определяется на ура за время O(pattern.length * source.length).

Как я сказал, сложность возникает при попытке решить что дальше с этим делать.

Поясняю - ручного труда там должно быть по минимуму. Желательно обрабатывать хотя бы 100 строк в секунду.

Это сообщение отредактировал(а) RodionGork - 4.5.2011, 10:21

Не понял. А пример можно (на любом языке) ?

Так если ты выделил название улицы, то и проверяй по базе наличие его в данном районе. В чём вопрос?

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

С такой постановкой возникают (у меня возникли) две основные задачи:
- нечёткое сравнение двух строчек - решить, одинаковы ли слова ЛИПИТСК и ЛИПЕЦК;
- нечёткий поиск подстроки - найти ЛИПЕЦК в строчке "АБЛИПИСЯ УХИЛИПИТСКАЯ ПИЛИЦЕЯ".

Посёрфив в википедии я нашёл вот это для первой задачи:
http://en.wikipedia.org/wiki/Damerau%E2%80...shtein_distance
http://en.wikipedia.org/wiki/Levenshtein_distance - упрощённый вариант, без перестановок, он понятнее
для второй задачи решение описано здесь:
http://en.wikipedia.org/wiki/Approximate_s..._and_algorithms
(после слов "a better solution" - оно ссылается на вышеуказанные алгоритмы)

Я получаю значит разницу между словами (минимальное количество замен) и могу сказать что если ЛИПЕЦК и ЛИПИТСК превращаются друг в друга с помощью 3 замен, а 4 буквы совпали, то это похожие слова... В общем, порог можно задать повыше или пониже, уже не важно... Ессно если вместо ЛИПЕЦК написано по ошибке МОСКВА, тут уж никто не спасёт.

В общем, всё оказалось просто, хотя существуют более хитрые методы, как там написано, основывающися на том что замена Е на И например это менее значимая замена чем Ж на А и т.п. Но этой ерундой я уж заниматься не хочу, это на кандидатскую диссертацию можно... ;-)

А задача теперь в том, что названия могут состоять из нескольких слов и быть по-разному сокращены... Нужно придумывать множественные паттерны и как-то ими оперировать... Скажем ЛИПЕЦКАЯ ДУБРОВКА может быть сокращена до ЛИПЕЦКАЯ ДУБ. или ЛИП. ДУБРОВКА... А кто-то со слуха напишет ЕГИПЕЦКАЯ БОБРОВКА (ессно с паттерном ЛИПЕЦКАЯ AND ДУБРОВКА это совпадёт, но получается нужно уже 3 паттерна хранить - для полного и двух сокращённых вариантов... фиг поймёшь, в общем... отчасти это похоже на поиск сайтов - и как известно яндекс недурно похожие задачи решает - но тут немножко наоборот, не один паттерн и много документов, а одна строка и к ней много паттернов...)

Это сообщение отредактировал(а) RodionGork - 4.5.2011, 15:45

Так с помощью этого алгоритма, как я понял, можно сравнить два конкретных слова. Но если мы видим "ЛИПИТСК", то откуда мы знаем, что это непременно "ЛИПЕЦК"-то? Не будет же программа перебирать все города в поисках подходящего совпадения.

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

Вот как этот список организовать - это другой вопрос. Если бы слова были без ошибок, можно было бы в виде дерева его сделать для скорости. Но здесь не тот случай... Получается, например, если строка адреса в среднем 50 символов, а длина названий в среднем 10 символов и всего надо перебрать 1000 названий, то требуется 50*10*1000=500 тыс сравнений символов... Если предположить для определённости что это занимает 1 секунду, то для проверки 10000 строчек потребуется 3 часа. Это безобразие. И вопрос именно в том какие подходы позволяют это дело оптимизировать.

Вот-вот. В КЛАДРе примерно 90000 населённых пунктов. Если каждый из них перебирать, да ещё буквы подставлять, боюсь, скорость программы намного упадёт. До такой степени, что быстрее будет определить НП вручную, что будет и надёжней, так как всякие Томск и Омск могут быть весьма похожи друг на друга.