Содержание к диссертации
Введение
1 Приближенный поиск в метрическом пространстве 13
1.1 Понятие приближенного поиска 13
1.2 Приближенный поиск в метрических пространстпах: обзор основных алгоритмов 15
1.3 Поиск в метрических пространствах: обобщающая модель . 22
1.4 Выводы 26
2 Выбор узловых точек, используемых для индексации 27
2.1 Применение гистограмм расстояний к оценке качества отдельно взятых узлов 27
2.2 Применение гистограмм расстояний к оценке качества набора узлов в целом 30
2.3 Экспериментальная проверка 42
2.3.1 Краткое описание эксперимента 43
2.3.2 Результаты эксперимента 44
2.4 Выводы 55
3 Модель приближенного поиска в БД 57
3.1 Отображение БД в координатное пространство 57
3.2 Индексация пространства Ш.3 для приближенного поиска . G3
3.3 Поиск в БД по нечетким критериям сходства G8
3.3.1 Основные понятия теории нечетких множеств. Лингвистическая переменная G9
3.3.2 Построение лингвистической переменной «схожесть строк» 74
3.4 Выводы 80
4 Применение приближенного поиска при идентификации останков погибших военнослужащих 82
4.1 Система идентификации останков военнослужащих 82
4.1.1 Процесс идентификации останков военнослужащих . 82
4.1.2 Исходные данные: анализ на полноту и достоверность 87
4.1.3 Требования, предъявляемые к информационной системе идентификации останков погибших воинов . 90
4.2 Этап разработки геоииформациоиной системы 95
4.2.1 Краткое описание возможностей ГИС 95
4.2.2 Слои электронной карты для ГИС «Поисковые экспедиции» 98
4.2.3 Вопросы конкретной реализации 100
4.3 Индексация БД, содержащей сведения о погибших военнослужащих 104
4.3.1 Выбор полей БД, участвующих в индексации для приближенного поиска 104
4.3.2 Выбор узлов, используемых при построении индексного дерева 105
4.3.3 Пример выполнения запроса пользователи па приближенный поиск в БД 109
4.4 Примеры идентификации 112
4.4.1 Характеристика района работ поисковой экспедиции «Любань» 112
4.4.2 Примеры идентификации 117
4.5 Выводы 129
Заключение 130
Литература
- Приближенный поиск в метрических пространстпах: обзор основных алгоритмов
- Применение гистограмм расстояний к оценке качества набора узлов в целом
- Основные понятия теории нечетких множеств. Лингвистическая переменная
- Требования, предъявляемые к информационной системе идентификации останков погибших воинов
Введение к работе
Поиск различного рода информации является одной из самых распространенных задач, с которыми сталкивается программист и процессе работы. При этом поиск обычно яилиется наиболее «времяемкой» частыо многих программ, и замена плохого метода поиска хорошим может значительно увеличить скорость работы программы [27]. Исследованием задач, связанных с поиском серьезно начали заниматься в начале; 50-х годов XX века, и первые обзоры (согласно [27]) по этой тематике были опубликованы А.И Думи (1956г.), В.В. Петсрсопом (1957г.), Э.Д. Бутом (1958г.), А.Ш. Дугласом (1959г.).
Первоначально исследовалась задача так называемого точного поиска, когда поисковому алгоритму даются некоторый ключ и таблица элементов, каждый из которых также снабжен ключом, однозначно идентифицирующим элементы. Алгоритм производил в таблице поиск ключа, в точности совпадающего с заданным. Таким образом, результатом поиска мог быть только один из двух вариантов: уникальная запись, соответствующая ключу, найдена (поиск завершился удачно) или же запись по найдена (поиск оказался неудачным).
Распространенные в настоящее время базы данных (БД) и системы управления базами данных (СУБД) построены именно по этому принципу: каждая записі» снабжается ключом, и поиск производится по этому ключу (обычно числовое или строковое значение). Но в последние годы, с увеличением производительности компьютеров, появилась возможность хранить в базах данных информацию, отличную от чисел или строк, например, различного рода графические изображения,
звуко- и видеоматериалы. Расширяется класс задач, которые становится возможным решать, используя подобные данные (например, задача поиска аудиофайла, близкого но звучанию к заданному). Таким образом, с: появлением подобных БД приходит понимание того, что, используя только поиск на точное соответствие, становится сложно найти нужную информацию. Появляется потребность производить поиск значений по неточному сходству. Актуальность этой задачи подтверждается большим количеством публикаций, появившихся в последнее двадцатипятилетие и
-> посвященных тематике приближенного поиска.
Приближенный поиск применяется во многих практических задачах, от поиска информации в сети Интернет до поиска совпадающих цепочек в молекулах ДНК. Интересным приложением приближенного поиска является задача идентификации останков погибших военнослужащих.
Задача идентификации останков военнослужащих, погибших во время Второй Мировой войны, лежит на стыке нескольких отраслей знания,
^ однако занимаются ей, в основном, специалисты гуманитарного профиля
(в первую очередь, историки). Среди работ, посвященных данной тематике, еле/густ отдельно отметить две монографии Садовникова СИ [40] и Котилевского С.С. [24]. К сожалению, практически все работы, it которых рассматривается проблема поиска пропавших без вести в годы Второй Мировой войны, написаны с историко-архивиой точки зрения, и крупных работ, в которых описывалось бы применение информационных технологий
% для поисковых целей, пет. С другой стороны, в настоящее время в
результате работы многих поисковых экспедиций накоплен большой объем информации о погибших, местах их гибели и местах захоронений, и требуется применение подхода, позволяющего оперативно обрабатывать накопленные данные.
Те информационные технологии, которые применяются в поисковой
* работе {в основном, различного рода БД), не учитывают специфики
информации, которая используется при идентификации останков.
Во-первых, эта информация носит пространственный характер, и исследователь, занимающийся проблемами идентификации, должен знать характер местности, на которой были обнаружены останки, представлять взаимное расположение многих объектов и многое; другое. Во-вторых, данные, используемые для идентификации останков погибших военнослужащих, зачастую отличаются неполнотой и неточностью, поэтому их автоматическая обработка (поиск, сопоставление информации) сопряжена со значительными трудностями и требует особого подхода. Таким образом, изучение возможности применения информационных технологий к обработке архивных данных о погибших и данных поисковых экспедиций становится весьма актуальным.
Задача создания системы идентификации останков погибших военнослужащих является разноплановой — для создании подобной системы необходимо решить несколько мало связанных между собой подзадач (задача хранения и поиска информации с учетом се возможных искажений, задача визуализации пространственных данных, задача сопоставления архивных сведений и данных, полученных в ходе поисковых экспедиций). Основная часть диссертации опирается на методы нечеткой логики и методы вычислительной геометрии.
Вопросами обработки нечеткой информации занимались такие исследователи, как А.Н. Аверкин, К. Асаи, И.З. Батыршин, Ж.К. Бездек, Л.С. Бернштсйн, А.Ф. Блиупш, А.Н. Борисов, Л.А. Заде, А. Коффман, О.А. Крумберг., Н.Г. Малышев, Е.А. Мамдани, Д.А. Поспелов, М. Сугепо, X. Танаки, В.Б. Тарасов, Т. Тэрано, И.П. Федоров, А. Хирота и др. Вопросы ускорения приближенного поиска данных поднимали в своих работах Р. Баеза-Ятес, В. Буркхард, С. By, В. Гупто, Р. Келлер, У. Мапбер, Г. Наварро, П. Янилос и другие исследователи.
Основная цель исследования — повышение эффективности алгоритмов приближенного поиска и разработка алгоритма приближенного поиска в БД, хранящей искаженную и неполную информацию.
В соответствии с поставленной целью в диссертационной работе решались следующие задачи:
- увеличение средней скорости поиска алгоритмов приближенного
поиска в метрическом пространстве за счет минимизации количества
вычислений метрики при обходе дерева;
- разработка алгоритмов поиска символьной информации is БД с учетом
ее возможной неточности;
- реализация разработанных методов, моделей и алгоритмов на
примере приближенного поиска при идентификации останков погибших
военнослужащих.
Для решения поставленных задач использованы аппарат нечеткой логики, картографический метод исследования и методы вычислительной геометрии.
Основные результаты диссертации, имеющие научную новизну:
- Построен критерий качества выбора узлов индексирования при
решении задачи приближенного поиска в метрическом пространстве и
исследован эффект от добавления нового узла в существующий набор
узлов.
Построена итерационная процедура выбора набора узлов индексирования при приближенном поиске в метрическом пространстве, позволяющая построить более эффективное индексное дерево, чем при случайном выборе узлов.
- Разработаны алгоритмы индексирования и поиска искаженной и
неполной информации в БД.
Практическая ценность исследования:
разработана структура информационной системы, позволяющая частично автоматизировать процесс идентификации останков погибших военнослужащих;
разработаны библиотеки модулей индексации БД для поиска по нечетко заданным критериям сходства и библиотеки, реализующие
функции, строящие нечеткие множества, отражающие степень сходства данных;
разработан программный комплекс, реализующий алгоритм идентификации останков погибших военнослужащих.
Результаты проведенных исследований используются в О МО
«Объединение "ОТЕЧЕСТВОМ, уполномоченной па ведение поисковой
работы от имени Республики Татарстан постановлением Кабинета
Министров РТ № С08 от 13.09.1999. Кроме того, полученные результаты
^ использовались при работе по грантам НИОКР РТ № 05-5.2-219/2003
«Развитие инфраструктуры корпоративной сети и интернет-портала в рамках домена antat.m» и № 01-1.10-2G2/2004 «Воинские захоронения на территории Республики Татарстан: история их возникновения и проблемы сохранности».
На защиту выносятся:
- критерий качества выбора узлов индексирования при решении задачи
(ф приближенного поиска в метрическом пространстве и алгоритм- выбора'
набора узлов, оптимальный по средней скорости поиска;
- алгоритм поиска искаженной символьной информации и БД;
- результаты экспериментальных исследовании скорости поиска при
помощи индексных деревьев, построенных с использованием двух процедур
выбора узлов (итерационной и случайной).
Диссертация состоит из введения, четырех глав, заключения, списка
щ литературы и приложений,
Во введении обосновывается актуальность темы диссертации, формулируются цель и задачи исследования, приводится перечень основных результатов, выносимых на защиту,
В первой главе «Приблиоюенпый поиск в метрическом проегпраисве»
задача приближенного поиска в БД рассматривается более абстрактно -
** как задача приближенного поиска в метрическом пространстве. Известно
множество алгоритмов, предназначенных для решения этой задачи;
в начале главы приводится обзор основных алгоритмов индексации
, при приближенном поиске в метрическом пространстве: это различные
модификации алгоритмов ВКТ и BST, а также алгоритмов, основанных па построении диаграммы Вороного [49, 47, 56, 52, 54]. Кратко описывается обобщение этих алгоритмов [54]. Известно, что все существующие па сегодняшний день алгоритмы приближенного поиска укладываются и приведенную обобщающую модель.
Во второй главе «Выбор узловых точек, используемых для индексации»
(Лі
^ исследуется вопрос о повышении скорости поиска информации
по индексному дереву. Как известно, качество работы алгоритмов индексирования в большой степени зависит от набора узлов (центров) индексации — один и тот же алгоритм может дать в корне различающуюся скорость сходимости для двух разных наборов узлов. Тем не менее, вопрос выбора узлов мало освещен в литературе.
В диссертационной работе был предложен пошли подход к проблеме
ґ* выбора узлов: здесь исследовалось качество не отдельных узлов
индексирования, а их совокупностей. Подход опирается па обобщающую
модель, поэтому ого можно будет применить к любому алгоритму
индексирования.
В рамках этого подхода было введено понятие суммарной цены поиска,
соответствующей набору узлов. Была сформулирована гипотеза о том, что
суммарная цена поиска является величиной, характеризующей качество
* набора узлов индексирования (Гипотеза 2.1).
Получено ограничение па величину суммарной цены поиска и введено понятие оптимальной цены поиска при количество узлов, равном s (оптимальная цена s-того уровня). Доказано, что для построения оптимального набора узлов s-того уровня не обязательно совершать полный перебор всех возможных комбинаций из s узлов (Теорема 2.1). Исследован вопрос о поведении оптимального набора узлов т-того уровня при добавлении в набор еще одного узла (Утверждение 2Л). Это
утверждение и теорема 2,1 дают возможность построить схему выбора
f оптимального набора узлов.
Проведена экспериментальная проверка гипотезы и результатов, полученных на се основе. Показано преимущество предложенной процедуры выбора узлов.
В главе третьей «Модель приблио/сенноео поиска о БД» предлооїсси
подходу который позволяет адаптировать конструкции, производящие
приближенный поиск и метрическом пространстве, к случаю
'* приближенного поиска и БД, содержащей искаженную или неполную
информацию.
Прежде всего было показано, как можно произвести отображение исходной БД в 8-мерное координатное пространство Ш8 таким образом, чтобы близкие записи БД отображались в близкие точки пространства.
Был рассмотрен вопрос о том, что будет происходить, когда
пользователь делает запрос на приближенный поиск к БД. Показано, что
(4 такой запрос индуцирует в Ж8 некоторый 5-мерный параллелепипед P{q, г).
Показано, каким образом можно применить алгоритмы индексирования, рассмотренные выше, для индексации этих объектов. При построении дерева для индексации объектов, лежащих в пространстве К*, лучше всего подойдет алгоритм FHQT. Предложена адаптация этого алгоритма к случаю индексации объектов пространства К*.
Далее на примере строковых полей БД обсуждалась методика
* задания метрики, пригодной для использования при построении нечетких
критериев сходства данных. Эта метрика использована при создании
человеко-ориептирусмого интерфейса для работы с БД.
Приближенный поиск в метрических пространстпах: обзор основных алгоритмов
Другими словами, мы считаем, что па множестве U задана метрика, при помощи которой мы определяем степень близости элементов этого ; , множества. Метрическое пространство, задаваемое на множестве U метрикой d, в дальнейшем будем обозначать парой (U7d), Используя понятие метрики, исходную задачу приближенного поиска можно сформулировать следующим образом: пусть задан произвольный элемент q. Требуется найти все элементы множества V, отстоящие от q по далее, чем на г, те. найти такие и Є /, что d(u,q) r, (1Л) где г 0 — радиус поиска. Для сокращения записи в дальнейшем эту задачу будем обозначать как (q,r)d.
Попятно, что можно решить эту задачу последовательным перебором всех элементов множества С/, проверяя для каждого элемента, будет ли выполняться неравенство (1Л). Однако существуют алгоритмы, не t f требующие последовательного перебора. Эти алгоритмы существенно используют тот факт, что на U задана структура метрического пространства. Подробный обзор алгоритмов приближенного поиска приведен в [54], здесь же мы дадим описание лишь наиболее распространенных алгоритмов. Кроме того, в работе [4 дано описание и классификации алгоритмов, предназначенных для текстового поиска (среди рассмотренных там алгоритмов есть также и алгоритмы приближенного поиска в метрическом пространстве).
Алгоритмы приближенного поиска можно условно разбить па две группы в зависимости от того, какого типа метрику они используют. Часть алгоритмов работает в предположении, что метрика, задан пни на U, может принимать относительно небольшое количество различных значений. В противном случае, т.е. если метрика d может принимать неограниченное число значений, множество всех значений метрики d разбивают на интервалы. Алгоритмы второй группы не накладывают ограничения па число различных значений метрики, т.е., эти алгоритмы могут работать непосредственно с непрерывными метриками.
По видимому, первым среди алгоритмов приближенного поиска появился алгоритм ВКТ (Burkhard-KcIIcr Tree) [49), основная идея ; которого заключается в рекурсивном построении индексного дерена: Выбираем произвольный элемент р Є U в качестве! корня дерена. Пробегаем множество U и для каждого элемента и ю этого множества вычисляем значение d(u,p). Затем группируем элементы \ул U в соответствии со значениями d(uJp)J таким образом получим множества Ud(p)7 в которых собраны элементы, находящихся па расстоянии d от вершины р: Ud{v) = {ue U :d{u,p) = d}. Строим первый уровень дерева; элемент р будет корном, от которого отходят ребра с мотками d где d\ — различные возможные значении метрики d(u,p), и пробегает все множество С/, а і Є {1,2,...,гїжм:), Wr число различных значений метрики d(uyp). I Множества Ud[p) разместим на концах ребер с соответствующими метками в качестве листьев дерева.
Дальнейшее построение дерева происходит рекурсивно; в каждом непустом U,i снопа выбираем произвольный элемент / , спона строим множества элементов, находящихся на расстоянии dj от вершины р и так далее. Этот процесс повторяется до тех пор, пока по множествах Ud не останется по одному элементу или, как вариант, пока там пе останется Ь элементов (букет размера Ь).
На рис- 1.1 показан первый таг построения индексного дерева. В этом примере точки располагаются на евклидовой плоскости, множество всех возможных значений метрики d разбито па интервалы единичной длины. Тогда согласно рисунку, имеем; d(p,u\) = 0, d(p,г/2) = d(p,u ) — 1, d(p, щ) = d(p, ІІ5) = d(p, щ) = 2. ti Замечание. Элементы р, использованные при построении дерева а качестве щшши, часто попивают узлами. Поиск в U с использованием построенного индексного дерена осуществляется следующим образом. I Получаем от пользователя эталон q. Находим dp = d{p, q).
Применение гистограмм расстояний к оценке качества набора узлов в целом
Как уже было сказано, гистограммы расстоянии — удобный инструмент для оценки качества отдельно взятого узла (центра). Однако, даже выбрав хорошие узлы или центры pi, Рь мы lice равно не можем быть умеренными в том, что весь набор в целом даст неплохой коночный результат.
Тем ие менее многие алгоритмы индексирования (например, FHQT и FQT) требуют для сноси работы заранее заданного набора узлов. Достраивать этот набор «па лету», по мере надобности адаптируя его под нужды задачи, подобно тому, как это описано выше, нельзя. Таким образом, за неимением возможности произвести оценку качества набора узлов (центров) в целом, в большинстве работ предлагается выбирать их случайным образом.
Здесь мы попробуем рассмотреть несколько иной подход к задаче выбора узлов: будем исследовать качество не отдельных узлов, а их совокупностей. Подход будет строиться па базо обобщающей модели, поэтому его можно будет применить к любому алгоритму индексировании. Поскольку и рамках обобщающей модели понятия узлов и центров становятся идентичными, то мы не будем делать различии между ними и станем называть узлами все точки, относительно которых строятся классы эквивалентности, т.е. и центры, и собственно сами узлы.
Введем некоторые обозначения. Согласно определению, Gp означает гистограмму расстояний, построенную относительно узла р. Тогда др(и) = \[и]р\ — значение гистограммы в точке и или, другими слонами, количество элементов, лежащих в том же классе эквивалентности, что и точка и (в данном случае иод классом эквивалентности подразумевается класс эквивалентности, определяемый узлом р). Аналогично, [ ]j,,...pj -количество элементов, лежащих в классе эквивалентности, определяемом узлами ри ...,рь
Прежде, чем говорить об оптимальном выборе узловых точек, нам необходимо будет обсудить вопрос о критерии качества выбора узлов. Будем исходить из того, что процедура вычисления значении метрики па. множестве U является относительно трудоемкой, поэтому основной целью оптимизации будет сокращение числа измерений расстояний при поиске по дерену.
Как говорилось выше, задавая на множестве U набор узлов рь -1 Рь мы трансформируем исходную задачу ( /, т)(\ и задачу ([g], г)о (см. раздел 1.3). При этом множество {{, r)d\ — решения задачи (q, r)(i содержится во множестве {([?],г)я} решений задачи ([(/],г)#. Мощность этого множества зависит не только от параметров q и г, но и от набора узлов. Рассмотрим отношение мощностей этих множеств;
Очевидно, что эта величина характеризует эффективность отбора элементов: чем ближе она к единице, тем меньше «липших» решении содержится п {(М,г)я}.
Величина Е зависит от многих параметров: от эталона /, радиуса г и набора узлов р\, .,,, р . Поэтому, чтобы определить, насколько па эффективность отбора элементов влияет набор узлов, нужно изучить поведение Е при различных фиксированных значениях остальных параметров. Кроме того, поскольку заранее неизвестно, какой эталон будет дан пользователем для поиска, то логично исследовать среднюю (но q) эффективность, т.е. среднее значение величины Е7 вычисленное для различных д.
Зафиксируем некоторое г и рассмотрим вопрос о том, как можно, варьируя наборы узлов, повысить среднее значение эффективности Е.
Пусть задай набор узлов pi, ..., рд., которые разбивают U на классы эквивалентности. Производя поиск решения задачи (1-1), мы отбросим некоторые из этих классов. Попятно, что чем меньше элементов будет содержаться в оставшихся классах эквивалентности, том лучше,
С другой стороны, поскольку элемент q, для которого мы производим поиск, заранее не известен, то мы не можем предсказать, какие классы останутся в рассмотрении, а какие нет, поэтому для повышения эффективности поиска нужно постараться минимизировать число элементов, находящихся в больших по мощности классах эквивалентности. Самый лучший вариант — попытаться сделать гак, чтобы во всех классах находилось примерно одинаковое число элементов.
Основные понятия теории нечетких множеств. Лингвистическая переменная
В начале этой главы было показано, каким образом производится приближенный поиск информации в метрическом пространство без совершения полного перебора всех элементов этого пространства. Далее было показано, что рассмотренные алгоритмы можно адаптировать к приближенному поиску в БД, если па множестве хранящихся в ней данных задать структуру метрического пространства. Причем метрику можно задавать не на всех полях базы, а лишь на тех, которые будут использоваться при приближенном поиске.
В данном параграфе мы обсудим способы задания метрики па примере строковых полей БД, Кроме того, здесь будут рассмотрены вопросы построения нечетких критериев сходства данных, хранящихся в этих полях. Такие критерии впоследствии позволит нам создать челошжо-ориситирусмый интерфейс для работы с БД.
Известно, что человеческому мышлению свойственна нечеткость, человек мыслит, пользуясь лингвистическими категориями, описывающими его задачу (например; «фамилии похожи», «даты рождения почти совпадают» и т.п.). Таким образом мы по можем потребовать от исследователя (особенно, если он не является специалистом в области информационных технологий), чтобы ои начал мыслить математическими категориями (метрика, множество, класс эквивалентности и т,п.). Поэтому и возникает необходимость создания человеко-ориснтированиого интерфейса, создания языка запросов к БД, близкого к естественному языку.
Как уже было сказано, задачу создания чсловско-орнептироваппого интерфейса для работы с искаженными данными мы будем решать при помощи аппарата теории нечетких множеств. Понятие нечеткого множества было введено Заде (см. [62]) в 19G5 году. Преимущества предложенного им подхода состоят в том, что описание условий и метода решений задачи происходит па языке, близком к естественному. Нечеткая логика ближе к человеческому мышлению и естественным языкам, чем классическая логика, поскольку теория нечетких множеств позволяем1 описывать нечеткие понятия и знания, оперировать этими знаниями и делать нечеткие выводы.
Понятие нечеткого множества
Понятие нечеткого множества приведено во многих работах, здесь будет дано лишь краткое описание, для более подробного знакомства с ними см. 34, 1, 6, 29, 62].
Пусть Е — универсальное множество, х — элемент Е, а Я некоторое свойство. Обычное (меткое) подмножество А множества Е, элементы которого удовлетворяют свойству Ry определяются как множество улор5гдочеппых нар A = {fiA(x)/x}, где І ІА(Х) — характеристическая функция, принимающая значение 1, если х удовлетворяет свойству Л, и 0 в противном случае.
Нечеткое множество отличается от обычного тем, что для элементов х из Е пет однозначного ответа «да-нет» относительно свойства R, В связи с этим нечеткое подмножество А универсального множества Е определяются как множество упорядоченных пар А={{1А{х)/х], щи №л{%) — функция припадлеэюпостщ принимающая значения и некотором упорядоченном множестве М {например, М = [0,1]).
Функция принадлежности указывает стенеш» принадлежности элемента х подмножеству А Множество М называют множеством принадлежностей. Если М = {0,1}, то нечеткое подмножество Л может рассматриваться как обычное четкое множество.
Нечеткое множество обычно имеет лингвистическую мотку, соответствующую содержательной интерпретации, например, если Е — [0,120] — множество числовых значений возраста, то на Е могут быть определены нечеткие множества с лингвистическими метками «молодой», «старый», «очень старый» и тль На рис. 3.6 показаны возможные способы представления понятия «молодой» с помощью характеристической функции множества и функции принадлежности нечеткого множества.
Требования, предъявляемые к информационной системе идентификации останков погибших воинов
Для работы метода идентификации останков, описанного в разделе 4.1,1, требуется анализ большого количества информации- Это и многотысячные списки потерь и миогис-многис привязки захоронений. Анализируя архивные данные и сравнивая их с данными нолевых экспедиции, исследователь обязан помнить, где были найдены медальоны и именные вещи, взаимное расположение останков и т.д. Кроме того, он должен очень хорошо представлять себе модель местности, местонахождение инженерных сооружений, минных полей и заграждений, воронок и огневых точек. Для получения достоверных результатов исследования необходимо держать все эти сведения если и не в памяти, то как минимум под рукой.
Объем находок, сделанных в различных экспедициях, па настоящий момент настолько вырос, что обработка его вручную стала очень затруднительной: обрабатывая и архиве очередной найденный медальон становится уже невозможным вспомнить, что из именных вещей было обнаружено несколько лет назад и где именно, невозможно также вспомнить точное местоположение останков, обнаруженных но время прошлых экспедиций и сравнить их с расположением останков, найденных сравнительно недавно. Вследствие всего сказанного, работа по установлению личности погибших солдат продвигается край і ю медленно и большая доля потенциально полезной информации (и первую очередь географической) безвозвратно теряется, В свою очередь, потеря этой информации отрицательно сказывается на надежности метода идентификации.
Таким образом возникла необходимость автоматизировать процесс хранении и получения информации, т.е., необходимость разработки & информационной системы, которая позволила бы с большей наглядностью оперировать данными, полученными в ходе поисковых экспедиций, оперативно осуществлять поиск архивной информации, с учетом того, что эта информация может быть искажена. Создание такой системы позволит повысить надежность и результативності, процесса идентификации останков погибших военнослужащих. Анализ возможных путей создания системы идентификации останков Как было показано в предыдущем разделе, необходимо создать информационную систему, позволяющую визуализировать пространственные данные и производить поиск информации с учетом ее неполноты и неточности. Рассмотрим возможные пути создания такой системы.
Применение в качестве основы разрабатываемой информационной системы какой-либо системы управления базами данных (СУБД), ограничено слабыми возможностями СУБД но хранению и визуализации географической информации. Поэтому строить систему идентификации останков погибших военнослужащих будет более логично па основе ГИС. Таким образом, примеряя возможности геоипформационпых технологий fj к задаче установления личности погибших солдат, можно сказать, что нам понадобится разработать ГИС, которая будет содержать электронную карту местности с нанесенными па нее специфическими данными. Такими данными могут быть схемы действий войск, расположение инженерных сооружений, коронок, остатков техники и т.д.; кроме того, на карте должны быть отмечены обнаруженные в ходе поисковых экспедиций останки войной и именные вещи.
Применение технологий ГИС її данной работе позволит: - получить разнообразные тематические карты с комбинацией различных информационных слоев как для анализа общей исходной информацией по территории, так и для оснащения поисковых групп достоверной картодокументацией (для ориентации на местности, дли ведения поиска и т.д.) - улучшить планирование поисковых работ, повысить учет и отчетность; таким образом, с одной стороны, увеличить число установленных имен, с другой стороны, повысить наглядность работы на местности — качество обработки территории. - визуализация данных облегчит процесс анализа информации из БД по совпадению географических параметров.
Однако, система идентификации останков военнослужащих не может сводиться лишь к гсоипформациопнпй системе, визуализирующей пространственные данные. Дело в том, что разрабатываемая система должна предоставлять пользователю возможность работы с искаженными и неполными данными, по распространенные в настоящее время ГИС и СУБД для этого не предназначены. С самого начала создания системы, автоматизирующей сопоставление архивных списков и данных поисковых экспедиций, возникают три трудности:
