WWW.NET.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Интернет ресурсы
 

«1. Введение В статье рассматривается задача сравнения времени применения метода trie-деревьев и метода q-грамм для реализации системы нечеткого поиска для ...»

УДК 004.65

СРАВНЕНИЕ МЕТОДА TRIE-ДЕРЕВЬЕВ И Q-ГРАММ ПРИ НЕСТРОГОМ СОЕДИНЕНИИ ТАБЛИЦ В MYSQL

Ключевые слова: базы данных, нестрогое реляционное соединение, сопоставление записей

В.В. Кедровская, Г.О. Федоркова

Липецкий государственный технический университет

Предлагается сравнение метода trie-деревьев, реализованного в виде программного proxy-уровня, работающего между СУБД MySQL и клиентскими приложениями, осуществляющего парсинг и оптимизацию запросов, содержащих операцию нестрогого равенства, и метода q-грамм, реализованного с помощью SQL-запросов.

1. Введение В статье рассматривается задача сравнения времени применения метода trie-деревьев и метода q-грамм для реализации системы нечеткого поиска для СУБД MySQL при помощи выполнения запросов нестрогого соединения таблиц. Целью данного сравнения является определение более эффективного и быстрого метода поиска.

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

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



Поскольку опечатки имеют неодинаковую частоту для разных пар букв, следует задать функцию стоимости преобразования как : (S { }) 2 Z (1) Здесь - «пустой» символ, так что (, а) - стоимость вставки символа a, (, ) - стоимость удаления, (, a) - стоимость замены на а, (a, a) = 0 для любого а.

Таким образом, расстояние Левенштейна целесообразно использовать для определения степени близости строковых значений и нахождения «похожих» значений ключевых атрибутов.

Для поиска близких по Левенштейну записей используются такие методы поиска, как метод расширения выборки, сигнатурные алгоритмы, алгоритмы последовательного перебора, алгоритмы фонетической похожести. В [1] предложена операция нестрогого соединения таблиц методом сравнения попарных записей. Основной сложностью при этом является время выполнения операции нестрогого соединения. Предлагается использовать подход, основанный на применении метода q-грамм [2], и сравнить время операции нестрогого соединения с помощью метода q-грамм и метода trie-деревьев [3].

2. Метод trie-деревьев Trie-деревья – это структура, поиск в которой основан на представлении термина последовательностью символов. В trie-дереве все строки, имеющие общее начало, располагаются в одном поддереве. Каждое ребро помечено некоторой строкой. Терминальным вершинам ("листьям") соответствуют слова списка. В случае неудачи поиск возвращает термин словаря, совпадающий с искомым образцом в наибольшем числе начальных символов. Обычно trie -деревья используются для поиска по подстроке, но их можно использовать, и весьма эффективно, для поиска по сходству.

Метод trie-деревьев для поиска по сходству не включен в стандартные функции MySQL, а его реализация отдельным пользователем слишком трудоемка. Поэтому для метода trie-деревьев реализован программный proxy-уровень, работающий между СУБД MySQL и клиентскими приложениями, осуществляющий парсинг и оптимизацию запросов, содержащих операцию нестрогого равенства. Для этого создан программный proxyуровень, являющийся клиентом по отношению к серверу MySQL и сервером по отношению к клиентам, отправляющим запросы к базе данных [4].

Оператор нестрого равенства разработан как дополнение к уже существующим операторам сравнения SQL.

Синтаксис оператора нестрогого равенства:

имя _ таблицы _ А.имя _ поля _ а1 n (2) имя _ таблицы _ В.имя _ поля _ b1, где n – расстояние Левенштейна.

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

Если оператор нестрогого равенства не выявлен, то текст данного блока будет сохранен без изменений для последующей отправки к системе управления базами данных. Таким способом была сохранена возможность использования в системе стандартных SQL-запросов.

Если оператор нестрогого равенства выявляется, то при помощи лексического анализа в тексте блока выявляется необходимая для операции нестрогого соединения информация: имена таблиц, полей, значение заданного пользователем расстояния Левенштейна. Далее эти данные передаются в оптимизатор, где принимается решение о наилучшем способе построения таблицы с похожими парами строк указанных полей. После построения такой таблицы текст блока необходимо изменить так, чтобы он соответствовал синтаксису SQL.

Пусть парсер получает запрос:

SELECT A.line1, B.line2 (3) from A, B where A.line1 1 B.line2

Запрос, который будет отослан СУБД, будет таким:

–  –  –

Пусть задана последовательность S s1, s2,...,s S (5) из S элементов.

q-граммой называется любая подпоследовательность последовательности S из q подряд идущих элементов: S si, si 1,...,si q (6). Т.е. если две последовательности похожи, то у них должны быть какие-либо общие подпоследовательности. Данный метод основан на предположении, что при малых искажениях последовательности, т.е. слова, должны обладать достаточным количеством общих q-грамм. Основной недостаток метода q-грамм

– относительно большой объем дискового пространства, необходимый для хранения грамм. Однако данный недостаток компенсируется точностью поиска.

Для реализация метода q-грамм в СУБД MySQL используются SQLзапросы.

Реализация метода включает следующие этапы:

Создание специальной таблицы, в которой будут находиться qграммы для таблицы исходных данных.

В виде запроса данная операция будет выглядеть следующим образом:

–  –  –

Функция upper преобразует все символы аргумента к верхнему регистру. Функции substr и concat присоединяют символы # и % к первым и последним q-граммам аргумента соответственно. Функция char_lenght подсчитывает символы и возвращает длину строки-аргумента.

В таблице an.i содержатся числа от 1 до n, где n – максимальная длина записи в таблицах d1 и d2.

Выполнение нестрогого соединения таблиц. Из таблиц выбираются 3.

только те данные, у которых есть достаточное количество общих q-грамм.

Для определения степени близости строковых значений используется расстояние Левенштейна.

Запрос на нестрогое соединение таблиц d1 и d2 будет выглядеть следующим образом:

–  –  –

4. Сравнение методов Для сравнения работы метода q-грамм и trie-деревьев были выбраны таблицы с фамилиями из телефонного справочника 2008. Сравнение производилось сначала для таблиц с различающимися записями, а затем для таблиц и их копий. Тестирование проводилось на таблицах различного размера (100, 250, 500, 750, 1000 элементов) для расстояния Левенштейна, равного 1 и 2.

В результате тестирования получены следующие данные:

Для таблиц с различающимися записями

–  –  –

Рис. 4. Сравнение времени выполнения запроса нестрогого соединения методом trie-деревьев и q-грамм для расстояния Левенштейна = 2:

5. Результаты

Среди полученных результатов необходимо выделить следующее:

1. Реализована операция нестрогого соединения таблиц в СУБД MySQL с помощью метода trie-деревьев и q-грамм.

2. В ходе проведенного тестирования и анализа результатов времени выполнения запросов можно сделать вывод о том, что метод trie-деревьев, встроенный в proxy-уровень, при работе с таблицами с различающимися данными, работает быстрее, чем метод q-грамм, особенно при тестировании таблиц с большим количеством записей. При работе с таблицами и их копиями в таблицах с небольшим количеством записей метод q-грамм работает быстрее, но по мере увеличения количества записей в таблицах он теряет свою эффективность как для соединения с расстоянием Левенштейна, равным 1, так и с расстоянием Левенштейна, равным 2.





3. Подтверждена эффективность применения метода trie-деревьев в алгоритме нестрогого соединения таблиц по сравнению с методом q-грамм, особенно при тестировании таблиц с большим количеством записей.

Хотя метод q-грамм достаточно просто реализовать с нуля с помощью SQL-запросов, для метода trie-деревьев необходимо реализовать специализированное программное обеспечение, включающее архитектуру “клиент-сервер”.

Список литературы Погодаев А.К., Федоркова Г.О. Нестрогое соединение реляционных 1.

таблиц: хеширование по сигнатуре // Системы управления и информационные технологии, 2005, №2(19), с. 93-95.

2. L. Gravano, P. Ipeirotis, H. V. Jagadish, N. Koudas, S. Muthukrishnan, L.

Pietarinen, D. Srivastava Using q-grams in a DBMS for Approximate String Processing// IEEE Data Engineering Bulletin, 2001, №4, p. 4-6.

Погодаев А.К., Федоркова Г.О. Нестрогое соединение реляционных 3.

таблиц: использование trie-деревьев // Системы управления и информационные технологии, 2010, №3, с. 40-44.

Грачев Е.Р., Федоркова Г.О. Нестрогое реляционное соединение таблиц 4.

при помощи trie-деревьев // ВНТИЦ, 2010, №50201150648, с. 3-5.

Опубликовано: Системы управления и информационные технологии, 2012,

Похожие работы:

«5. Машины непрерывного механического транспорта 5.1. Общие понятия и определения Транспортирующими машинами непрерывного действия называют машины, которые перемещают насыпные или штучные грузы непрерывным потоком. От других видов транспорта они отличаются фиксированной в пространстве траекторией пер...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ НАУЧНОЯДЕРНАЯ ИЗВЕСТИЯ ТЕХНИЧЕСКИЙ ЖУРНАЛ ВЫСШИХ Издается в Университете ЭНЕРГЕТИКА УЧЕБНЫХ атомной энергетики с 1993 г. ЗАВЕДЕНИЙ N4 ОБНИНСК•2004 СОДЕРЖАНИЕ АКТУАЛЬНЫЕ Е.В. Федорова, Т.Г. Зорина ПРОБЛЕМЫ Моделирование межрегионального энергообмена с помощью программы ЯДЕ...»

«АКАДЕМИЯ УПРАВЛЕНИЯ ПРИ ПРЕЗИДЕНТЕ РЕСПУБЛИКИ БЕЛАРУСЬ УТВЕРЖДЕНО Проректором по учебной работе 18.06.2010 Регистрационный № УД-09.Пп/уч. УЧЕБНАЯ ПРОГРАММА ПО ДИСЦИПЛИНЕ Механизмы антикризисного управления организа...»

«Наименование учебного курса Физиологические механизмы нарушенных функций Физиология – наука о физиологических явлениях в живой природе. Этот учебный предмет является одним из основных при подготовке специалистов в области адаптивной физической культуры и сп...»

«МАСТЕРА АРХИТЕКТУРЫ О. А. ЧЕКАНОВА, А. Л. РОТАЧ ОгюстМОНФЕРРАН ЛЕНИНГРАД СТРОЙИЗДАТ ЛЕНИНГРАДСКОЕ ОТДЕЛЕНИЕ УДК 72 (47 + 57) (092) Ротач А. Л., Чеканова О. А. Огюст Монферран. — Л.: Стройиздат. Ленингр. отд-ние, 1990. —...»

«Cодержание 1. Общие указания............................ 2 2. Функциональные характеристики прибора.............. 2 3. Описание прибора............................ 2 4. Технические данные........................... 2 Инструкция по эксплуата...»

«Добрицкая Екатерина Михайловна ПОНИМАНИЕ ЦИВИЛИЗОВАННОСТИ И ВАРВАРСТВА В МИРОВОЗЗРЕНИИ ДРЕВНЕГО КИТАЯ: ДОКОНФУЦИАНСКАЯ И КОНФУЦИАНСКАЯ МОДЕЛИ ЧЕЛОВЕКА И МИРА 24.00.01 – теория и история культуры АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата философских наук Томск – 2009 Работа выполнена на кафедре культурологии и соц...»

«Краткое руководство по установке 00825-0207-4420, ред. GA июнь 2016 г. Беспроводной шлюз 1420 июнь 2016 г. Краткое руководство по установке ПРИМЕЧАНИЕ В данном руководстве представлены общие указания по интеллектуальному беспроводному шлюзу. В нем не приводятся инструкции по диагностике, техническому обслуживанию, эксп...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РООСИЙСКОЙ ФЕДЕРАЦИИ КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ АРХИТЕКТУРНОСТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ Кафедра оснований, фундаментов, динамики сооружений и инженерной геологии ИСПОЛЬЗОВАНИЕ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ПРИ ИЗУЧЕНИИ ДИСЦИПЛИН "ИНЖЕНЕРНАЯ ГЕОЛОГИЯ", "МЕХАНИКА ГРУНТОВ", "О...»








 
2017 www.ne.knigi-x.ru - «Бесплатная электронная библиотека - электронные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.