Удк 681. 51: 57 Использование методов приближенного поиска строк в информационных системах
| Вид материала | Документы |
- Удк 340. 6+681. 327+681 015 Д. В. Ландэ, В. Н. Фурашев, 450.24kb.
- Удк 681 053: 681. 32: 007, 134.3kb.
- Удк 519. 681 Формализация некоторых аспектов взаимодействия алгоритмов с внешней средой, 15.98kb.
- Удк 378. 144: 004. 3 Т. В. Столяр, зав библиотекой, 156.42kb.
- Курсовая работа по информатике на тему: Эффективность поиска в Интернете сведений, 88.75kb.
- Удк 681. 51: 303. 732+681 066 вопросы анализа проблем рыбохозяйственных комплексов:, 87.72kb.
- Лекция. Информационные ресурсы общества, 38.1kb.
- Представлен: Украина, 26.75kb.
- «Использование информационных технологий для изучения детерминант экономического развития», 184.88kb.
- Удк 681. 3: 519 применение методов data mining для формирования базы знаний экспертной, 78.88kb.
УДК 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.