ПРЯМОЙ ДОСТУП К ТАБЛИЦЕ ИЛИ МЕТОД ИНДЕКСОВ

Суть этого метода состоит в том, что по символам цепочки (идентификатора) вычисляется индекс, который обеспечивает прямой доступ к таблице (индекс массива). В качестве примера рассмотрим проблему идентификации переменных языка MINI–BASIC. Переменная в нем либо английская буква, либо буква, за которой следует цифра. Всего имеется 286 допустимых переменных MINI–BASIC. Так как это число невелико, то можно позволить себе завести по одному элементу таблицы для каждой допустимой переменной. Тогда проблема поиска переменной сводиться к простому преобразованию имени в индекс. Один из способов состоит в присваивание индексу значения от 1 до 26 для каждой входной буквы английского алфавита. Далее, если следующий символ – произвольная цифра d, то к индексу буквы прибавляется число 26*(d+1). Это значит, что переменная Z получит номер 26, A0 – 27, а Z9 – 286.

Индексный метод можно эффективно применять при выполнении 3–х условий. Во–первых, число слов не должно быть слишком большим. Поэтому, такой метод нельзя применять даже для имен переменных ФОРТРАНа (не более шести символов), т.к. их более миллиарда. Во–вторых, индекс должен легко вычисляться. Это условие может исключить даже небольшое множество ключевых слов, так как хороший способ построения индекса по ним вряд ли удастся предложить. В–третьих, объем множества слов фиксируется при построении, так как изменение метода вычисления индекса во время компиляции требует реорганизации всей таблицы. Если учесть эти три условия, то становится очевидным, что рассматриваемым методом можно воспользоваться нечасто. Тем не менее, когда он применим, поиск и включение элемента (отметка что он включен) осуществляется с минимальными затратами времени.

НЕУПОРЯДОЧЕННАЯ ТАБЛИЦА ИЛИ МЕТОД ЛИНЕЙНОГО СПИСКА

Наиболее простой метод поиска состоит в том, что входное слово сопоставляется с каждым элементом хранимым в памяти массива или списка слов, до тех пор, пока не происходит совпадение (если оно возможно). Добавляются же элементы к текущему концу заполненной части массива или к последнему элементу в списке. У этого метода есть лишь один недостаток: поиск по длинной таблице займет много времени! Если в таблице N элементов, то ожидаемое число сопоставлений, необходимых для обнаружения случайно выбранного элемента, равно (N+1)/2.

УПОРЯДОЧЕННАЯ ТАБЛИЦА. БИНАРНЫЙ, ДВОИЧНЫЙ ИЛИ ЛОГАРИФМИЧЕСКИЙ ПОИСК

Время поиска по таблице большого объема можно значительно сократить, если элементы таблицы упорядочены по аргументу, например, лексикографически, т.е. по алфавиту. Эффективным методом поиска в таком списке является бинарный (двоичный, логарифмический) поиск. Имя S, которое следует найти, сравнивается с аргументом элемента с номером (N+1)/2 в середине таблицы. Если этот элемент не является требуемым, то мы должны просматривать только блок элементов пронумерованных от 1 до (N+1)/2–1 или блок от (N+1)/2+1 до N в зависимости от того, меньше или больше искомый идентификатор S того элемента, с которым его сравнивали. Затем мы повторяем процесс для блока меньшего размера. Так как на каждом шаге число элементов, которые могут содержать S, сокращается наполовину, то максимальное число сравнений – 1+log₂N. Если N=2, то необходимо, самое большое, 2 сравнения (N=4, – то 3, N=8, – то 4). Для N=128 потребуется не более 8 сравнений, в то время как среднее время поиска в неупорядоченной таблице того же объема составит 64 сравнения.

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

1. Находится k для которого S_k < S < S_k+1.

2. Элемент N сдвигается на позицию N+1, N–1 – на позицию N и т.д. Элемент с номером k+1 сдвигается на позицию k+2.

3. S заносится на место k+1.

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

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

На рис. 3.3 показано представление таблицы в виде дерева поиска для некоторого подмножества ключевых слов и стандартных типов языка С.

При поиске слова for в этом дереве оно последовательно сравнивается со словами if, do, enum и for.

Разместив дерево в памяти, можно добавлять к нему слова не нарушая этого размещения. Слово bitset, например, присоединится к слову break, а слово delete к слову default. Но, к сожалению, после таких добавлений результирующее время поиска может превышать логарифмическую границу. Для слова delete, например, потребуется 6 сравнений. Если желательно расширить множество слов, сохранив логарифмическое время поиска, необходимо проводить реорганизацию структуры дерева.

Поиск по сайту: