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

выражением. В этом случае адрес Кі числа х,-, а следо­ вательно, и адрес числа г/j, может быть вычислен на ЭВМ но самому числу Хі, и в ЗУ машины достаточно хранить только числа у.

Особенно просто определяется адрес числа по его величине, когда функциональная зависимость (5.2) ли­ нейна (например, при равноотстоящих значениях чисел х). Однако в информационно-поисковых системах она обычно нелинейна, и здесь приходится применять дру­ гие способы поиска адреса числа х.

Рассмотрим некоторые способы поиска адреса числа X по заданному значению этого числа, полагая при этом, что функциональная зависимость (5.2) не может быть представлена достаточно простым аналитическим выра­ жением.

Способ последовательного просмотра (способ перебора)

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

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

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

в которой Кі обозначает адрес первого числа, а k имеет тот же смысл, что и в формуле (5.4). При выполнении равенства (5.4) поиск прекращается.

Способ последовательного просмотра — самый невы­ годный в смысле затрат машинного времени. Если веро­ ятность обращения к любому из I чисел списка одинако­

73

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

а в порядке убывания вероятностей их поиска. Однако

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

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

Расположение чисел х в ЗУ машины в порядке воз­ растания их величины позволяет избежать последова­ тельного просмотра всего списка чисел при определении адреса искомого числа. Вместо последовательного сплошного просмотра этого списка можно просматри­

к которым производится обращение, будут иметь адреса, определяемые формулой

Здесь К1 — начальный адрес списка; Е — оператор вы­ деления целой части числа, а g— номер шага просмотра (£ принимает последовательно значения 1, 2 —1).

Просмотр ячеек с адресами, определяемыми по фор­ муле (5.6), продолжается до тех пор, пока не окажется невыполненным одно из неравенств типа

или пока не будут просмотрены все такие ячейки. При невыполнении одного из неравенств (5.7) описанная проце­ дура просмотра применяется к участку списка (х\-\, Х\). Если все неравенства оказываются выполненными, то делению на п частей и просмотру подвергается участок списка (Хп-і, Хі).

74

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

где / ' — количество чисел в области поиска. После вы­ полнения условия (5.8) поиск осуществляется способом последовательного просмотра.

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

а среднее количество циклов поиска в случае равномер­ ного распределения вероятностей поиска чисел списка— формулой

значение, так как способ деления на части приобретает

списка чисел на части при п = 2 носит название «способа

ска чисел на части выполняется только один раз, а затем производится последовательный просмотр чисел выделен­

75

ного участка. Максимальное число циклов поиска по способу двухстепенного перебора определяется выраже­ нием

а количество просматриваемых чисел на первом и вто­ ром этапах поиска совпадает.

Среднее число циклов поиска при двухстепенном переборе может быть приближенно определено по фор­ муле

а минимальное время поиска здесь обеспечивается при том же условии, что и в формуле (5.12).

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

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

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

76

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

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

Разновидностью способа разделителей является «ме­

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

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

г=Е[\о&1/п]+\,