МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН

КАРАГАНДИНСКИЙ  ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

   
 
 
 

Кафедра автоматизированных  
информационных систем 
 
 
 
 
 
 

Методические  указания для выполнения

 

К У Р С О В  О Г О  П Р  О Е К Т А 

«Сравнительный анализ информационного поиска» 

для специальности 050703 «Информационные системы»

по курсу  «Информационное обеспечение социально-экономических процессов» 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Караганда 2011  

ЦЕЛЬ  РАБОТЫ: изучение информационного поиска при различных способах организации массивов, различных поисковых стратегиях, различных критериях выдачи. 
 

1. Организация массивов 

   Известно  множество методов организации  массивов. Основные различия между  ними заключаются в способе размещения записей и форме представления информации.

   Последовательно-смежное  размещение записей использует такое  размещение, при котором (n+1)-я запись следует непосредственно за n-ой записью. Этот вид организации записей способствует экономии памяти, но затрудняет введение изменений в массивы. Примером массивов информации, записанных в ЗУ с последовательным доступом, является магнитный диск.

   Списки - такая организация данных, при  которой размещение записей не зависит  от места в информационном массиве. Если при последовательно-смежной  организации нет необходимости в n-ой записи указывать место или адрес расположения (n+1)-ой записи, то в списковых структурах n -я запись должна содержать сведения о том, где можно найти (n +1)-ю запись. Списковая структура может быть практически реализована только на внешних ЗУ (МД).

   Матрицы - одним из простейших обобщенных линейных списков являются двумерные (n -мерные массивы, n >2) массивы. Рассмотрим матрицу A(m n): 

 

   Каждый  элемент А(i, j) принадлежит двум линейным спискам: списку строки i A(i,1), A(i,2),…,A(i,n) и списку столбца j A(l,j), A(2,j), ,A(m,j) Эти списки строк и столбцов определяют двумерную структуру матрицы.

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

   Каждый  узел дерева является корнем некоторого поддерева, которое содержится в  этом дереве. Число поддеревьев данного  узла называется степенью этого узла. Вершина с нулевой степенью называется концевой вершиной или листом. 
 

     

Рисунок1 - Дерево

   

Рисунок 2- Представление бинарного дерева в виде списковой структуры 

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

   Максимальное  число сыновей у отца определяет порядок дерева. На рис. 1 изображена древовидная структура данных с  порядком 4. Если порядок дерева больше 2-х, то такие деревья являются общими; если порядок равен 2 - то бинарными (двоичными). Дерево порядка один - есть строчная структура.

   Бинарные  деревья получили широкое распространение. Часто обычные деревья представлены в виде бинарных деревьев; бинарные деревья допускают простое и  естественное представление в памяти ЭВМ: в виде списковых структур. Каждый элемент такого списка кроме данных содержит два адреса связи левой (LLINK) и правой (RLINK) вершин.

   Помимо  того, находим указатель списка Т. Если дерево пусто, то Т=0, в противном  случае Т содержит адрес корня  этого дерева. На рис. 2 показано представление дерева в виде списковой структуры.

   Формирование  бинарного дерева. Наиболее распространенным условием организации бинарных деревьев является наличие отношений порядка  на множестве ключевых признаков, которыми снабжаются элементы дерева. Будем обозначать такое отношение символом "S". Отношение упорядоченности привычно, когда речь идет о числах, но оно может быть определено и для слов некоторого языка, например, словарь - это упорядоченное множество слов. В упорядоченном бинарном дереве каждый элемент имеет на своей левой ветви элементы с меньшим, чем у него значением ключа, а на правой ветви элементы с большим значением. Элементы с равным значением могут располагаться и на левой и на правой ветви данной вершины. Обычно они направляются в правую ветвь. Таким образом, в упорядоченном бинарном дереве значение ключа каждого элемента больше, чем значение ключа любого элемента на его левой ветви, и не меньше чем ключ любого элемента на его правой ветви.

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

1. Первый  поступающий элемент Р₁ поступает в корень дерева;

2. Значение  ключа следующего элемента Р₂ сравнивается с Р₁.

   Если  P₂<P₁, то P₂ помещается по левой ветви относительно корня.

   Если  P₂ P1 - то по правой ветви.

3) Выбор  местоположения i-го элемента производится  следующим образом: просматривается  некоторый путь по дереву, начиная  с корня. На каждом шаге такого  просмотра значение ключа элемента Р_i сравнивается с ключом некоторой вершины Р_k. Если P_i> Р_k то переходим к следующей вершине, находящейся на левой ветви относительно элемента Р_k.

   Если  эта ветвь пуста, то достраивается  новая вершина, и в нее помещается элемент P_i. В случае P_i Р_k все происходит аналогично, но с правой ветвью вершины Р_k. Пример показан на рис. 3.

D - массив записей, которые должны быть размещены в вершинах дерева.

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

 

 

Рисунок З- Формирование упорядоченного бинарного дерева (сортировка по алфавиту) 

2. Стратегия поиска 

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

1) Упорядоченность  множества А;

2) Тип  используемого носителя информации;

3) Логическая  и физическая организация множества  А.

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

   В={а|а А&Р(а)}

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

   Рассмотрим  некоторые способы поиска: 

        2.1. Ассоциативно-адресные способы 

   Сущность  данного поиска заключается в  том, что информационные сведения, обладающие признаками, объединяются с помощью  системы адресных отсылок в ассоциативные  группы или списки. Это позволяет производить быстрый поиск в массивах неупорядоченных элементов и создает удобства при обновлении информации. Различают 3-и основных способа объединения информационных сведений в ассоциативные группы: гнездовой, цепной, узловой. 

   2.1.1. Гнездовой способ 

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

   Если  адресные отсылки располагаются  в нескольких гнездах, то переход от одного гнезда к другому осуществляется через адреса связи, специально вводимые в состав гнезда.

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

   Если  необходимо дополнить ассоциативные  группы новыми элементами, то коды размещаются  на свободном поле памяти, а для  записи отсылочных адресов создаются  новые гнезда. 

   2.1.2. Цепной способ 

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

   Рассмотрим  пример организации поисковых массивов, когда в качестве признаков для  формирования цепочки ассоциативных  элементов принимаются свертки  кодов этих элементов. Область памяти ЭВМ делится на 2 части: адресную часть и массив элементов информации.