Базы данных: нечёткий поиск строк

[AnTe]

Здравствуйте!

Возникла проблема, которая видится довольно типичной.

На всякий случай дам предысторию вопроса. Сразу скажу, что в теории и практики БД не силён

Есть несколько (пусть для определённости, две) баз данных, в которых должна содержаться идентичная информация. Например, в моём случае, информация об изделиях, в частности, о радиоэлементах. И базы данных есть производственная, а вторая - у конструкторов.

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

Проблема в том, что исторически базы данных были получены из различных источников. На производстве их забивали одни люди, в конструкторском отделе - другие, поэтому куча несогласованностей и главное, конечно же, ошибок.

Стоит задача свести эти базы воедино.

Решение проблемы сводится к вопросу поиска "нечёткого" поиска по базе данных.

То есть, имеется база данных, в которой некоторое текстовое поле ("обозначение") идентифицирует искомый объект. Оператор в клиентской программе вводит предполагаемое обозначение искомого объекта и запускает процедуру поиска.

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

Некоторые ошибки типичны (например, вместо нолика "0" стоит большая буква "О", русские буквы забиты схожими в латинице (или наоборот), некоторые не совсем типичны: поставлен лишний пробел, пробела не хватает, пропущена или указана лишняя цифра и т.п.

Возможно ли каким-либо образом средствами баз данных (в наличии оракл) организовать такой поиск, нет ли штатных средств для этого?

Например, встречал множество различных алгоритмов и даже готовых функций по "нечёткому" сравнению строк, решение "в лоб" - выковырять ключевое поле, по которому производится поиск, в массив, а затем организовать поиск по массиву.

Может, возможно это сделать более цивилизованными средствами, как-нибудь привинтить к БД? Или более того - технология соответствующая имеется?

[Vapaamies]

Сообщение от AnTe

Или более того - технология соответствующая имеется?

Придумать какой-нибудь алгоритм нормализации, по принципу Soundex. К примеру, выкидывать пробелы и знаки препинания, приводить артикулы к одной длине, дополняя пробелами, заменять нули на "О" и т. п. Может даже хватить обычной функции replace. Потом нормализированные части как-то склеивать в строку и сравнивать с нормализованной строкой на другой стороне.

[AnTe]

Сообщение от Vapaamies

Придумать какой-нибудь алгоритм нормализации, по принципу Soundex. К примеру, выкидывать пробелы и знаки препинания, приводить артикулы к одной длине, дополняя пробелами, заменять нули на "О" и т. п. Может даже хватить обычной функции replace. Потом нормализированные части как-то склеивать в строку и сравнивать с нормализованной строкой на другой стороне.

Ухтыблин. Ну есс-но именно это и было придумано, более того - название такое же дал, "нормализовать", приводить к одной строке (обозначение то реально хранится в нескольких полях), создаваемой по определённому алгоритму, а я то всё думал слово "нормализация" не совсем точно отражает суть происходящего, искал замену.

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

т.е. функцию хоррошего сравнения двух строк сделать не вопрос, вопрос в том, как её вставить в базу данных. Ну ладно у меня сейчас БД небольшая, не больше полумиллиона записей, можно в массив отдублировать и перебирать его. Ну а как их больше будет?

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

[Vapaamies]

Сообщение от AnTe

Но с нормализацией как раз и приходим к исходной задаче. Имеем теперь уже лишнее, нормализованное поле, по которому проводим поиск.

Делаем его либо виртуальным полем, если позволяет СУБД, либо обычным полем с обновлением триггером, создаем по нему индекс. Либо создаем функциональный индекс, если позволяет СУБД.

Сообщение от AnTe

ошибки другого типа - пропуск или ввод лишних символов не учитываются

Придумываем функцию хеширования или "рафинирования", -- не знаю, как правильно назвать. Можно даже попробовать поискать теорию, как работает алгоритм в Google. Скорее всего, она проработана и открыта, а не конкретно Google или "Яндекс" ее придумал.

[AnTe]

Забыл отписаться. В оракле, (начиная с 9го, если не ошибаюсь) нечёткий поиск - штатная функция

[Utkin]

Есть несколько (пусть для определённости, две) баз данных, в которых должна содержаться идентичная информация.

Если это не учебное задание, то это ошибка проектирования.

[Аватар]

это ошибка проектирования.

Навряд ли. Информация с разных источников и попытка объединить. Как разовая задача - трудоемкая поэтапная конвертация, с выделением некоторых закономерностей, типичности и постепенным отсеиванием сведенной к единому целому части. Возможно RCO

[buriat]

Я когда-то использовал функцию (Levenshtein distance), которая определяет на сколько символов отличаются две строки. Потом сравнивал это кол-во символов с заданным числом (на сколько максимум могут отличаться) и делал вывод - похожа строка или нет.
В твоем случае можно было бы применить к нормализованным строкам.