В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 27
Текст из файла (страница 27)
е. 0 6 h1 (id) 6 N − 1, где id — символьное представлениеидентификатора). Таким образом, функция расстановки сопоставляет идентификатору некоторый адрес в таблице символов.Пусть мы хотим найти в таблице идентификатор id. Если элемент таблицыс номером h1 (id) не заполнен, то это означает, что идентификатора в таблиценет. Если же он занят, то это еще не означает, что идентификатор id в таблицу занесен, поскольку (вообще говоря) много идентификаторов могут иметьодно и то же значение функции расстановки.
Для того чтобы определить,нашли ли мы нужный идентификатор, сравниваем id с элементом таблицыh1 (id). Если они равны — идентификатор найден, если нет — надо продолжатьпоиск дальше.Для этого вычисляется вторичная функция расстановки h2 (h1 ) (значением которой опять-таки является некоторый адрес в таблице символов).Возможны четыре варианта:– элемент таблицы не заполнен (т. е. идентификатора в таблице нет),– идентификатор элемента таблицы совпадает с искомым (т.
е. идентификатор найден),– адрес элемента совпадает с уже просмотренным (т. е. таблица вся просмотрена, но идентификатора нет),– предыдущие варианты не выполняются, так что необходимо продолжатьпоиск.Для продолжения поиска применяется следующая функция расстановки:h3 (h2 ), h4 (h3 ) и т. д. Как правило, hi = h2 для i > 2. Аргументом функцииh2 является целое в диапазоне [0, N − 1], и она может быть быть устроенапо-разному. Приведем три варианта.1) h2 (i) = (i + 1) mod N .Берется следующий (циклически) элемент массива.
Этот вариант плохтем, что занятые элементы «группируются», образуют последовательные140Глава 7. Организация таблиц символовзанятые участки и в пределах этого участка поиск становится по существулинейным.2) h2 (i) = (i + k) mod N , где k и N взаимно просты.По существу это предыдущий вариант, но элементы не накапливаютсяв последовательных элементах, а «разносятся».3) h2 (i) = (a ∗ i + c) mod N — «псевдослучайная последовательность».Здесь c и N должны быть взаимно просты, b = a − 1 кратно p для любогопростого p, являщегося делителем N , b кратно 4, если N кратно 4 [6].Поиск в таблице расстановки можно описать следующей функцией (здесьNULL некоторое выделенное значение типа int, например, −1):class BoolRef {boolean val;}class IntRef {int val;}void Search(String Id,BoolRef Yes,IntRef Point){int H0=h1(Id), H=H0;while (1){if (Empty(H)==NULL){Yes.val=false;Point.val=H;return;}else if (IdComp(H,Id)==0){Yes.val=true;Point.val=H;return;}else H=h2(H);if (H==H0){Yes.val=false;Point.val=NULL;return;}}}Функция IdComp(H,Id) сравнивает элемент таблицы на входе H с идентификатором и вырабатывает 0, если они равны.
Функция Empty(H) вырабатывает NULL, если вход H пуст. Функция Search присваивает параметрамYes и Pointer соответственно следующие значения :true, P — если найден требуемый идентификатор, где P — указательна вход в таблице, соответствующий этому идентификатору;false, NULL — если искомый идентификатор не найден, причем в таблиценет свободного места;7.3. Таблицы расстановки со списками141false, P — если искомый идентификатор не найден, но в таблице естьсвободный вход P.Занесение элемента в таблицу можно осуществить следующей функцией:int Insert(String Id){BoolRef Yes;IntRef Point;Search(Id,Yes,Point);if (!Yes.val && (Point.val!=NULL)) InsertId(Point,Id);return(Point.val);}Здесь функция InsertId(Point,Id) заносит идентификатор Id для входа Point таблицы.7.3.
Таблицы расстановки со спискамиТолько что описанная схема страдает одним недостатком — возможностьюпереполнения таблицы. Рассмотрим ее модификацию, когда все элементы,имеющие одинаковые значения (первичной) функции расстановки, связываются в список (при этом отпадает необходимость использования функций hiдля i > 2). Таблица расстановки со списками — это массив указателей насписки элементов (рис. 7.3).Вначале таблица расстановки пуста (все элементы имеют значение NULL).При поиске идентификатора Id вычисляется функция расстановки h(Id)Рис. 7.3142Глава 7.
Организация таблиц символови просматривается соответствующий линейный список. Поиск в таблице может быть описан следующей функцией:class Element{String IdentP;Element Next;};ArrayList T = new ArrayList(N);Element Search(String Id){ Element P;P=(Element)T.get(h(Id));while (1){if (P==null) return(null);else if (IdComp(P.IdentP,Id)==0) return(P);else P=P.Next;}}Занесение элемента в таблицу можно осуществить следующей функцией:Element Insert(String Id){ Element P,H;P=Search(Id);if (P!=null) return(P);else {H=H(Id);P=new Element();P.Next=(Element)T.get(h(Id));P.IdentP=Include(Id);T.add(H,P);}return(P);}Функция Include заносит идентификатор в таблицу идентификаторов.Алгоритм иллюстрируется рис. 7.4.Рис.
7.47.4. Функции расстановки1437.4. Функции расстановкиМного внимания исследователи уделили тому, какой должна быть (первичная) функция расстановки. Основные требования к ней очевидны: онадолжна легко вычисляться и распределять равномерно. Один из возможныхподходов здесь заключается в следующем.1. По символам строки s определяем положительное целое H .
Преобразовать одиночные символов в целые обычно можно средствами языка реализации. В Паскале для этого служит функция ord, в Си при выполненииарифметических операций символьные значения трактуются как целые.2. Преобразуем H , вычисленное выше, в номер элемента, т. е. целое между0 и N − 1, где N — размер таблицы расстановки, например, взятием остаткапри делении H на N .Функции расстановки, учитывающие все символы строки, распределяютлучше, чем функции, учитывающие только несколько символов, например,в конце или в середине строки. Но такие функции требуют больше вычислений.Простейший способ вычисления H — сложение кодов символов. Передсложением с очередным символом можно умножить старое значение Hна константу q , т.
е. полагаем H0 = 0, Hi = q ∗ Hi−1 + ci для 1 6 i 6 k , k —длина строки. При q = 1 получаем простое сложение символов. Вместо сложения можно выполнять сложение ci и q ∗ Hj−1 по модулю 2. Переполнениепри выполнении арифметических операций можно игнорировать.Функция Hashpjw, приведенная ниже [3], вычисляется, начиная с H = 0(предполагается, что используются 32-битовые целые). Для каждого символасдвигаем биты H на 4 позиции влево и добавляем очередной символ. Есликакой-нибудь из четырех старших битов H равен 1, то сдвигаем эти 4 битана 24 разряда вправо, затем складываем по модулю 2 с H и устанавливаемв 0 каждый из четырех старших битов, равных 1:final int PRIME = 211;final int EOS = ’\0’;int Hashpjw(String s){char p;int H=0, g, i;int sLen = s.length();for (i=0; i<sLen; i++){H=(H<<4)+s.charAt(i);if ((g=H&0xf0000000)!=0){H=H^(g>>24);H=H^g;}}return H%PRIME; }144Глава 7.
Организация таблиц символов7.5. Таблицы на деревьяхРассмотрим еще один способ организации таблиц символов — с использованием двоичных деревьев.Ориентированное дерево называется двоичным, если у него в каждуювершину, кроме одной (корня), входит одна дуга и из каждой вершинывыходит не более двух дуг. Ветвью дерева называется поддерево, состоящееиз некоторой дуги данного дерева, ее начальной и конечной вершин, а такжевсех вершин и дуг, лежащих на всех путях, выходящих из конечной вершиныэтой дуги. Высотой дерева называется максимальная длина пути в этомдереве от корня до листа.Пусть на множестве идентификаторов задан некоторый линейный (например, лексикографический) порядок ≺, т. е.
некоторое транзитивное, антисимметричное и антирефлексивное отношение. Таким образом, для произвольнойпары идентификаторов id1 и id2 либо id1 ≺ id2 , либо id2 ≺ id1 , либо id1совпадает с id2 .Каждой вершине двоичного дерева, представляющего таблицу символов,сопоставим идентификатор. При этом если вершина (которой сопоставлен id)имеет левого потомка (которому сопоставлен idL ), то idL ≺ id; если онаимеет правого потомка (idR ), то id ≺ idR .
Элемент таблицы изображенна рис. 7.5.Рис. 7.5Узел дерева описывается как класс TreeElement:class TreeElement{String IdentP;TreeElement Left, Right;};Поиск в такой таблице может быть описан следующей функцией:TreeElement SearchTree(String Id,TreeElement TP){int comp;if (TP==null) return null;comp=IdComp(Id,TP.IdentP);if (comp<0) return(SearchTree(Id,TP.Left));if (comp>0) return(SearchTree(Id,TP.Right));return TP;}7.5. Таблицы на деревьях145Занесение в таблицу осуществляется функциейvoid InsertTree(String Id,TreeElement TP){int comp=IdComp(Id,TP.IdentP);if (comp<0)if (TP.Left != null)InsertTree(Id,n.Leftt);else {n.Left = new TreeElement();n.Left.InentP = Id;n.Left.Left = null;n.Left.Right = null;}}else if (comp>0)if (TP.Right != null)InsertTree(Id,n.Right);else {n.Right = new TreeElement();n.Right.InentP = Id;n.Right.Left = null;n.Right.Right = null;}}}struct TreeElement * Fill(String Id,struct TreeElement * P,struct TreeElement ** FP){ if (P==NULL){P=alloc(sizeof(struct TreeElement));P->IdentP=Include(Id);P->Left=NULL;P->Right=NULL;*FP=P;return(P);}else return(InsertTree(Id,P));}Как показано в [10], среднее время поиска в таблице размера n, организованной в виде двоичного дерева, при равных вероятностях появления каждогообъекта равно (2 ln 2) log 2 n + O(1).
Однако на практике случай равных вероятностей появления объектов встречается довольно редко. Поэтому в деревепоявляются более длинные и более короткие ветви, и среднее время поискаувеличивается.Чтобы уменьшить среднее время поиска в двоичном дереве, можно в процессе построения дерева следить за тем, чтобы оно все время оставалось сбалансированным. А именно, назовем дерево сбалансированным, если ни длякакой вершины высота выходящей из нее правой ветви не отличается от высоты левой более чем на 1. Для того чтобы достичь сбалансированности,146Глава 7. Организация таблиц символовРис.
7.6в процессе добавления новых вершин дерево можно слегка перестраиватьследующим образом [1].Определим для каждой вершины дерева характеристику, равную разностивысот выходящих из нее правой и левой ветвей. В сбалансированном деревехарактеристика вершины может быть равной −1, 0 или 1, для листьев онаравна 0.Пусть мы определили место новой вершины в дереве. Ее характеристикаравна 0. Назовем путь, ведущий от корня к новой вершине, выделенным.При добавлении новой вершины могут измениться характеристики только техвершин, которые лежат на выделенном пути.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
