Файл: Белоногов Г.Г. Автоматизированные информационные системы.pdf

П р и м е р ы сверт ок кодов

где / — объем массива кодов, в котором производится поиск; п — среднее количество кодов в участке. Величину п выбирают, исходя из практических соображений.

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

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

Заменим произвольную монотонно возрастающую функцию (5.2) линейной функцией

с коэффициентами А = (Кі—Ki)/(xt—х\) и ß = —Ахi. Подставляя выражение для В в формулу (5.15) и учи­ тывая, что адрес К, должен быть целым числом;, цолучщ

те

имеющее адрес К.

Поиск способом линейной интерполяции производится следующим образом. Сначала по формуле (5.16) вычис­ ляется величина адреса К. Затем определяется величина и знак разности х— Дд. Если эта разность равна нулю, то поиск окончен. Если она не равна нулю и положи­ тельна, то дальнейший поиск ведется способом последо­ вательного просмотра в направлении от меньших значе­ ний X к большим. Если разность отрицательна, то после­ довательный просмотр ведется в направлении от больших значений х к меньшим.

Серийный упорядоченный поиск

Этот способ поиска известен также под названием

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

Способ скользящего начала выгодно применять тогда, когда список чисел хранится в ЗУ на магнитных лентах или магнитных барабанах, не допускающем произволь­ ного порядка обращения к ячейкам. Но и при поиске в ЗУ с произвольным доступом к ячейкам способ сколь­ зящего начала может быть эффективным, если требуется найти большое количество предварительно упорядочен­ ных чисел. Среднее количество циклов поиска одного числа здесь определяется величиной

1Сф—І/П;

где I — объем списка чисел, хранящихся в ЗУ; л — коли­ чество искомых чисел.

79

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

Существо ассоциативно-адресных способов поиска (другое их название — программно-ассоциативные спо­ собы) состоит в том, что информационные сведения, обладающие общими признаками, объединяются с по­ мощью системы адресных отсылок в ассоциативные группы (или списки). Это позволяет производить быст­ рый поиск в массивах неупорядоченных сведений и соз­ дает удобства при обновлении информации. В настоя­ щей главе мы рассмотрим лишь основные принципы применения ассоциативно-адресных способов поиска. Более подробные сведения по этому вопросу можно найти в монографии А. И. Китова [68].

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

водном или нескольких «гнездах». Каждое гнездо пред­ ставляет собой группу следующих друг за другом ячеек. Если адресные отсылки к элементам ассоциативной группы располагаются в нескольких гнездах, то перехо­ дят от одного гнезда к другому через отсылочные адре­ са, вводимые для этой цели в состав гнезд (по так назы­ ваемым адресам связи). Элементы информации, образу­ ющие одну ассоциативную группу, могут располагаться

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

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

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

8 0

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

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

Рассмотрим важный в практическом отношении при­ мер организации поисковых массивов, когда в качестве признаков для формирования цепочек ассоциированных элементов принимаются свертки кодов этих элементов.

Здесь область памяти ЭВМ, отводимая для записи ин­ формационных сведений, делится на две части (рис. 5.1):

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

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

Если необходимо отождествить элемент информации, поступивший «а вход поисковой системы, е одним из элементов этой системы, то сначала формируют код свертки входного элемента. Код свертки интерпретиру­ ется как адрес участка Л поискового массива (рис. 5.1) и с его помощью выбирается ячейка с отсылочным ад­ ресом Ло и кодом связи Ксв. По отсылочному адресу из участка В выбирается код элемента информации и сравнивается с кодом, поступившим на вход системы. Если коды совпадают, то поиск считается законченным, если нет, то производится обращение по коду связи к одной из ячеек участка Б, содержащей отсылочный адрес к следующему элементу ассоциативной группы и код связи. По отсылочному адресу снова выбирается элемент информации и сравнивается с кодом, поступив­ шим на вход системы. При совпадении кодов поиск заканчивается, при несовпадении — из участка Б выби­ рается по коду связи новая ячейка с отсылочным адре­ сом и кодом связи и т. д. Процесс поиска продолжается до тех пор, пока в одной из ячеек адресной части поискового массива вместо кода связи не окажется при­ знак конца ассоциативной цепочки (в качестве при­ знака конца может служить кодовая комбинация, состо­ ящая из нулей или единиц).

Если нужно дополнить массив элементов информа­ ции, то при обнаружении признака конца ассоциативной

82