книги из ГПНТБ / Зубов В.С. Математическое обеспечение цифровых вычислительных машин и систем учеб. пособие

- 8 0 -

или записи во внешнюю память в расчёте на элемент данных

значительно сокращается, если пересылается совокупность по­

следовательно расположенных в памяти элементов (" блок" ) .

Данное обстоятельство в силу необходимости совместного рас­

смотрения упорядочиваемых данных и сегментации объёма внеш­

ней памяти требует соответствующей сегментации исходной и

промежуточных последовательностей, обеспечивающей такую не­

зависшую обработку в оперативной памяти отдельных сегмен­

тов, которая приводит к получению правильной последователь­

ности, Этому требованию удовлетворяют алгоритмы взаимного

и внутреннего упорядочения последовательностей, как сопос­

тавительные, так: и стобразительные. С целью повышения про-

А Л Г О Р И Т М Ы У П О Р Я Д О Ч Е Н И Я

[по сопоставительному методу] |п'о отобразнтельному методу)

Рис.9. Классификационное дерево алгоритмов упорядочения .

- 81-

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

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

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

Схематичное представление о распространённых алгоритмах упорядочения во внешней памяти читатель может получить из [7],

ГЛАВА Ш. ИНФОРМАЦИОННЫЙ ПОИСК

§I . Понятие информационного поиске, и его связь

опонятиями упорядочения и сортировки

Назначением структур данных, упорядоченных по содерка-

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

(например, по имени, по качественному признаку) с целью ис­

пользования другой части их содержания. В качестве опозна­

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

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

Процесс опознания элементов данных по содержанию на

любом уровне, их иерархии будем называть информационным по­

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

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

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

- 8 3 -

числе использований элементов этого уровня» приводящем к превышению суммарного выигрыша времени при доступе к дан­ ным над его проигрышем при организации в ЭВМ этого уровня.

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

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

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

понятие сортировка покрывает понятие "упорядочение" лишь частью, хотя, с другой стороны, упорядочение нередко в той или иной степени ограничивает произвол в расположении

элементов ассоциации, т .е . привносит большую определённость в расположение элементов, чем это требуется для сортировки.

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

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

ве нескольких характеристик, присущих описываемым объек­ там.

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

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

- 8 5 -

лэняого явно ограничения в списке, естественно рассматри­

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

социацию, а затем выявляются все входящие в неё записи.'

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

чие в заданном смысле от значения той же функции для а|>-

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

ля от модуля старшего управляющего поля поискового образа. '■

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

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

- ё б -

лёняым на этапы, умозрительно выделенные наш для облегче­

ния его восприятия, и рассматривать управляющее слово одним

актом.

3. Примером случая, когда затруднительно явно выделять

ассоциации записей для последующего•их поиска, является случай нахождения ассоциации записей со значениями управ­

ляющих слов, попадающих в заданный интервал числовой оси

(предполагается что от случая к случаю поиска интервал мо­ жет изменяться; управляющее слово может быть спроецировано на числовую ось по правилу, рассмотренному в §4 гл .П ). Вы­

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

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

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

рассмотренных в п .п . 1 - 3 , будем именовать поиском по сложному арифметическому условию.

5. Рассматривая логические переменные, соответству­ ющие подобным вышеуказанным условиям поиска, можно обра-

- а ? - ,

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

6. Как указывалось выше, в состав записей могут вхо­ дить и текстовые элементы данных. При их использовании в составе управляющих слов понятия совпадения, попадания в интервал, близости (минимального отклонения) могут интер­ претироваться не в"арифметическом", а в более сложною.,

условно именуемом семантическим, смысле. Характерным при­ мером может служить библиографический поиск, когда объ­ ектами поиска служат научные публикации, рефераты, тези­ сы публикаций. Условием поиска по аналогии с поиском по совпадению может быть совпадение содержания закодирован­ ного зЙцюса с содержанием публикации, также закодиро­ ванным по определённым правилам, или - по аналогии с по­ иском по интервалу - совпадение содержания публикации с содержанием запрошенного в условии поиска раздела, по существу более широкого, чем содержание отдельной публи­ кации, или - по аналогий с поиоком по близости - не обя­ зательно полное совпадение, но близость содержания запро­ са и содержания публикации. Поиск, осуществляемый по опи­ сываемым условиям будем называть’ поиском по семантическо­

му условию.

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

подхода и далеко не всегда поддающейся разрешению. Кроме

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

является выбор языка для кодирования информации внутри ЭВМ и запросов на поиск, позволяющего, во-первых, отразить

существенные черты самой информации и запроса и, во-вторых,

реализовать в рамках этого языка проверку критериев совпа­ дения информации с заданным запросом или близости запроса

иинформации.

б) Поиск с ослаблением ( усилением) условий

ни одного объекта, удовлетворяющего условиям приска. Та­ кой случай' может произойти, например, при поиске по ин­

-89-

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

Особенно часто необходимость динамических изменений

поисковых образов возникает при семантическом поиске.

До сих пор подразумевался вариант поиска с ослаблени­

ем (усилением) условий поиска, при котором результат вы­ полненного этапа используется для управления следующими

шагами поиска. Такое решение, в самом деле, часто оказы-

с

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

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

Допустим, например, что задана конъюнктивная сово­

купность П условий поиска, и необходимо выделить объекты

с наибольшим количеством выполненных условий. Если это ко­