Реферат: Удк 681. 51: 57 Использование методов приближенного поиска строк в информационных системах

УДК 681.51:57

Использование методов приближенного поиска строк в информационных системах

Ю.В. Шамарин

Донецкий национальный университет


Для повышения достоверности и качества данных в информационных системах необходимо применение специализированных подходов и методов.

Целью работы является экспериментальное сравнение существующих методов приближенного поиска строк, которые можно использовать в информационных системах, использующих СУБД.

Главным критерием при выборе методов приближенного поиска является возможность его использования совместно со стандартным оператором запросов SELECT.

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

Функция Левенштейна в качестве оценки похожести строк использует количество операций редактирования необходимое для преобразования одной строки в другую [1]. Достоинством использования функции Левенштейна является независимость от предметной области и соответствии наиболее распространенным ошибкам, которые допускают операторы.

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

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

Для использования функции Левенштейна была разработана пользовательская функция (UDF), которая использовалась в условиях отбора WHERE оператора SELECT.

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

Для использования q-грамм был выбран подход, предложенный в [2]. Для этого был разработан триггер, который разбивает требуемое поле на q-граммы и хранимая процедура, позволяющая производить отбор похожих строк по указанной строке-образце.

Достоинством разбиения строк на q-граммы является возможность оптимизации поиска средствами СУБД и использования в большинстве современных СУБД. Недостатком использования является необходимость предварительной подготовки строк для поиска – разбиение на q-граммы, и дополнительных расходов памяти для хранения q-грамм.

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


Литература

1. Гасфилд Д. Сроки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. – СПб.: Невский диалект, 2003. – 654 с.

2. Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Lauri Pietarinen, Divesh Srivastava. Using q-grams in a DBMS for Approximate String Processing. // Bulletin of the Technical Committee on Data Engineering. 2001. Vol. 24, No. 4. P. 28-35.