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

На правах рукописи

КОЛЕСОВ ДМИТРИЙ АЛЕКСАНДРОВИЧ

ПРИБЛИЖЕННЫЙ ПОИСК В БАЗАХ ДАННЫХ НА ОСНОВЕ МЕТРИЧЕСКИХ ДЕРЕВЬЕВ

05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Казань 2006

Диссертация выполнена в Институте проблем информатики Академии наук Республики Татарстан.

Научный руководитель доктор технических наук, профессор

Песошин Валерий Андреевич

Официальные оппоненты: доктор физико-математических наук,

профессор Елизаров Александр Михайлович

доктор технических наук, профессор Емалетдинова Лилия Юнеровна

Ведущая организация Марийский государственный технический

университет

Защита состоится «2> ®» Я 2006 г. в / Ц часов на заседании

диссертационного совета Д 212.079.01 в Казанском государственном техническом университете им. А. Н. Туполева по адресу: 420111, г. Казань, ул. К. Маркса, д. 10, зал заседаний ученого совета.

С диссертацией можно ознакомиться в библиотеке Казанского государственного технического университета им. А. Н. Туполева.

Автореферат разослан «"2Я~ » Я 2006 г.

Ученый секретарь диссертационного совета доктор физ.-мат. наук, профессор

Данилаев П.Г.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

мали в своих работах Р. Баеза-Ятс, В. Буркхард, С. Ву, В. Гунто, Р. Келлер, У. Манбер, Г. Наварро, П. Янипос и др.

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

Достижение поставленной цели требует решения следующих задач:

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

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

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

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

Научная новизна работы заключается в следующем:

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

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

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

Практическая ценность диссертационной работы заключается в том, что:

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на Всероссийском семинаре «Информационные технологии и методическое обеспечение поисковых работ» (Казань, 2003), 2-ой ежегодной международной научно-практической конференции «Йнфоком-муникационные технологии глобального информационного общества» (Казань, 2004), Межрегиональной научно-практической конференции «Источники по истории Казани» (Казань, 2004), 9-ой национальной конференции по искусственному интеллекту (Тверь, 2004), Межрегиональной научно-практической конференции «Поисковое движение: проблемы и перспективы» (Глазов, 2004), Всероссийской научно-практической конференции «Поисковое движение как форма изучения событий Великой Отечественной войны» (Курск, 2005).

Публикации. Основное содержание диссертационной работы опубликовано в 8 печатных работах.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав и заключения. Работа содержит 142 страницы машинописного текста, включая 35 рисунков, 3 приложения и список литературы из 62 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе рассматривается задача приближенного поиска в метрическом пространстве. Пусть задан произвольный элемент q метрического пространства (U, d). Требуется найти все элементы множества U, отстоящие от q не далее, чем на г, т.е. найти такие и из U, что

diu, q)<r, (1)

где г — радиус поиска.

Проведен обзор основных алгоритмов индексации при приближенном поиске в метрическом пространстве: это различные модификации алгоритмов ВКТ и BST, а также алгоритмов, основанных на построении диаграммы Вороного. В качестве примера здесь можно привести способ построения индексного дерева при помощи алгоритма FHQT. Этот алгоритм строит дерево высотой к так, что элементы множества U в конечном итоге приписываются некоторому листу дерева. Согласно этому алгоритму дерево строится следующим образом: заранее выбирается к узлов - (р;,..., р*)- Тогда каждому

элементу и из множества и можно поставить в соответствие А-мерный вектор: Уи={г/()},,и), <Цр2,и),..., (1(рл,и)}. Элемент и из и можно поместить на дерево, пользуясь координатами вектора.

Пусть, например, задано множество, состоящее из четырех элементов и={Л,В,С,0) • и пусть выбрано, к примеру, два произвольных элемента р\=й, Р:=С. Эти элементы называют узлами и используют при построении дерева. Пусть, кроме того, заданы расстояния между элементами и узлами: с/(р/А)= 1, <1(р,,В)= с1(р,,С)=2, ¿(р>И)= ¿(рг„Н)=3, с/(А,В)=1. Тогда векторы, соответствующие элементам множества и, будут равны г>/1={1,3}, уи={2,3}, уг={2,0}, ^,= {0,2}. —

Построенное по этим векторам дерево изображено на рис.1.

Во время поиска решений задачи (1) алгоритм просматривает лишь те ветви, для которых выполняется условие )т-11(рд)\<г, где т — метка ветви, р — узел, соответствующий текущей вершине дерева.

Рассмотрено обобщение алгоритмов приближенного поиска'. В обобщающей модели утверждается, что все алгоритмы поиска неявным образом задают на множестве и отношение эквивалентности, индуцируемое узлами (центрами) индексирования. Это отношение позволяет алгоритму поиска исключить из рассмотрения сразу целые классы эквивалентности, а оставшиеся классы приходится просматривать полным перебором. В случае индексных деревьев, классами эквивалентности будут листья построенного дерева. Например, для вышеприведенного примера получаем четыре класса эквивалентности: {Л}, {Д}, {С}, и {О}.

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

Для алгоритмов ВКТ и В5Т гистограмма расстояний позволяет опреде-

' Edgar Chavez, (ionzalo Navarro, Ricardo A. Baeza-Yates, and Jose L. Marroquin Searching in mctric spaces // ACM Computing Surveys, 33(3), 2(XM. -p.273-321.

лить качество узла еще на этапе построения индексного дерева. Схема выбора «хороших» узлов в данном случае является очень простой, поскольку она основана на полном переборе.

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

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

В рамках этого подхода было дано следующее определение: Определение 2.1. Пусть |[н]/>1...л<| — количество элементов, лежащих в классе эквивалентности, определяемом узлами р1г ..., рк и элементом и. Тогда величину

tteU

назовем суммарной ценой поиска, соответствующей набору узловpt, ...,рк..

Была сформулирована гипотеза о том, что суммарная цена поиска является величиной, характеризующей качество набора узлов индексирования: Гипотеза 1. Пусть у нас есть два набора узлов ръ ..., рк и ..., f.„ разбивающие множество U на различные наборы классов эквивалентности. Тогда набор узлов plt ..., рк даст возможность построить в среднем более эффективное индексное дерево, если его суммарная цена поиска меньше:

ZlMPl..,J<ZlM,..J

иЛГ пе{/

Величину суммарной цены поиска можно заменить более удобным для работы соотношением. Действительно, если на множестве U задан только один узел индексирования р,, то с каждым классом эквивалентности в U связано значение гистограммы на данном классе: gPl'=^[u]Pl Если же на

множестве U задано два узла рг и рг, то с каждым классом эквивалентности связано две гистограммы (рис. 2). Следовательно, число элементов, лежащих в классе эквивалентности [и]Р1Р2 не может превышать наименьшего из значений g и g .

u

Рис. 2. Гистограммы, соответствующие классам эквивалентности.

Аналогично, в случае, когда задано к узлов,' получаем следующее ограничение C(pi,...,pk) на величину суммарной цены поиска:

С(р{,...,рг) = £min(£ft(U),gft (и),..., gpДи)) к £ | [«]ЛЛ

Ißu US/

здесь символ g„ означает гистограмму расстояний, построенную относительно узлар, т.е. gp(u) = ||и]р|.

Нужно отметить, что C(plt ..., pt) является точной верхней гранью, например, в случаеpi =... = рК имеем, что С (р,.....Рг) = £)[«]„, |.

Таким образом, задача выбора качественного набора узлов индексирования р,, ..., рк сводится к выбору такого набора узлов, чтобы значение величины C(ph ..., pt) обращалось в минимальное из всех возможных. Определение 2.2. Символом С* будем обозначать наименьшую суммарную цену поиска при количестве узлов, равном s, т.е.

Тогда величину Cs* назовем оптимальной ценой поиска уровня s, а набор узлов р,, ..., ps, при котором достигается эта величина - оптимальным набором уровня s.

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

Теорема 2.1. Пусть С'„_х - С(а,■■•/>„_,) и пусть задан узелрт такой, что

fcf MiV ••/>■_) J

Тогда

Эта теорема показывает, как получить оптимальный набор узлов т-то уровня, если известен оптимальный набор узлов (m — 1)-го уровня. Но остается вопрос о том, как будет меняться величина С* при увеличении количества используемых узлов индексирования. Поведение оптимальной цены поиска уровня s при добавлении в набор узлов дополнительного узла описывают следующие две теоремы.

Теорема 2.2. Если С/л-1 то Cm_i - cm+s Для любого

Теорема 2.3. С*_, - С* г С* -С*+1. Таким образом, было получено следующее

Утверждение: Пусть имеется оптимальный набор узлов ти-ro уровня: Pi,---tPm- Вводя в рассмотрение новый узел (т.е. переходя от оптимального

набора т-то уровня к оптимальному набору (от + 1)-го уровня), мы будем получать все меньший и меньший эффект от процедуры добавления нового узла (теорема 2.3). Наконец, наступает такой момент, когда добавление нового узла эффекта уже не приносит (теорема 2.2).

Из гипотезы 1, теорем 1, 2 и 3 получаем итерационную процедуру выбора оптимального набора, состоящего из к узлов:

1. Выбираем узел р\ такой, что

С(р,)-ттС(0-С,\

(О/

2. Пусть выбраны узлы ръ ...,ртЛ. Тогда узел рт выберем так, чтобы

с'т - С(р1,...,рт_1,рт) = {тпС(ри...,рт_1,1).

13/

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

Приведены результаты экспериментальной проверки гипотезы и экспериментального сравнения алгоритмов выбора узлов. Установлено, что варьируя наборы узлов с целью минимизации величины С(ръ ,.., рк), мы одновременно увеличиваем эффективность отбора элементов. Таким образом, экспериментальные данные не противоречат гипотезе.

Проведено сравнение средней скорости поиска по индексным деревьям, построенным при использовании различных стратегий выбора'узлов (случайной и итерационной). Рассматривалось два крайних случая:

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

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

Экспериментальные данные для первого случая показаны на рис, 3,

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

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

мума скорости поиска при меньшем числе узлов.

Рис. 3. Сравнение средней эффективности для различных стратегий выбора узлов.

На рис. 4 приведен пример того, как скорость поиска по дереву зависит от числа узлов К и способа их выбора. Скорость оценивалась по сумме среднего числа переходов между вершинами дерева и количества вычислений метрики (сумма обозначена на графике символом Т).

о -,-,-,-

0 « 10 15 К

[—<—Игарвц. —■—Случ |

Рис.4. Оценка среднего времени поиска с использованием индексных деревьев, построенных, на различных наборах узлов

Как видно из рисунка, с увеличением числа узлов время поиска резко падает, а потом медленно возрастает. Число узлов, при котором достигается минимум, зависит: от отношения времени, необходимого для вычисления расстояний на множестве I/, ко времени перехода между вершинами дерева; от количества элементов во множестве £/; от размерности пространства.

Таким образом, использование итерационной процедуры выбора позволяет построить такое индексное дерево, которое при фиксированном объеме используемой памяти имеет меньшее среднее время поиска или при заданном среднем времени поиска использует меньший объем памяти.

Рассмотрена зависимость эффективности Е от радиуса поиска (см. соотношение (1)), полученные результаты приведены на рис. 5.

□ а « и ао га за зз «

Итердц --—Случ |

Рис.5. Зависимость эффективности Е от радиуса поиска г.

Как видно из графиков, зависимости имеют минимальные различия в поведении. Это позволяет производить сравнение алгоритмов выбора узлов при фиксированном параметре г.

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

Пусть БД имеет поля р\ Р2,..., I7™ и на каждом поле задана метрика <1\ (I2,..., сГ. Выберем среди значений каждого поля несколько узлов индексирования: для поля Рх это будут узлы р], р\,...,р\,, для поля Р2 - узлы

2 2 2 1п /п м

Р\ , Р2 ,--,Рк2, и так далее. Наконец, для поля Р" - узлы Р\ , Рг,...,Рк„.

Тогда значения, лежащие в поле Р БД, можно отобразить в пространство Як' следующим образом. Пусть и - значение поля Р некоторой записи. Найдем расстояние от этого значения до каждого из узлов поля. Полученные значения метрик (¿(и, р\(и,р\),..будут координатами точки пространства Р, соответствующей значению и (считаем, что Р - подпространство И", где 5 = кI + к2 + ... + к„). Проделав эту операцию для каждого поля, получим координаты пространства И4, соответствующие всей записи БД:

Таким образом, получено отображение БД в координатное пространство Я'1: каждой 'записи БД соответствует- единственная точка пространства Я'. Представим теперь, что значение поля Р'какой-либо записи отсутствует. Это означает, что значение данного поля у этой записи может принимать любые

значения из некоторого допустимого интервала. Тогда этой записи будет соответствовать в пространстве Я5 не точка, а -мерная плоскость, параллельная координатным осям (или ¿¡-мерный параллелепипед, если интервал допустимых значений ограничен).

При запросе на приближенный поиск к БД мы получаем от пользователя эталон q = ((¡¡, д2, ... , (],„) - значения полей записей БД и г = {гь г2, ... , г„} — радиусы поиска, т.е. значения допустимых отклонений записей от эталона. Нам нужно найги все записи БД, для которых выполняется система неравенств:

¿и1лд<г1ЖГ2,Ч2)<Гг,-ЖГ,<1т)<гт, (2)

где / значение поля 1<* текущей записи БД.

Эталон д отображается в точку <7 пространства Я", следовательно, вектор расстояний г и точка Ч задают в пространстве в-мерный параллелепипед ^(Ч'1-) лежащий в пространстве Я* (рис. 6).

Легко показать, пользуясь правилом треугольника, что запросу не могут удовлетворять следующие объекты пространства Я5: точки, не лежащие внутри параллелепипеда ^(4>т); прямые, плоскости, А-мерные плоскости и т.п., не пересекающие параллелепипед.

ИСР2.и2) А

<ЦрЭ.иЭ)

и;

Р1 п РЗ

(11 112 113

(21

и

А.

П Р2 РЗ

Г11 112 (13

(21 (23

Рис. 6. Пример отображения записей БД в пространство Я* и интерпретация запроса пользователя к БД как Р(ц,г).

Рассмотрено применение алгоритмов индексирования. Показано, что для построения индексного дерева, используемого для хранения объектов, лежащих в пространстве Я®, лучше всего подойдет алгоритм РНО'Г, поскольку он работает с постоянным набором узлов, общим для всего дерева. Предложена адаптация этого алгоритма к случаю индексации объектов пространства Я".

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

Для построения функций, описывающих степень сходства' данных, сначала на множестве данных задается метрика, позволяющая измерять1 «расстояния» между различными элементами множества. После этого по результатам опроса экспертов, оценивающих степень сходства между различными элементами множества, строится лингвистическая переменная, отражающая степень схожести данных.

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

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

Теорема 3.1. Обозначим при помощи величины метрику Левен-

штейна, а величиной II II — длину строки 5,. Тогда функция

Г(с , у т

,('Ма)-»«{||.1у.а||> ()

является метрикой.

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

Функции принадлежности термов полученной лингвистической переменной приведены на рис. 7.

1,2 — --------------------------------—......................................—...........—........................—■

0,9 0.0 ---*

\ / X/ \ .V

\

1 } ужу1

к

0,1 0,2 0,3 0,4 0,5 0,6 0.7 0*8 0,9

строки совпадают 1 0,0357 0,0147 0 0 0 0 0 0 0

-«- почту! совпадают 0 1 0.3339 а,073 □.□136 0.0042 0.002 0 0 0

т ПОХОЖИ 0 а,звэ5 1 0,372В 0,2722 0,0716 0,0232 0,0229 0 0

и похожи и не гвхоэ»и □ 0,1058 0,7916 1 0,7510 0,395В 0,2136 0,0767 0 0

не псиожи а 0 0,1178 0.501В (1.661 4 0.В442 0,9205 0,9679 1 1

Рис.7. Функции принадлежности термов лингвистической переменной «схожесть строк», построенной при помощи метрики (3).

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

кой Отечественной войны.

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

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

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

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

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

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

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

местности.

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

В качестве примера рассмотрена БД, содержащая сведения о военнослужащих, погибших в Тосненском районе Ленинградской области. Для этой БД наибольшая скорость приближенного поиска достигается при следующем количестве узлов: поле «Фамилия» — четыре узла, поле «Имя» - семь узлов, поле «Отчество» - пять узлов. Узлы, используемые при индексации БД, выбирались согласно итерационной процедуре, рассмотренной в главе 2. Пример полученных зависимостей среднего времени выполнения запроса от количества узлов приведен на рис. 8.

аямимисоагмдмзт Фаютма гочш сопйдмт фамилии помоми

г ................................t ; t .......................

1Э5791Э5791 J ' '

MMnKiuytiM и пшмту]«« (14 шкнмигияМ

Рис.8. Зависимость среднего времени выполнения запроса от количества узлов индексирования в случае трех вариантов условий поиска.

Исследован вопрос о порядке расположения узлов, соответствующих различным полям БД. Экспериментально показано, что наибольшая скорость поиска по индексному дереву достигается в случае, когда узлы, соответствующие полям «Фамилия», «Имя» и «Отчество» располагаются у корня дерева, в средней части и в верхней части соответственно. В табл. приведены сводные данные о времени выполнения поиска по индексному дереву (БД, содержащая сведения о военнослужащих, погибших в Тосненском районе Ленинградской области) для различных комбинаций условий запроса. Данные получены на PC класса Pentium 1000Mg/128MB. Приведен пример, иллюстрирующий этапы выполнения запроса пользователя на приближенный поиск в БД: дефа-зификация нечетких множеств, описывающих запрос, отображение эталона в координатное пространство и процесс поиска по индексному дереву.

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

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

БД «эксгумация» останков, находящихся недалеко от места обнаружения медальона; поддержка индекса при добавлении и удалении записей в БД.

Таблица. Среднее время поиска при помощи индексного дерева для различных комбинаций условий запроса

Условие для поиекг фамилии Условие для поиска имени Условие для поиска отчества Время (с)

похожи- похожи похожи 1.42

похожи похожи почти совпадают 0.84

похожи похожи совпадают . 0.53

похожи почти совпадают похожи 0.44

похожи почти совпадают почти совпадают 0.25

похожи почти совпадают совпадают 0.19

похожи совпадают похожи 0.20

похожи совпадают почти совпадают 0.11

похожи совпадают совпадают 0.07

почти совпадают похожи похожи 0.38

почти совпадают похожи почти совпадают 0.19

почти совпадают похожи совпадают 0.14

почти совпадают почти совпадают похожи 0.10

почти совпадают почти совпадают почти совпадают 0.07

почти совпадают почти совпадают совпадают 0.03

почти совпадают совпадают похожи 0.05

почти совпадают совпадают ' почти совпадают 0.03

почти совпадают совпадают • совпадают 0.02

совпадают похожи ■' похожи 0.01

совпадают похожи почти совпадают 0.01

совпадают похожи совпадают 0.01

совпадают почти совпадают похожи 0.00

совпадают почти совпадают почти совпадают 0.00

совпадают почти совпадают совпадают 0.00

совпадают совпадают похожи 0.00

совпадают совпадают почти совпадают 0.00

совпадают совпадают совпадают 0.00

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

Реализация программного комплекса осуществлена с использованием ГИС Maplnfo, а для реализации СУБД использована система Delphi. Связь разработанных программ осуществляется при помощи СОМ-технологий.

Приведены примеры идентификации останков на основе созданной системы. Показаны основные принципы работы комплекса.

В первом примере при погибшем была обнаружена ложка с надписью «Бу-

тусов». В результате анализа информации, хранящейся в БД, и сопоставления полученных данных с электронной картой местности, где были найдены останки, выдвинуто предположение, что останки принадлежат Бутусову Павлу Павловичу, 1909 г. рождения, уроженцу Вологодской области Росятинского района Крутского сельсовета. Красноармейцу, связисту 641 стрелкового полка 165 стрелковой дивизии, убитому 19 февраля 1943 года в Ленинградской области Тосненском районе, у развилки ручья Безымянный и реки Лезна. Данный вывод является предварительным, поскольку для точной ' идентификации требуется наличие дополнительной архивной информации (в частности, именных списков потерь 14-й отдельной стрелковой бригады), сбор которой еще не завершен.

Во втором примере рассматривается санитарное захоронение, в котором находились останки 17-ти бойцов. При одном их них была найдена ложка с надписью «Власенко Т.У.». После проведенного анализа сделано предположение, что эти останки принадлежат Власенко Тихону Ульяновичу, 1914 г. рождения, уроженцу города Смоленска. Младшему лейтенанту, командиру стрелкового взвода 641 стрелкового полка 165 стрелковой дивизии, убитому 18 февраля 1943 года в Ленинградской области у отметки высоты 34,9. Как и ранее, данный вывод также является предварительным.

В третьем примере рассматривается госпитальное захоронение, обнаруженное в районе урочища Зенино Ленинградской области. В результате анализа количества останков, их местоположения, найденного при одном из погибших спичечного коробка (надпись «Емельянов Паня Коми АССР деревня Лозым») и архивных данных, удалось установить личность 108 человек. О личности остальных военнослужащих (их также около 100) можно сделать лишь предположения, которые возможно будет подтвердить или опровергнуть при дальнейшей работе по сбору архивных сведений.

Заключение содержит основные результаты диссертационной работы.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

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

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

Рассмотрен пример построения лингвистической переменной, отражающих степень сходства строковых данных по начертанию. Построенная лингвистическая переменная «схожесть строк» используются при индексировании БД для приближенного поиска и построения запросов к БД на языке, близком к естественному.

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

Основное'содержание диссертации опубликовано в следующих работах:

1. Колесов В.Н., Колесов Д.А., Коноплев А.Ю., Салахиев P.P. О создании информационной системы, автоматизирующей процесс установления личности военнослужащих, погибших в годы Великой Отечественной войны // Сборник материалов к Всероссийскому семинару «Информационные технологии и методическое обеспечение поисковых работ», Казань, Отечество, 2003.-С.63-67.

2. Колесов Д.А., Коноплев А.Ю. Об алгоритмизации процесса установления личности военнослужащих, погибших в годы Великой Отечественной войны. // Исследования по информатике. Вып. 6, Институт проблем информатики АН РТ, Казань: Отечество, 2003. -С.139-145.

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

4. Коноплев А.Ю. Колесов В.Н., Салахиев P.P., Колесов Д.А. Воинские захоронения на территории г. Казани: история возникновения и применение ГИС к решению проблемы их сохранности. // «Проблемы истории Казани: современный взгляд», Институт истории им. Ш.Марджани АН РТ, 2004. -С.469-480.

5. Колесов Д.А. Разработка алгоритма поиска искаженной строковой информации в базах данных // Тезисы докладов 2-ой ежегодной международной научно-практической конференции «Инфокоммуникационные технологии глобального информационного общества», Казань, Изд-во Каз.гос.техн. ун-та, 2004.-С. 186-187.

6. Колесов Д.А. Разработка алгоритма поиска информации в базах данных с использованием функции нечеткого сравнения строк // Труды девятой национальной конференции по искусственному интеллекту КИИ-2004. М.: Физмат-лит, 2004.-Том 1. - С.386-391.

7. Колесов Д.А., Нуриахметов P.P. О создании информационной системы МИНЦ «ОТЕЧЕСТВО» для сбора и хранения информации о погибших в годы Великой Отечественной войны военнослужащих // Поисковое движение: проблемы и перспективы. Материалы межрегиональной научно-практической конференции, Глазов, 2005,- С.26-36.

8. Колесов Д.А. Этапы создания человеко-ориентируемого интерфейса к базам данных, хранящих информацию о погибших воинах // Материалы Всероссийской научно-практической конференции «Поисковое движение как форма изучения событий Великой Отечественной войны», Курск, Курский государственный университет, 2005. - С. 172-181.

Лицензия на полиграфическую деятельность №0128 от 08.06.98г. выдана Министерством информации и печати Республики Татарстан Подписано в печать 24.04.2006 г. Форм. бум. 60x84 1/16. Печ. л.1. Тираж 100. Заказ 125.

Минитипография института проблем информатики АН РТ 420012, Казань, ул.Чехова, 36.

Введение

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. Связь этих программ осуществляется при помощи СОМ-техиологпй. Обоснован выбор полей, используемых для индексации БД о погибших военнослужащих. Получены экспериментальные данные, отражающие зависимость среднего времени выполнения запроса на приближенный поиск фамилии (имени, отчества) от количества узлов индексирования. По данным эксперимента выбрано оптимальное количество узлов для каждого из нолей. Приведены примеры выполнения запроса к БД на приближенный поиск информации о военнослужащих и примеры идентификации останков погибших военнослужащих для различных типов захоронений (верховое залегание останков, санитарное захоронение и кладбище) на основе архивных сведений о погибших и накопленных данных, полученных в ходе нолевых экспедиций.

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.