Анализ подходов к реализации нечеткого поиска записей в базе данных

Размещено на http://www.allbest.ru/

Анализ подходов к реализации нечеткого поиска записей в базе данных

Ю.В. Лещик

Национальный исследовательский Томский

Политехнический Университет, г. Томск, catlen@ya.ru

Поиск - одно из наиболее часто встречающихся в программировании действий. Однако не всегда поиск подразумевает нахождение точного соответствия поставленным условиям. Часто возникает необходимость в поиске по сходству или нечетком поиске. Поиск по сходству - это поиск объектов, похожих в определенном смысле на некоторый заданный объект. Объекты могут быть самыми разнообразными: адреса, фамилии, отрывки документов, точки n-мерного пространства, а также геометрические фигуры [1].

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

Механизмы нечетких запросов (fuzzy queries, flexible queries) к реляционным базам данных, базирующиеся на теории нечетких множеств Заде, были впервые предложены в 1984 году и впоследствии получили развитие в работах Д. Дюбуа и Г. Прада.

Для реализации подобных запросов необходимо формализовано описать множества значение термов логического выражения. Моделью таких структур является лингвистическая переменная и функция принадлежности.

Под лингвистической следует понимать переменную, значениями которой являются слова или предложения естественного или искусственного языка. Например, «Возраст» -- лингвистическая переменная, если она принимает лингвистические, а не числовые значения, т.е. значения «молодой», «не молодой», «очень молодой», «вполне молодой», «старый», «не очень старый», «не очень молодой» и т. п., а не 20, 21, 22 и т. д. [2].

Т.е. лингвистическая переменная описывается набором, где - имя лингвистической переменной; U - базовое множество: Т - множество ее значений (терм-множество), представляющие имена нечетких переменных, областью определения которых является множество; G - синтаксическая процедура, позволяющая оперировать элементами терм-множества, в частности, генерировать новые термы (значения); М - семантическая процедура позволяющая преобразовывать новые значения лингвистической переменной, образованной процедурой G, в нечеткую переменную, т.е. сформировать соответствующее нечеткое множество.

Функцией принадлежности называется функция, которая позволяет вычислить степень принадлежности произвольного элемента u множества U к нечеткому множеству F [3].

Алгоритм нечеткого поиска записей в таблице базы данных можно представить в виде следующих шагов:

1. Выделяется первая запись в базе данных.

2. Рассматривается первый поисковый признак, сформулированный в запросе, и его значение.

3. По признаку находится соответствующий атрибут базы данных.

4. Вычисляется значение функции принадлежности, соответствующей значению признака, в точке, представляющей значение анализируемого атрибута. Полученное значение функции принадлежности запоминается.

5. Рассматривается следующий поисковый признак и повторяются шаги 3 и 4 до окончания поисковых признаков. В результате будет получен набор значений функций принадлежности всех атрибутов анализируемой записи.

6. Основываясь на полученных на шаге 5 наборах значений, вычисляется обобщенная оценка принадлежности анализируемой записи запросу (минимальное значение из указанного набора, произведение элементов набора и т.п.). Полученное обобщенное значение запоминается в рабочем поле базы данных.

7. Осуществляется переход на следующую запись и повторяется шаг 2. Повторение происходит до тех пор, пока не будут перебраны все записи.

Результатом поиска по нечеткому запросу станет упорядоченная выборка записей по степени их соответствия данному запросу от 1 (полное соответствие) до 0 (полное несоответствие) [4].

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

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

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

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

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

Процесс выделения характерных элементов строк называют сэмплированием. Чаще всего используются следующие методы сэмплирования:

* сэмплирование подстрок: префиксов, суффиксов или n-грамм;

* буквенное сэмплирование;

* метрическое сэмплирование.

Метрический метод сэмплирования заключается в вычислении вектора расстояний от заданной строки до образующих элементов. Образующие элементы могут быть выбраны из существующих строк словаря или сгенерированы.

В целях поиска сэмплы могут быть преобразованы. Так, например, на основании набора n-грамм могут быть построены, как инвертированные списки, так и частотные вектора. Следующие два вида преобразований сэмплов наиболее распространены:

* построение частотного вектора;

* построение сигнатурного вектора.

Осуществив преобразование строк в сэмплы, можно проиндексировать словарь для быстрого доступа. Для этого можно использовать следующие алгоритмы:

* trie-деревья;

* инвертированный индекс;

* координатные структуры, например, kd- деревья и rd-деревья;

* “точный индекс”, используемый для поиска методом расширения выборки. нечеткий поиск запись база

Комбинирование различных методов сэмплирования и индексирования позволяет строить новые алгоритмы [5].

Таким образом, выделены следующие подходы к решению задачи нечеткого поиска записей в реляционной базе данных: построение нечетких запросов и преобразование записей таблиц базы данных в строки с применением к ним поиска по сходству. Каждый из подходов может быть реализован с помощью множества разнообразных алгоритмов, отличных по точности и скорости поиска и характеризующихся различными проблемами. Так, например, в случае использования нечетких запросов возникает проблема определения функции принадлежности, находящаяся за пределами теории нечетких множеств и относящаяся в большей степени к теории экспертного оценивания. А в случае поиска по сходству необходимо выбрать функцию близости слов в зависимости от критериев эффективности нечеткого поиска применительно к текущей задаче. Рассматриваемые алгоритмы имеют множество модификаций, поэтому выбор оптимального способа реализации нечеткого поиска записей базы данных зависит от ее характеристик (структуры, размера и т.д.) и особенностей постановки задачи.

Литература

1. ЧАВО по нечеткому поиску (поиску по сходству). URL http://www.itman.narod.ru/ir/faq/fzfaq_gen.html#q1_1 (дата обращения: 30.06.2012).

2. Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений. - М.: Мир, 1976.

3. Математическое описание нечетких запросов к реляционным базам данных. URL http://rybanoff.narod.ru/bdat/bd_lection_12.pdf (дата обращения: 30.06.2012).

4. Рыжов А.П. Модели поиска информации в нечеткой среде. - М.: Издательство Центра прикладных исследований при механико-математическом факультете МГУ, 2004.

5. Бойцов Л.М. Классификация и экспериментальное исследование современных алгоритмов нечеткого словарного поиска // Труды 6-й Всероссийской научной конференции ?Электронные библиотеки: перспективные методы и технологии, электронные коллекции? - RCDL2004, Пущино, Россия, 2004.

Размещено на Allbest.ru