Теоретические основы информационных процессов

Теоретические основы информационных процессов

Введение

из истории науки. В 1948 году вышла в свет работа Клода Шеннона «Математическая теория связи», в которой развивались идеи помехоустойчивого кодирования при передаче сообщений по каналам с шумами. Этот труд лег в основу нового научного направления, получившего название «Теория информации». В рамках теории информации был получен ряд значительных результатов, связанных с различными вопросами кодирования передаваемых сообщений. Это результаты «в области алгебраической теории кодирования, построения различных оптимальных кодов, в области декодирования избыточных кодов, получения границ вероятности ошибки и различных информационных пределов избыточности» [Советов, с.13]. Многие из них были успешно использованы на практике, например, при решении задачи выбора комплекса технических средств и обеспечения его оптимального функционирования.

Однако с развитием вычислительной техники – появлением персональных ЭВМ и их сетей – наиболее актуальными оказались проблемы не оптимального кодирования, а оптимального поиска и хранения данных в искусственной памяти, а также другие вопросы, связанные с обработкой данных. Поэтому в 80-е годы прошлого столетия на основе классической теории информации сформировалась новая наука с более широкой предметной областью - теоретическая информатика, включившая теорию информации как один из разделов. Курс «ТОИП» охватывает некоторые основные направления развития теоретической информатики.

 

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

Согласно некоторым, наиболее общим представлениям в теоретической информатике можно выделить следующие основные направления:

1. Хранение данных (организация баз данных и знаний, моделирование данных и т.п.).

2. Поиск данных (виды поиска, их эффективность, помехоустойчивость поиска и т.п.).

3. Передача данных (кодирование сообщений, помехоустойчивость кодирования и другие вопросы теории информации).

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

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

 

Цели и задачи курса. Овладение набором теоретических сведений, используемых при проектировании алгоритмов обработки данных.

КОДИРОВАНИЕ СООБЩЕНИЙ

Информационные процессы

 

С категорией «информация» (см. разд.1, §5) тесно связано понятие информационного процесса (ИП). Под ИП понимается:

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

 

Рис.1.1

Движение данных в АИС

 

2) Процесс обработки данных. Напомним (см. курс «ТЭИС»), что обработка данных – это всевозможные действия, производимые над данными. Процессы обработки данных связаны с процессами их движения – в процессе обработки происходит преобразование данных из одной формы в другую. Например, на рис. 1.1 показана взаимосвязь процесса движения данных с тремя процессами обработки;

3) Система информационных процессов (т.е. совокупность взаимосвязанных ИП).

Таким образом, определение ИП строится по принципу рекурсии. Рассмотрим теперь информационные процессы передачи и кодирования данных в АИС, являющихся подсистемами различных АСУ.

 

 

Процедура Шеннона-Фано

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

Рис.1.5

Кодовое дерево в процедуре Шеннона-Фано

 

Выполнив расчеты по формуле 1.3, получим: λ_k^S= 3,145(бит/сообщение).Таким образом, код, полученный при помощи процедуры Шеннона-Фано, оказывается более экономным, чем код из таблицы 1.1.

 

Процедура Хафмана

 

Рассмотренная в §13процедура Шеннона-Фано является простым, но не всегда оптимальным алгоритмом построения экономного кода. Причина состоит в том, что способ разбиения на подмножества ограничен: вероятности сообщений, отнесенных к первому подмножеству, всегда больше или всегда меньше вероятностей сообщений, отнесенных ко второму подмножеству. Оптимальный алгоритм, очевидно, должен учитывать все возможные комбинации при разбиении на равновероятные подмножества. Это обеспечивается в процедуре Хафмана.

Процедура Хафмана представляет собой рекурсивный алгоритм, который строит бинарное дерево «в обратную сторону», т.е. от конечных вершин к корню. Основная идея алгоритма состоит в том, чтобы объединить два сообщения с наименьшими вероятностями – например, p₁ и p₂ – в одно множество и далее решать задачу с m-1 сообщениями и вероятностями p₁’ = p₁ + p₂; p₂’ = p₃; …; p_{m-1’ =} p_m. Кодовое дерево, построенное процедурой Хафмана для рассматриваемого примера, приведено на рис.1.6.

 

Рис.1.6

Кодовое дерево в процедуре Хафмана

 

Расчеты по формуле 1.3 дают среднее значение длины кодового слова λ_k^S= 3,145(бит/сообщение), что совпадает с результатом применения процедуры Шеннона-Фано. Это означает, что для данного примера процедура Шеннона-Фано также оказалась оптимальной.

 

Помехоустойчивость данных

 

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

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

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

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

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

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

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

Например, вместо двоичных знаков 0 и 1 можно передавать через канал связи последовательности 0…0 и 1…1, каждая из которых содержит нечетное число знаков. Ясно, что если помехи действуют на знаки независимо и вероятность искажения знака меньше 1/2, то принятая комбинация будет содержать больше неискаженных знаков, чем искаженных. Следовательно, приемник сообщений должен подсчитывать число нулей и единиц в полученных комбинациях и делать вывод о том, что была передана единица, если в некоторой комбинации больше единиц, или был передан нуль, если в ней больше нулей. Чем больше кратность повторения, тем достовернее такой вывод.

Применение процедуры повторения ведет к тому, что при кодировании сообщений используются не все возможные кодовые комбинации. Такое кодирование называется избыточным. При этом используемые кодовые комбинации называются разрешенными, а неиспользуемые – запрещенными. Например, если вместо знаков 0 и 1 мы передаем кодовые слова 00000 и 11111 (пятикратное повторение), то разрешенными являются всего две кодовые комбинации из 2⁵ = 32 возможных.

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

Необходимо отметить, что меры обеспечения экономности и помехоустойчивости взаимно противоречивы: экономность достигается за счет уменьшения избыточности, а помехоустойчивость – за счет ее увеличения.

 

ПОИСК ДАННЫХ

Проблема поиска данных

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

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

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

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

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

Виды ЗУ

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

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

Адресные ЗУ при каждом считывании предоставляют запись, находящуюся в ячейке, адрес которой указан на входе устройства. Чтобы получить некоторую i -ю запись таблицы, нужно на входе ЗУ указать адрес (номер) ячейки, в которой размещена эта запись. На рис. 2.1 представлена схема адресного ЗУ.

 

 

Рис.2.2

Схема адресного ЗУ

 

Адресное ЗУ состоит из двух частей: дешифратора адреса и матрицы ЗУ. Записи хранятся в строках матрицы ЗУ. Двоичный код адреса записи поступает на вход дешифратора адреса, который преобразует его в унитарный код с числом разрядов, равным количеству строк в матрице ЗУ. Логическая единица появляется на выходе дешифратора, номер которого соответствует двоичному коду адреса. Под действием сигнала логической единицы содержимое соответствующей строки матрицы ЗУ выводится на выход устройства. В качестве адресных ЗУ выступают такие технические устройства, как оперативное и постоянные запоминающие устройства ЭВМ, накопители на магнитных, оптических дисках и т.п.

Ассоциативные ЗУ при каждом считывании выдают на выходе запись, содержимое определенного поля которой совпадает со значением ключевого слова, поданного на вход устройства. Чтобы получить в распоряжение i -ю запись таблицы, нужно на вход ЗУ подать кодовое слово, соответствующее ключевому слову i -й записи. На рис. 2.2 приведена схема ассоциативного ЗУ.

 

Рис.2.2

Схема ассоциативного ЗУ

 

 

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

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

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

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

Методы поиска можно разделить на два класса:

поиск, основанный на преобразовании аргумента в адрес;

поиск, основанный на сравнении ключей.

Рассмотрим оба этих класса.

 

§3. Поиск на основе преобразования ключа в адрес

 

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

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

Примерно такой же простотой и быстротой характеризуется поиск, основанный на определенной регулярности возможных значений ключей. Например, если в файле успеваемости студентов в качестве ключей использовать последовательность NMP, то адрес записи с информацией об успеваемости студента с номером N в месяце M по предмету с номером P может вычисляться по формуле (N-1)∙35∙12∙L + (M-1)∙12∙L + (P-1)∙L + 1, где L – длина записей в файле.

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

Строку символов, составляющих ключ, всегда можно взаимно однозначно преобразовать в целое число. Например, ее можно рассматривать как запись числа в системе счисления с основанием, равным размеру алфавита. Так, для русского алфавита А=0, Б=1, В=2, …, Ю=31, Я=32 и фамилия «ДЕЕВ» будет преобразована в число 4∙33³ + 5∙33² + 5∙33¹ + 4∙33⁰ = 149362. Однако и после такого преобразования значения ключей не приобретут регулярности.

 

Перемешивание

 

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

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

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

 

Рис.2.3

Пример использования перемешивания

 

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

В приведенном примере отражены две существенные проблемы перемешивания:

1) как найти преобразование значений аргумента в целые числа из заданного диапазона, при котором числа были бы распределены в диапазоне достаточно равномерно?

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

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

1. Перевод аргумента (если он не числовой) во взаимно однозначное числовое представление.

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

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

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

Наиболее распространенная функция перемешивания основана на методе деления. Аргумент в числовом представлении делится на число, равное или близкое к числу записей в таблице. Остаток от деления дает относительный хеш-адрес. Данный метод при всей его простоте обеспечивает достаточно равномерное рассеивание хеш-адресов при заполнении таблицы. Для лучшей равномерности перемешивания делитель должен быть нечетным числом, не должен выражаться степенью основания, по которому ключи переводятся в числовую форму, по мере возможности это должно быть простое число. Например, если число адресов равно 7000, то в качестве делителя подходит число 6997. Пусть числовая форма ключа равна 149362 (строка «ДЕЕВ»), тогда остаток от деления ее на число 6997 равен 2425. Поэтому запись с ключом «ДЕЕВ» при заполнении таблицы направляется в ячейку с адресом 2425, а при поиске извлекается из той же ячейки.

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

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

Возможность коллизий приводит к тому, что не всегда нужная запись находится за одно считывание данных из памяти. При возникновении коллизии, возможно, потребуется два, три или даже более считываний данных – так называемых опробований, пока не будет найдена требуемая запись или не выяснится, что данная запись отсутствует. Другой особенностью данного метода организации поиска является наличие пустых мест в таблице. Дело в том, что чем плотнее заполнена таблица, тем больше вероятность коллизии и, следовательно, больше опробований нужно совершить, чтобы найти нужную запись. Поэтому для сокращения времени поиска целесообразно не заполнять таблицу до конца (на практике плотность заполнения таблицы обычно не более 80-90%).

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

 

Последовательный поиск

 

Этот вид поиска является единственно возможным для последовательных ЗУ, однако ввиду своей простоты и универсальности он часто применяется и для адресных ЗУ.

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

В случае удачного поиска возможное число сравнений лежит в пределах [1,N], где N – число записей в таблице. Для случая неудачного поиска всегда требуется N сравнений.

Пусть значения аргумента случайны, т.е. в текущем запросе с некоторой вероятностью Q аргумент не совпадает ни с одним ключом таблицы, а с вероятностью 1-Q совпадает хотя бы с одним ключом (Q – вероятность неудачного поиска). Кроме того, в случае удачного поиска существуют вероятности p_i того, что аргумент совпадает с ключом i- й записи таблицы (). Тогда среднее число сравнений в случае удачного поиска составляет

Для равновероятных запросов ,

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

Для равновероятных запросов аргумента последняя формула принимает вид:

 

Пусть записи в файле или таблице упорядочены по возрастанию ключей, т.е. K₁<K₂<…<K_N. Во многих случаях упорядочивание файла легко производится с помощью разнообразных алгоритмов сортировки. Для удачного поиска предварительное упорядочивание файла никак не влияет на необходимое среднее число сравнений, однако в случае неудачного поиска это часто позволяет завершить поиск раньше, чем будет просмотрен весь файл. Действительно, лишь только ключ очередной записи превзойдет аргумент поиска, можно будет утверждать, что требуемая запись в таблице отсутствует. Таким образом, необходимое число сравнений в этом случае лежит в пределах [1,N].

Пусть известны вероятности q_i того, что в случае неудачного поиска аргумент принимает значения A< K₁ при i=1, K_i-1<A< K_i при i=2,3,…,N и A> K_N при i=N+1. Тогда среднее число сравнений при неудачном поиске составляет…

Для равновероятного случая

 

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

Для равновероятного случая эта формула принимает вид

 

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

 

Блочный поиск

 

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

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

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

 

Двоичный поиск

 

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

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

,

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

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

 

 

Рис.2.4.

Пример двоичного поиска записи в таблице

 

Двоичный поиск удобно представить в виде двоичного дерева (см. рис.2.5). Вершинами дерева двоичного поиска являются ключи, сравниваемые с аргументом поиска. При этом корнем является ключ записи, сравниваемой на первом шаге. Поиск можно интерпретировать как прохождение дерева от корня до искомой записи. Если достигнута конечная вершина, а заданный ключ не найден, то искомая запись в файле отсутствует. Число вершин на единственном пути от корня к искомой записи равно числу сравнений, выполняемых алгоритмом двоичного поиска при попытке отыскания нужной записи.

 

Рис.2.5.

Представление двоичного поиска в виде бинарного дерева

 

 

Среднее число сравнений в случае равновероятных запросов равно

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

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

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

 

Поиск по бинарному дереву

 

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

позволяет достичь минимума среднего числа сравнений в условиях неравновероятных запросов;

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

Для реализации бинарного дерева в явном виде в каждой записи таблицы помимо поля ключа предусматривается два поля указателей U_R и U_L, в которых записываются адреса правого и левого преемников вершины дерева, соответствующей данной записи. Для свободных вершин, не имеющих преемников, в указателях помещается специальный символ «T» (тупик). Чтобы иметь возможность начать поиск, требуется адрес записи, соответствующей корню дерева: будем хранить его в специальной ячейке V. Пример явного задания бинарного дерева приведен на рис. 2.6.

Рис.2.6

Явное задание бинарного дерева поиска

 

На каждом i-м шаге алгоритма поиска по бинарному дереву производится чтение из таблицы некоторой записи с ключом K_i и указателями Uⁱ_R и Uⁱ_L. При этом первый шаг всегда начинается с корня дерева, адрес которого содержится в указателе V.

На каждом шаге ключ K_i сравнивается с аргументом поиска A и по результатам сравнения выполняются следующие действия:

а) A= K_i – запись найдена, поиск заканчивается удачно;

б) A> K_i, Uⁱ_R =T или A< K_i, Uⁱ_L =T – тупик, запись в таблице отсутствует, поиск заканчивается неудачно;

в) A> K_i, Uⁱ_R ≠T – поиск продолжается, считывается очередная запись (K_i+1, Uⁱ⁺¹_R, Uⁱ⁺¹_L) по указателю Uⁱ_R;

г) A< K_i, Uⁱ_L ≠T – поиск продолжается, считывается очередная запись (K_i+1, Uⁱ⁺¹_R, Uⁱ⁺¹_L) по указателю Uⁱ_L.

При продолжении поиска (случаи в и г) аналогичным образом выполняется (i+1)-й шаг для записи K_i+1, полученной на i-м шаге.

 

Конкретный вид бинарного дерева для заданного множества записей определяется порядком, в котором записи заносятся в таблицу. Например, оно может выродиться в цепочку (линейный список) или принять сбалансированный вид, когда свободные вершины находятся на примерно одинаковом расстоянии от корня (см. рис. 2.7).

 

Рис.2.7

Возможные варианты бинарного дерева

 

В первом случае на рис. 2.7 поиск по бинарному дереву соответствует последовательному поиску, во втором – двоичному. Следовательно, необходимое число сравнений определяется видом бинарного дерева. Например, при равновероятных запросах и удачном поиске среднее число сравнений меняется примерно от log₂N-1 (двоичный поиск) и до N/2 (последовательный поиск). Если записи добавляются в таблицу в случайном порядке с одинаковыми вероятностями (что часто встречается на практике), то получаются бинарные деревья, для которых среднее число сравнений приблизительно равно . Это несколько больше, чем для двоичного поиска, но существенно меньше (особенно при больших N), чем для последовательного поиска.

Как уже отмечалось, метод бинарного дерева широко применяется для организации пои<