Приближенный поиск в базах данных на основе метрических деревьев тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Колесов, Дмитрий Александрович

• Колесов, Дмитрий Александрович
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Колесов, Дмитрий Александрович

Введение

1 Приближенный поиск в метрическом пространстве

1.1 Понятие приближенного поиска

1.2 Приближенный поиск в метрических пространствах: обзор основных алгоритмов

1.3 Поиск в метрических пространствах: обобщающая модель

1.4 Выводы.

2 Выбор узловых точек, используемых для индексации

2.1 Применение гистограмм расстояний к оценке качества отдельно взятых узлов.

2.2 Применение гистограмм расстояний к оценке качества набора узлов в целом

2.3 Экспериментальная проверка.

2.3.1 Краткое описание эксперимента

2.3.2 Результаты эксперимента.

2.4 Выводы.

3 Модель приближенного поиска в БД

3.1 Отображение БД в координатное пространство.

3.2 Индексация пространства Ея для приближенного поиска . . G

3.3 Поиск в БД по нечетким критериям сходства.G

3.3.1 Основные понятия теории нечетких множеств.

Лингвистическая переменная.G

3.3.2 Построение лингвистической переменной «схожесть строк».

3.4 Выводы.

4 Применение приближенного поиска при идентификации останков погибших военнослужащих

4.1 Система идентификации останков военнослужащих.

4.1.1 Процесс идентификации останков военнослужащих

4.1.2 Исходные данные: анализ па полноту и достоверность

4.1.3 Требования, предъявляемые к информационной системе идентификации останков погибших воинов

4.2 Этап разработки геоииформациопиой системы.

4.2.1 Краткое описание возможностей ГИС.

4.2.2 Слои электронной карты для ГИС «Поисковые экспедиции».

4.2.3 Вопросы конкретной реализации

4.3 Индексация БД, содержащей сведения о погибших военнослужащих.

4.3.1 Выбор полей БД, участвующих в индексации для приближенного поиска.

4.3.2 Выбор узлов, используемых при построении индексного дерева.

4.3.3 Пример выполнения запроса пользователя па приближенный поиск в БД.

4.4 Примеры идентификации.

4.4.1 Характеристика района работ поисковой экспедиции «Любаиь».

4.4.2 Примеры идентификации.

4.5 Выводы.

Введение диссертации (часть автореферата) на тему «Приближенный поиск в базах данных на основе метрических деревьев»

Поиск различного рода информации является одной из самых распространенных задам, с которыми сталкивается программист в процессе работы. При этом поиск обычно является наиболее «времяемкой» частью многих программ, и замена плохого метода поиска хорошим может значительно увеличить скорость работы программы {27]. Исследованием задач, связанных с поиском серьезно начали заниматься в начале 50-х годов XX века, и первые обзоры (согласно [27]) по этой тематике были опубликованы А.И Думи (1956г.), В.В. Петерсопом (1957г.), Э.Д. Бутом (1958г.), А.Ш. Дугласом (1959г.).

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

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

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

Задача идентификации останков военнослужащих, погибших во время Второй Мировой войны, лежит на стыке нескольких отраслей знания, однако занимаются ей, в основном, специалисты гуманитарного профиля (в первую очередь, историки). Среди работ, посвященных данной тематике, следует отдельно отметить две монографии Садовиикова С.И [40| и Котилевского С.С. [24]. К сожалению, практически все работы, в которых рассматривается проблема поиска пропавших без вести в годы Второй Мировой войны, написаны с историко-архивиой точки зрения, и крупных работ, в которых описывалось бы применение информационных технологий для поисковых целей, нет. С другой стороны, в настоящее время в результате работы многих поисковых экспедиций накоплен большой объем информации о погибших, местах их гибели и местах захоронений, и требуется применение подхода, позволяющего оперативно обрабатывать накопленные данные.

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

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

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

Вопросами обработки нечеткой информации занимались такие исследователи, как А.Н. Аверкии, К. Асаи, И.З. Батыршип, Ж.К. Бездек, JI.C. Бсриштейи, А.Ф. Блиуши, А.Н. Борисов, JI.A. Заде, А. Коффмап, О.А. Крумберг., Н.Г. Малышев, Е.А. Мамдаии, Д.А. Поспелов, М. Сугсно, X. Таиаки, В.Б. Тарасов, Т. Тэрапо, И.П. Федоров, А. Хирота и др. Вопросы ускорения приближенного поиска данных поднимали в своих работах Р. Баеза-Ятес, В. Буркхард, С. By, В. Гупто, Р. Келлер, У. Мапбер, Г. Наварро, П. Яиилос и другие исследователи.

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

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

- увеличение средней скорости поиска алгоритмов приближенного поиска в метрическом пространстве за счет минимизации количества вычислений метрики при обходе дерева;

- разработка алгоритмов поиска символьной информации в БД е учетом ее возможной неточности;

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

Для решения поставленных задач использованы аппарат нечеткой логики, картографический метод исследования и методы вычислительной геометрии.

Основные результаты диссертации, имеющие научную новизну:

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

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

- Разработаны алгоритмы индексирования и поиска искаженной и неполной информации в БД.

Практическая ценность исследования:

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

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

Результаты нроведеииых исследований используются в ОМО «Объединение "ОТЕЧЕСТВО"», уполномоченной па ведение поисковой работы от имени Республики Татарстан постановлением Кабинета Министров РТ № G08 от 13.09.1999. Кроме того, полученные результаты использовались при работе по грантам НИОКР РТ № 05-5.2-219/2005 «Развитие инфраструктуры корпоративной сети и иптерпет-иортала в рамках домена antat.ru» и № 01-1.10-2G2/2004 «Воинские захоронения па территории Республики Татарстан: история их возникновения и проблемы сохранности».

На защиту выносятся:

- критерий качества выбора узлов индексирования при решении задачи приближенного поиска в метрическом пространстве и алгоритм-выбора-набора узлов, оптимальный по средней скорости поиска;

- алгоритм поиска искаженной символьной информации в БД; *

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

Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Колесов, Дмитрий Александрович

5 Выводы

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

2. Проведен анализ возможных путей создания системы идентификации останков и определены требования, предъявляемые к разрабатываемой системе.

3. Приводятся краткие сведения о возможностях ГИС, описываются особенности работы с электронными картами, и принципы их создания. Рассматривается процесс создания ГИС «Поисковые экспедиции», перечисляются слои карты, которые необходимо сформировать и описываются способы создания этих слоев.

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

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

Заключение

1. Рассмотрена задача приближенного поиска. Приводится обзор основных алгоритмов индексации метрического пространства для приближенного поиска.

2. Предложен новый подход к решению задачи выбора узлов индексации. Введено понятие суммарной цены поиска и выдвинута гипотеза, что эта величина характеризует степень эффективности набора узлов. Получено ограничение па величину суммарной цепы поиска, дающая возможность вычислить оптимальную цепу поиска уровня s. Доказаны теоремы, описывающие поведение оптимальной цены поиска уровня s при увеличении количества узлов, используемых при индексировании, и доказано, что для выбора оптимального набора узлов т-го уровня пе обязательно совершать полный перебор всех возможных комбинаций, состоящих из т узлов. Построена итерационная процедура выбора оптимального набора узлов m-го уровня. Экспериментальное сравнение различных процедур выбора узлов показало, что использование итерационной процедуры позволяет построить индексное дерево, которое при фиксированном объеме используемой памяти имеет меньшее среднее время поиска или при заданном среднем времени поиска использует меньший объем памяти.

3. Рассмотрена модель приближенного поиска в БД. Предложен подход, позволяющий адаптировать приближенный поиск в метрическом пространстве в приближенный поиск в БД, содержащей искаженную или неполную информацию. Показано, что если на полях БД, содержащей искаженную и неполную информацию, заданы метрики, то записи такой БД можно отобразить в s-мерпое координатное пространство Rs, причем эти записи будут являться либо точками этого пространства, либо некоторыми А;-мерпыми плоскостями. Запрос пользователя к БД индуцирует в пространстве Rs s-мерпый параллелепипед. Показано, что записи БД, которые отображаются в объекты пространства R,s, не пересекающиеся с параллелепипедом, не могут удовлетворять запросу пользователя. Предложен способ адаптации алгоритма приближенного поиска FHQT к поиску объектов пространства Rs, удовлетворяющих запросу пользователя к БД.

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

5. Рассмотрена схема идентификации останков погибших военнослужащих, применяемая поисковиками. Проведен анализ возможных путей создания человеко-машинной системы идентификации останков. Определены требования, предъявляемые к разрабатываемой системе. Создана система идентификации останков погибших военнослужащих — программный комплекс, представляющий собой набор взаимодействующих программ: СУБД, обеспечивающая работу с индексированной для приближенного поиска БД и ГИС «Поисковые экспедиции». Для реализации программного комплекса использована ГИС Maplnfo, а для реализации СУБД — система Delphi. Связь этих программ осуществляется при помощи СОМ-техиологпй. Обоснован выбор полей, используемых для индексации БД о погибших военнослужащих. Получены экспериментальные данные, отражающие зависимость среднего времени выполнения запроса на приближенный поиск фамилии (имени, отчества) от количества узлов индексирования. По данным эксперимента выбрано оптимальное количество узлов для каждого из нолей. Приведены примеры выполнения запроса к БД на приближенный поиск информации о военнослужащих и примеры идентификации останков погибших военнослужащих для различных типов захоронений (верховое залегание останков, санитарное захоронение и кладбище) на основе архивных сведений о погибших и накопленных данных, полученных в ходе нолевых экспедиций.

Список литературы диссертационного исследования кандидат технических наук Колесов, Дмитрий Александрович, 2006 год

1. Батырншн И.З. Основные операции нечеткой логики и их обобщений / И.З. Батырншн. -Казань: Отечество, 2001. -101с.

2. Берляит A.M. Геоинформационные технологии и их использование в эколого-географических исследованиях / A.M. Берляит, О.Р. Мусин, Ю.В.Свеитэк // География. -М.: Изд-во МГУ. -1993. -С.229-2СЗ.

3. Бойцов JI.M. Анализ строк. http://itmaii.iiarod.ru/articlcs/ infoscope/stringsearch. l-3.html

4. Бойцов JI.M. Современные поисковые системы: структуры данных и стратегии поиска. http://www.itman.narod.ru/ir/review/review.pdf

5. G. Борисов А.Н. Принятие решений па основе нечетких моделей: примеры использования / А.Н. Борисов, О.А. Крумберг, И.П. Федоров. -Рига: Зипатпе, 1990. -184с.

6. В походах за памятью. Казань: Книга Памяти. -1995. -208с.

7. Геоипформациоипые системы и методы их создания: учебное пособие. -М.: МИИГАиК, -1995. -164с.

8. Горелик A.JI. Методы распознавания: учеб. пособие для вузов / А.Л. Горелик, В.А. Скриикин. -М.: Высшая школа, 2004. -201с.

9. Елмапова Н. Delphi G и технология СОМ / Н. Елмаиова, С. Трепалип, А. Тепцер. -СПб.: ПИТЕР, 2002. 738с.

10. И. Заде Л.А. Понятие лингвистической переменной и его применение к принятию приближенных решений / Л.А. Заде. -М.:Мир, 197G.-lG5c.

11. Иванов А.А. Опыт информатизации процесса подготовки к изданию книги «Память» Республики Татарстан / А.А. Иванов, P.P. Салахисв, М.В. Черепанов // Исследования по информатике. Выи.1 Казань: Отечество, 1999. -С.41-44.

12. Ивлев И.И. Военная археология. Методика поисковых архивно-полевых исследований. / / http: / / otcchestvo.ipian.kazan.rn/METOD/003/ inain.htm

13. Кепту М. Delphi 7: Для профессионалов / М. Кенту СПб.: Питер, 2004.-1101с.

14. Колосов Д.А. Разработка алгоритма поиска искаженной строковой информации в базах данных // Тезисы докладов 2-ой ежегодной международной паучио-нрактической конференции Министерства связи РТ. -Казань: Изд-во Каз.гос.тсхп. ун-та, 2004. C.18G-187.

15. Колосов Д.А. Разработка алгоритма поиска информации в базах данных с использованием функции нечеткого сравнения строк / Д.А. Колосов // Исследования по информатике. Выи.7, Институт проблем информатики АН РТ. -Казань: Отечество, 2004. С. 125-132.

16. Коновалова Н.В. Введение в ГИС: учебное пособие / Н.В. Коновалова, Е.Г. Капралов. -М.: ООО «Библиоп», 1997. -160с.

17. Коиоплев АЛО. Об информатизации процесса увековечения памяти жертв войн и репрессий / А.Ю. Коиоплев, В.Н. Колосов, P.P. Салахиев // Исследования но информатике. Вып.1 -Казань: Отечество, 1999. -С.31-40.

18. Котилевский С.С. Теория и практика поисковых работ / С.С. Котилевский -Казань: Отечество, 2004. -230с.

19. Кошкарев А.В. Региональные геоинформациоппые системы /

20. A.В. Кошкарев, В.П. Каракин. -М.: Наука, 1987. -126с.

21. Кошкарев А.В. Гсоииформатика / А.В. Кошкарев, B.C. Тикунов. -М.: "Картгсоцснтр'-'Тсодсзиздат", 1993. 213с.

22. Кнут Д.Э. Искусство программирования: в Зт. Т.З. Сортировка и поиск / Д.Э. Кнут. -М.: Издательский дом «Вильяме», 2000. -832с.

23. Кофмап А. Введение в теорию нечетких множеств / А. Кофмап. -М.: Радио и связь, 1982.- 432с.

24. Круглов В.В. Нечеткая логика и искусственные нейронные сети /

25. B.В. Круглов, М.И. Дли. -М.: ФИЗМАТЛИТ, 2001. -224с.

26. Левснштсйн В.И. Двоичные коды с исправлением выпадений, вставок и замещений символов / В.И. Левснштсйн // Доклады АН СССР Т.163. -1965. -М -С.845-848.

27. Леонтьев В.А. Система электронных карт: пауч-иые основы, методы и технология / В.А. Леонтьев, А.И. Мартынепко // Геодезия и картография. -1996. -№7. -С.48-50.

28. Мюллер Д.П. Технология СОМ+: библиотека программиста / Д.П. Мюллер -СПб.: Питер, 2003. -400с.

29. Сассоли М. МККК и лица, пропавшие без вести / Марко Сассоли, Мари-Луиза Туга // Международный журнал Красного Креста: Пропавшие без вести. -М.: Международный Комитет Красного Креста, 2003. -208с.

30. Нечеткие множества в моделях управления и искусственного интеллекта / А.Н. Аверкип, И.З. Батыршин, А.Ф. Блиушп и др.; Под ред. Д.А. Поспелова. -М.: Наука, 1986.-311с.

31. Нечеткие множества и теория возможностей. Последние достижения/Под ред. P.P. Ягсра.-М.: Радио и связь, 1986.-408с.

32. Нуриахметов P.P. О применении информационных технологий для сбора информации по именным находкам поисковых экспедиций / P.P. Нуриахметов // Исследования ио информатике. Вып.9. 2005. -С.151-154.

33. Петров П.В. Система хранения и поиска картографической информации / П.В. Петров, Ю.В. Свептэк. -М.: Изд-во Моск. ун-та, 1987. С.105-113.

34. Препарата Ф. Вычислительная геометрия: Введение / Ф. Препарата, М. Шсймос. -М.: Мир, 1989. -480с.

35. Прикладные нечеткие системы / Под ред. Т.Терапо. -М.: Мир, 1993. -368с.

36. Садовников С.И. Поиск, ставший судьбой / С.И. Садовников -М.: 2003. -260с.

37. Тикуиов B.C. Современные средства исследования системы «общество природная среда»//Изв. АН ВГО, 1989.- Т. 21.- Выи. 4. -С.299-306.

38. Федюнииский И.И. Поднятые ио тревоге / Фсдюпинский И.И. —М.: Воепиздат, 1961. -248с.

39. Хеммипг Р.В. Теория кодирования и теория информации / Р.В. Хсммипг; Пер. с англ, иод ред. Б. С. Цыбакова. -М.: Радио и связь, 1983. -176с.

40. Цветков В.Я. Геоииформациониые системы и технологии / В.Я. Цветков. -М.: 1998. -288с.

41. Шайтура С.В. Геоинформационные системы и методы их создания / С.В. Шайтура. -Калуга: Изд-во Н. Бочкаревой, 1997. -253с.

42. R. Baeza-Yates Searching: an algorithmic tour // Enciclopedia of Computer Science and Technology, vol. 37, 1997. -P.331-359.

43. R. Baeza-Yates, W. Cunto, U. Manber S. Wu Proximity matching using fixed-queries trees // Proc. 5th Combinatorial Pattern Matching LNCS 807, 1994. -P.198-212.

44. W. Burkhard, R. Keller Some approaches to best-match file searching. // Comm. of the ACM 16(4), 1973. -P.230-236

45. E. Chavez, J. Marroquin, G. Navarro. Overcoming the curse of diincnsionaly. European workshop on Contest-Based Multimedia Indexing (CBMI-99) P.57-64,1999 // ftp://garota.fismat.umich.mx/pub/users/elchaves/fqa.i)s.gz

46. Т. Cox, M. Cox Multidimensional scaling // Chapman and Hall, 1994.

47. Dubois D., Prade H. Using Fuzzy Sets in Database Systems: Why and How? // Proc. of 1996 Workshop on Flexible Query-Answering systems, Denmark, May 22-24, 1996. -P.89-103.

48. Edgar Chavez, Gonzalo Navarro, Ricardo A. Baeza-Yates, and Jose L. Marroquin Searching in metric spaces // ACM Computing Surveys, 33(3), 2001, -P.273-321. http://citeseer.ist.psu.edu/avez99searching.html

49. Lober Douglas Resolving the siting iinpasse: Modelling social and environmental locational criteria with a geographic informations system // J. Amer. Plann. Assoc. 1995. - G1 N4. -P.482-495.

50. MapBasic — Среда разработки. Руководство пользователя. / Пер. с англ.- М.: Изд-во Эсти-М, 1995.-285с.

51. Maplnfo — Система настольной картографии. Руководство пользователя. / Пер. с англ.- М.: Изд-во Эстн-M, 1995.-3G8c.

52. GO. Norio Katayama The SR-tree: an index structure for high-dimentioiial nearest neigbour queries (http://citeseer.nj.com/G8737.htinl)

53. Gl. Ribeiro R.A., Moreira A.M. Fuzzy Query Interface for a Business Database // International Journal of Human-Computers Studies, Vol. 58 2003. -P.363-391.

54. G2. Zadeh, L.A.: Fuzzy Sets. Information and Control 8 1965. -P.338-353.