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

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

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

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

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

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

для специальности 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 части: адресную часть и массив элементов информации.

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

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

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

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

   2.1.3. Узловой способ организации массивов 

   Применяется для записи в память ЭВМ информационных сведений сложной структуры. Связи между элементами одного информационного массива фиксируются позиционно, т.е. путем совместного расположения кодов этих элементов или их адресов в одном узле. В узловом способе сочетаются свойства гнездового и цепного способов. На рис.5 приведен пример использования узлового способа массива сообщений, каждое из которых состоит из трех элементов: А - адресная часть, Б - массив сообщений. Для записи одного сообщения отводится 1 ячейка памяти. Ячейка делится на три участка. Каждый участок представляет один элемент сообщения, участки ячеек, обозначающие одинаковые элементы сообщения, соединяются между собой цепочками адресных отсылок - эти цепочки условно изображены линиями со стрелками. Адресные отсылки к участкам, являющиеся первыми элементами цепочек, указываются в части А, а отсылки к остальным элементам цепочек - в части Б.

   При этом отсылки элементов к элементам  ассоциативных цепочек с порядковым номером i записываются на участках, являющихся элементами этих цепочек с порядковым номером (i-1). Заштрихованные участки на рис.5 обозначают признак конца. В данном примере предполагается, что поиск в адресной части будет вестись цепным способом, а в качестве признаков для формирования ассоциативных цепочек будут служить свертки кодов элементов. К первым элементам ассоциативных цепочек будут обращаться по сверткам, а к остальным элементам - по кодам связи. Соответственно в ячейках адресной связи будут храниться тройки кодов К_эА₀<К_св. Поиск в адресной части считается законченным, если заданный код элемента совпадает с одним из кодов К_э и для чего выбирается соответствующий адрес А₀.

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

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

Рисунок 4- Цепной способ поиска

Рисунок 5 -Узловой способ поиска 

       2.2. Способ последовательного просмотра или способ перебора 

   Для заданного числа Х последовательно  проверяется выполнение неравенства:

   X>X₁, Х>Х₂,..., x>x_l   (1).

   Одновременно  ведется подсчет числа проверок. Этот процесс продолжается до тех  пор, пока одно из условий (1) окажется невыполнимым. Тогда проверяется равенство:

   Х=Х_K    (2),

К - порядковый номер сравниваемого числа списка.

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

   k=k₁+k-1 ,

K₁ - адрес первого числа.

   При выполнении (2) поиск прекращается. Способ последовательного просмотра самый  невыгодный в смысле затрат машинного времени. Если вероятность обращения к любому из L чисел списка одинакова и равна 1/L, то в среднем требуется просмотреть (L+1)/2 чисел, чтобы найти нужный адрес. 

         2.3. Способ последовательного деления на части. 

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

К - целая  часть от деления количества элементов  в массиве на шаг l.

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

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

n - количество элементов в массиве X.

   Метод деления массива на части при  К=2 называют дихотомическим или двоичным поиском. Он является более эффективным  по сравнению с методом деления на части при K 2.

        2.4. Способ разделителей. 

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

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

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

   2.4.1. Разновидностью способа разделителей является метод "свертки кодов".  
Свертка имеет значительно меньшую длину, чем длина исходного кода. Свертки могут быть использованы в качестве адресов для обращения к таблице разделителей.

   Правила образования кодов рассмотрим на примерах (таблица 1).

Таблица 1-Правила образования кодов

   Приближенно длина свертки может быть определена по формуле:

где  l - объем массива кодов, в котором производится поиск;

   n - среднее количество кодов в участке.

       2.5. Способ линейной интерполяции. 

   Дана  монотонно возрастающая функция

   k=f(x)     (4)

   Заменим ее линейной функцией

   k=Ax+B     (5)

с коэффициентами:

   Подставляя  в формулу (5) В и учитывая, что адрес k должен быть целым числом, получим для него следующее выражение:

      (6)

   Действительный  адрес числа х при х₁ х x_L заключен либо в интервале (k₁, k), либо в интервале (k, k_L.) в зависимости от того, выполняется или не выполняется условие х х_S, в котором х_S означает число X₁, имеющее адрес k.

   Поиск способом линейной интерполяции: сначала  по формуле (6) вычисляется адрес k. Затем  определяется величина и знак разности x-x_S. Если x-x_S=0, то поиск окончен. Если x-x_S>0, то дальнейший поиск ведется способом последовательного просмотра от меньших значений х к большим/ Если х-х_S<0, то последовательный просмотр ведется в обратном направлении.

        2.6. Серийный упорядоченный поиск (способ скользящего канала) 

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

   Среднее количество циклов поиска одного числа  определяется величиной:

l - объем списка чисел, находящихся в ОЗУ;

n - количество искомых чисел. 

       2.7 Прохождение бинарных деревьев 

   Это способ методического исследования вершин дерева, при котором каждая вершина проходится только один раз

   В результате обхода дерева получаем линейную расстановку всех вершин, т.е. фактически вводим отношение предшествования на множестве вершин дерева. На рис.6 изображен обход дерева. Мы обходим дерево вдоль пунктирной линии в направлении стрелок, начиная и заканчивая обход в корне. На каждое прохождение мы попадаем в вершину по меньшей мере один раз, а вообще говоря, три раза. Обходя дерево, мы можем систематически делать что-то с каждой вершиной, например, печатать номер вершины. Если мы будем печатать номер вершины только при первой встрече с ней, то получим последовательность 6, 4, 3, 5, 7. Если печатать номер при второй встрече, то получим 3, 4, 5, 6,7, а если при третьей - 3, 5, 4, 7, 6. Эти три способа обхода вершин называются соответственно обходом: сверху, слева направо, снизу.