Форумы GIS-Lab.info

Вопрос такой: как можно быстро и безболезненно присоединенить данные связанные с одной адресной базе в другую. Например у меня есть статистика с привязкой по адресной базе, ее нужно прицепить к карте у которой немного другая эта база ( в первой ул. Бронная , во второй - ул. М.Бронная). Жду предложений. Заранее всем спасибо)

может вот так?
http://gis-lab.info/qa/levenshtein.html

Например программно вырезать из ул. Бронная слово Бронная и в другой базе искать вхождение подстроки "Бронная"...ну как вариант...

Есть такой индексатор Sphinx называется. Он позволяет выдавать из индексированных источников результаты близкие к запрошенному (ул. Бронная -> Бронная). Исходники открыты - изучайте, как он это делает. Или приводите все слова к единому виду (отбрасываются ул., пл., пробелы и т.п.)

Если можете все перевести в MS Access, то у меня есть выписанная на VBA функция, для упомянутой выше метрики Левенштейна. Работает правда очень долго. Поскольку вычисления являются произведением количества исходных строк на количество строк шаблонов.

Boris писал(а):Если можете все перевести в MS Access, то у меня есть выписанная на VBA функция, для упомянутой выше метрики Левенштейна. Работает правда очень долго. Поскольку вычисления являются произведением количества исходных строк на количество строк шаблонов.

Для ускорения можно построить индекс. Тогда сначала будет долго этот индекс строиться, а потом быстро по нему искать. Если база меняется редко, и индексы не нужно часто перестраивать, то это поможет.

KolesovDmitry писал(а): Для ускорения можно построить индекс. Тогда сначала будет долго этот индекс строиться, а потом быстро по нему искать. Если база меняется редко, и индексы не нужно часто перестраивать, то это поможет.

А не поясните как именно построить индекс? Как я понял алгоритм расчета метрики состоит в расчете перестановок между двумя текстовыми строками. И функция расчета является кубической или квадратичной на длинной обеих строк. То, что можно вычислить какое-то число которое можно присвоить самой строке и оно будет говорить о подобии строки другим строкам с близкими числами индексов, ну или с помощью какой-то другой зависимости, я из описания метрики не вынес.
---
Что же касается самого вопроса, заданного автором, то там при отсутствии орфографических ошибок, дело сводится к нормализации формальных записей, что обычно быстро производится с помощью словаря подстановок, т.к. "М." в названии "М.Бронная" ничем кроме "Малая" не бывает. И хотя не большой знаток московской топонимики, но все же "М.Бронная" и просто "Бронная" должны быть разными улицами. Ну или для того, что бы так решить надо точно знать, что "Б.Бронной" не существует.

таки существует Б. Бронная, и на ней находится синагога
http://www.bronnaya.ru/

значит постановка задачи предельно не верна и предельно не политкорректна.

Boris писал(а):

KolesovDmitry писал(а): Для ускорения можно построить индекс. Тогда сначала будет долго этот индекс строиться, а потом быстро по нему искать. Если база меняется редко, и индексы не нужно часто перестраивать, то это поможет.

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

Реализаций может быть несколько, но идея везде примерно одна.

Пусть имеется множество объектов и метрика на этом множестве. Далее строится поисковое дерево, для простоты покажу на примере BKT:

* Выбирается случайно (или по какому-либо алгоритму) один элемент множества, называемый узлом. Обозначим его p.
* Рассчитывается расстояние от выбранного узла (p) до всех элементов множества.
* Строится первый уровень дерева (см. рисунок). Этот уровень разбивает исходное множество на подмножества элементов, равноудаленных от узла p. (Процедура работает для дискретных метрик, непрерывные метрики нужно предварительно разбить на интервалы). Каждое ребро дерева помечено числом. Это число=расстоянию от узла до всех элементов поддерева.
* Процедура повторяется на последующих уровнях: для элементов каждого поддерева выбирается новый узел, строится новое разбиение.

Поиск:
* Задается число R -- максимально допустимое расстояние от заданного поискового шаблона (s) до искомых элементов (u) в множестве. Т.е. ищем такие элементы u, для которых верно d(s,u)<R
* Расчитываем расстояние от s до узла p. Обозначим его r
* Ищем возможное решения на тех ветвях дерева, для которых метка удовлетворяет неравенству: * Последовательно поднимаемся по подходящим ветвям поддеревьев, рассчитывая расстояния от шаблона до соответствующих узлов, пока не соберем список всех листьев. Эти листья -- кандидаты в решение. Для окончательного решения нужно проверить каждый кандидат, рассчитав соответствующее расстояние между шаблоном и кандидатом.

В статье про использование метрики Левенштейна есть программный код. В примере для языка python есть модуль, который ищет при помощи поискового дерева FHQT. Во вложении -- статья с обзором поисковых алгоритмов.

спасибо за информацию.
тряхнем стариной. когда-то я почти написал диссертацию по быстрому поиску по заранее рассчитанным признакам у органических веществ.

Boris писал(а):спасибо за информацию.
тряхнем стариной. когда-то я почти написал диссертацию по быстрому поиску по заранее рассчитанным признакам у органических веществ.

ну если уж помянули отношение структура/свойство ... в начале 90-х мы использовали такой индекс: берем вектор (unsigned char) длиной число возможных в строке знаков (букв в алфавите+число точек, запятых, и т.д. - например амидных групп), и в i-ю позицию пишем 1, если такая буква/знак есть в слове (или считаем число таких букв) - линейный проход, поскольку сама буква используется как индекс в таблице номеров позиций. Мы считали в памяти скалярные произведения, т.е. число совпадающих позиций.