- •Теоретические основы информационных процессов введение
- •1.Кодирование сообщений
- •§1. Информационные процессы
- •§2. Передача и кодирование данных в аис
- •§3. Сжатие данных как информационный процесс
- •§4. Сжатие на основе смыслового содержания данных
- •§5. Переход от естественных обозначений к более компактным.
- •§6. Подавление повторяющихся символов
- •§7. Кодирование часто используемых данных
- •§8. Сжатие данных на основе сравнения
- •§9. Целесообразность сжатия данных
- •§10. Сжатие на основе статистических свойств данных и неравномерные коды
- •§11. Двоичное кодирование и бинарные деревья
- •§12. Кодирование сообщений словами переменной длины
- •§13. Процедура Шеннона-Фано
- •§14. Процедура Хафмана
- •§15. Кодирование последовательностей символов
- •§16. Помехоустойчивость данных
- •§17. Методы обеспечения помехоустойчивости
- •§18. Способность кодов обнаруживать и исправлять ошибки
- •2. Поиск данных
- •§1. Проблема поиска данных
- •§ 2. Виды зу
- •§3. Поиск на основе преобразования ключа в адрес
- •§4. Перемешивание
- •§5. Поиск на основе сравнения ключей
- •§6. Последовательный поиск
- •§7. Блочный поиск
- •§8. Двоичный поиск
- •§9. Поиск по бинарному дереву
- •§10. Чистый бинарный поиск
- •§11. Помехоустойчивый поиск
- •§12. B-деревья: общие сведения
- •§13. B-деревья: добавление ключей
- •§14. B-деревья: удаление ключей
§7. Блочный поиск
Пусть файл или таблица упорядочены по возрастанию ключей и пусть на каждом шаге поиска имеется возможность выбирать любую по счету запись для сравнения ее ключа с аргументом поиска. Как организовать последовательность сравнений в этом случае, чтобы уменьшить сложность поиска?
Можно просматривать не каждую, а, например, сотые записи таблицы. Как только будет обнаружена запись с ключом, превышающим аргумент поиска, просматриваются (методом последовательного поиска) последние пропущенные 99 записей. Этот алгоритм называется поиском с пропусками или блочным поиском: записи группируются в блоки и сначала ищется нужный блок, а затем в нем ищется нужная запись.
Оптимальное число записей в блоке при равновероятных запросах равно квадратному корню из числа записей в файле. Среднее число записей, которые должны быть просмотрены при удачном поиске, в этом случае также равно . Примем это без доказательства.
§8. Двоичный поиск
Пусть, как и в предыдущем случае, таблица поиска упорядочена по возрастанию ключей. Если теперь выбрать для проверки запись из середины таблицы, то, если эта запись не окажется искомой, множество возможных претендентов сократится приблизительно в два раза: искомая запись находится в одной из половин таблицы. На этой идее последовательного деления множества записей пополам основан двоичный или дихотомический поиск.
На каждом i-м шаге двоичного поиска считывается и сравнивается с аргументом запись , находящаяся примерно в середине некоторого множествапоследовательно расположенных записей таблицы
,
где ,исоответствуют начальной, серединной и конечной записям множестванаi-м шаге поиска. Взяв в качестве исходного множества всю таблицу, шаги повторяются до тех пор, пока либо аргумент поиска не совпадет с ключом сравниваемой записи, либо множествоне станет пустым. В первом случае поиск оканчивается удачно, во втором - неудачно. В качестве множествадля следующего шага берется правое или левое подмножествотекущего шага, причем
Рис. 2.4 поясняет алгоритм двоичного поиска на примере таблицы из 16 записей и значения аргумента . В этом методе особенно удивительно то, что уже после двух сравнений три четверти таблицы будут вне области поиска.
Рис.2.4.
Пример двоичного поиска записи в таблице
Двоичный поиск удобно представить в виде двоичного дерева (см. рис.2.5). Вершинами дерева двоичного поиска являются ключи, сравниваемые с аргументом поиска. При этом корнем является ключ записи, сравниваемой на первом шаге. Поиск можно интерпретировать как прохождение дерева от корня до искомой записи. Если достигнута конечная вершина, а заданный ключ не найден, то искомая запись в файле отсутствует. Число вершин на единственном пути от корня к искомой записи равно числу сравнений, выполняемых алгоритмом двоичного поиска при попытке отыскания нужной записи.
Рис.2.5.
Представление двоичного поиска в виде бинарного дерева
Среднее число сравнений в случае равновероятных запросов равно
Ни один метод, основанный на сравнении ключей, не может дать лучших результатов при равновероятных запросах.
Рассмотрим случай неравновероятных запросов. Пусть, например, некоторая запись файла запрашивается с вероятностью, намного превосходящей суммарную вероятность запросов остальных записей. В этом случае, очевидно, что, прежде всего, целесообразно проверить эту запись, а только затем - остальные. Приведенные рассуждения показывают, что в случае неравновероятных запросов двоичный поиск, вообще говоря, не является оптимальным.
Даже в случае равновероятных запросов преимущества двоичного поиска не всегда бесспорны. Это, прежде всего, относится к ситуациям, когда время считывания записей непостоянно. В последнем случае доступ к серединным записям может быть сопряжен с большими затратами времени, чем доступ к записям в начале таблицы и алгоритм двоичного поиска оказывается менее эффективным.